Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Function Dispatch Tables in C (2019)

blog.alicegoldfuss.com

Post reply on HN
Print view View original

41–50 of 52 posts

Re: Function Dispatch Tables in C (2019)

#41

Post by JonChesterfield »

xboxnolifes wrote: post #12

> Having 100 cases means we could potentially check 100 cases before selecting one. case statements are O(n), where n is the number of case/switch statements possible. I was under the impression that most (all?) C compilers would optimize this use-case into a jump-table, turning this case statement usage into an O(1) operation. Or is this a C++ feature that I'm thinking of?

Quite a lot of effort goes into compiling switch statements. Jump tables and binary search are likely, as is a mixture of the two based on distribution of cases.

I haven't seen computed goto but wouldn't be surprised if some compilers have that as a third option.

Re: Function Dispatch Tables in C (2019)

#42

Post by actionfromafar »

unwind wrote: post #39

Uh, this is a few years old, and perhaps the author was learning as they went. Still, I think this passage is a bit too much: Quick refresher: a pointer is a location in memory aka a memory address. That memory address can contain anything: an integer, a float, the middle of a string. It can also store the name of a function, also known as its label. A function’s name is its address in memory. A pointer is not a loca…

If you come at it from an assembly perspective, the explanation makes a lot of sense IMHO. But it could use a qualifier that the "name" is just a number and not the actual name as in the source code.

Re: Function Dispatch Tables in C (2019)

#43

Post by lelanthran »

boffinAudio wrote: post #26
asveikau wrote: post #18

Earlier quoted context omitted.

Modern CPUs with pipelining, branch prediction, speculative execution, caching do best with fewer jumps, small code size, predictable jump targets, sequential access. A tight loop of "jump to the address i just loaded from this 64 bit quantity" throws a total wrench in the middle of it and will have those mechanisms stall. Imagine a sorting algorithm with a jump into a callback to compare the elements. Then compare w…

I think you are constructing a straw man argument. The jump-table approach is just as likely to be a candidate for the optimization you claim will get in the way, as the code using if/switch statements. In fact, the compiler can see that simple call through the jump table and optimize it even better - maybe even by inlining. The question is, how are you sure this isn't happening? The answer is, you're not - unless yo…

> In fact, the compiler can see that simple call through the jump table and optimize it even better - maybe even by inlining.

Sure, if the table is `static const`. Otherwise the compiler generates code to load the table address, add the offset, retrieve the address and then jump to it.

If the table is defined in the current translation unit[1], or if it is visible but not const[2], or if it is visible but not static[3][4], the compiler cannot safely inline anything.

If the table is: a) Defined in the current function b) Does not escape the scope of the current function c) Is qualified with static d) Is qualified with const

Then sure, the compiler can figure out the best optimisation. Luckily, for benchmark purposes all of the above will be true so your benchmark program will show a performance benefit to the jump table.

Real programs with jump tables are never able to satisfy all those conditions.

[1] If defined elsewhere, the compiler doesn't know the contents of the table and so has generate code to look it up every time.

[2] If it isn't const, the compiler cannot assume that the entries in the table don't change, and thus has generate code to look it up every time.

[3] If the table is visible outside of the current scope or translation unit, the compiler cannot assume that the entries don't change, and once again has to generate code to perform the lookup every time.

[4] If the table is defined in the current function but not static, the compiler will have to generate code to populate that table every single time the function is entered.

Re: Function Dispatch Tables in C (2019)

#44

Post by asveikau »

boffinAudio wrote: post #26
asveikau wrote: post #18

Earlier quoted context omitted.

Modern CPUs with pipelining, branch prediction, speculative execution, caching do best with fewer jumps, small code size, predictable jump targets, sequential access. A tight loop of "jump to the address i just loaded from this 64 bit quantity" throws a total wrench in the middle of it and will have those mechanisms stall. Imagine a sorting algorithm with a jump into a callback to compare the elements. Then compare w…

I think you are constructing a straw man argument. The jump-table approach is just as likely to be a candidate for the optimization you claim will get in the way, as the code using if/switch statements. In fact, the compiler can see that simple call through the jump table and optimize it even better - maybe even by inlining. The question is, how are you sure this isn't happening? The answer is, you're not - unless yo…

I wrote this:

> A good optimizer would detect this and replace the indirect call with inlining

And it seems like it's true for your experiment. These days, this is a common optimization, provided the optimizer can figure it out. A link time optimizer can even do it between complication units. I remember when it wasn't possible or common.

Re: Function Dispatch Tables in C (2019)

#45

Post by dmitrygr »

> case statements are O(n), where n is the number of case/switch statements possible.

What now? Not even close. Any modern or even semi-modern (2005-vintage) compiler will compile large switches into a jump table (O(1)) and medium ones into a tree of branches, giving O(log n)

Re: Function Dispatch Tables in C (2019)

#46

Post by teknopaul »

boffinAudio wrote: post #40
Joker_vD wrote: post #38

Earlier quoted context omitted.

Well, which is actually faster? Also, try benchmarking while there is a lot of context switching goes on in background (I vaguely recall a story about how some non-optimal looking code actually fared better when the processor constantly kept flushing its caches/buffers but can't remember the exact details).

I measured it with a simple modification of the above program to call each method() 5,000,000 times and sample the time taken. With minimal optimizations (-O), the call_table is moderately slower. This is probably because with gcc's default optimizer, it doesn't recognize the inline-ability of call_table(), whereas it does with the other method()'s. With all optimizations on (-O3): all methods are, performance-wise,…

In a switch you see the index as a number in the case statement, above a small number, finding the value of choice is going to be unreadable, no? You have to count the position of the function you want?

Re: Function Dispatch Tables in C (2019)

#47

Post by dzaima »

boffinAudio wrote: post #37
flohofwoe wrote: post #27

Earlier quoted context omitted.

...not quite: the if-else (or switch-case) can usually inline the called function, which gets rid of the epilogue/prologue and opens up more optimization opportunities.

The call-table functions also get inlined, so the advantage is shared by both approaches, and yet the call-table produces more efficient code (no cmp/jump traps to fall into...) See my comment here for the C code and Assembly that demonstrates this: https://news.ycombinator.com/item?id=31834241

I can't reproduce neither clang nor gcc with -O3 inlining functions in a call table: https://godbolt.org/z/E7Tj31vox

Nor do I see any of that kind of behavior in your linked assembly - call_table clearly contains "call *%r8", which is an indirect call to a function, definitely not inlined.

Here's a more complete test: https://godbolt.org/z/dT45aKTe1 - putting the operation in a loop (to be able to more clearly see the per-iteration cost of the operation), with -O3, both clang & gcc. While gcc decides to do comparisons (it wants at least 5 cases for a jump table apparently), clang does do the indirect jump, while neither does anything other than a call (thus suffering said register spilling & stack manipulation overhead) for the explicit function jump table.

Re: Function Dispatch Tables in C (2019)

#48

Post by dzaima »

dzaima wrote: post #47
boffinAudio wrote: post #37

Earlier quoted context omitted.

The call-table functions also get inlined, so the advantage is shared by both approaches, and yet the call-table produces more efficient code (no cmp/jump traps to fall into...) See my comment here for the C code and Assembly that demonstrates this: https://news.ycombinator.com/item?id=31834241

I can't reproduce neither clang nor gcc with -O3 inlining functions in a call table: https://godbolt.org/z/E7Tj31vox Nor do I see any of that kind of behavior in your linked assembly - call_table clearly contains "call *%r8", which is an indirect call to a function, definitely not inlined. Here's a more complete test: https://godbolt.org/z/dT45aKTe1 - putting the operation in a loop (to be able to more clearly see th…

And, some actual timings (code: https://godbolt.org/z/qnWEqs446):

    $ clang -DLEN=1024 -DITERATIONS=100000 -O3 switch.c && ./a.out
    predictable:
      call_table:   173.1ms
      switch_cases: 59.6ms
    random:
      call_table:   536.2ms
      switch_cases: 450.4ms
    $ gcc -DLEN=1024 -DITERATIONS=100000 -O3 -fcf-protection=none switch.c && ./a.out
    predictable:
      call_table:   174.5ms
      switch_cases: 114.7ms
    random:
      call_table:   581.8ms
      switch_cases: 108.8ms
    $ clang -DLEN=64 -DITERATIONS=2000000 -O3 switch.c && ./a.out
    predictable:
      call_table:   230.6ms
      switch_cases: 116.0ms
    random:
      call_table:   218.7ms
      switch_cases: 158.2ms
    $ gcc -DLEN=64 -DITERATIONS=2000000 -O3 -fcf-protection=none switch.c && ./a.out
    predictable:
      call_table:   872.7ms
      switch_cases: 146.3ms
    random:
      call_table:   740.4ms
      switch_cases: 132.2ms
The switch is faster in all cases, often by a big margin.

Re: Function Dispatch Tables in C (2019)

#49

Post by dzaima »

nynx wrote: post #10
hermitdev wrote: post #8

Earlier quoted context omitted.

I'm also dubious on the claim the switch statement is O(n). It might be in a pathological worst case, but you can pretty much bet the compiler is going to transform it into a jump table or other optimized execution (maybe a computed jump). Especially when the cases are contiguous like this... I agree that a benchmark is warranted, or at least a comparison of the generated assembly (at different optimization levels).

Also, O(n) doesn’t mean much when the CPU can execute hundreds of checks in a few tens of cycles.

Not for jumps - modern CPUs still (usually) have limit of one taken branch per cycle, or 1 to 2 untaken branches. And usually branch prediction will be the limiting factor anyway, for which a single branch is gonna be faster than many.

Re: Function Dispatch Tables in C (2019)

#50

Post by boffinAudio »

teknopaul wrote: post #46
boffinAudio wrote: post #40

Earlier quoted context omitted.

I measured it with a simple modification of the above program to call each method() 5,000,000 times and sample the time taken. With minimal optimizations (-O), the call_table is moderately slower. This is probably because with gcc's default optimizer, it doesn't recognize the inline-ability of call_table(), whereas it does with the other method()'s. With all optimizations on (-O3): all methods are, performance-wise,…

In a switch you see the index as a number in the case statement, above a small number, finding the value of choice is going to be unreadable, no? You have to count the position of the function you want?

Small number? I think you mean properly documented enum. ;)

But yeah, point taken. Its a style thing. I've just gotten allergic to wading through multiple-1000 lines of switch/case statements while trying to keep the state machine 'intentions' in my head, comparing with 'actuality' in the debugger.

I much prefer the smaller lines-of-code approach, even if it has been pointed out to me now by others in this thread that switch() is faster - maintenance is a performance index, also... especially when going back to code that was written some time >1year ago, etc.

Post reply on HN