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

11–20 of 52 posts

Re: Function Dispatch Tables in C (2019)

#11

Post by vardump »

belgesel wrote: post #2

I was expecting some form of benchmark to see if claims about better performance is true.

Function pointer jumps definitely break most chances for a compiler to optimize a function call. But then, so does a switch statement, most of the time. (Not to mention switch statements are often transformed into jump tables anyways.)

Humans tend to do a lot better jump tables in assembler, because of better choices about register usage etc. can be made, less (or no) need to spill to stack. One of the few remaining compiler weaknesses.

Re: Function Dispatch Tables in C (2019)

#12

Post by xboxnolifes »

> 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?

Re: Function Dispatch Tables in C (2019)

#13

Post by jacknews »

As others say I'm fairly sure switch/case creates a jump table under the hood, and it also checks bounds.

Personally, I don't think a static dispatch table like this is a good example. It's really more useful where the dispatch table might be dynamic; for example if a plugin could add more maths functions.

Re: Function Dispatch Tables in C (2019)

#14

Post by Gibbon1 »

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?

If you want fun see what a C compiler does to your switch statement with -Os

My opinion is the big advantage of dispatch tables in C is decoupling modules from each other.

Tip: Taking things further: variadic function pointers.

Re: Function Dispatch Tables in C (2019)

#15

Post by asveikau »

There is a vague reference to performance and runtime efficiency, as if function pointers will magically help. The syscalls table is said to be function pointers for performance reasons?? I feel the author does not understand this. The syscall ABI needs it because it's not a direct call, it's a generic mechanism to index into a list of functions whose implementations are completely abstract to the caller...

I guarantee you for these short examples in this article, using function pointers will slow everything down. The function pointer approach destroys locality, is bad for speculative execution, increases code size... A good optimizer would detect this and replace the indirect call with inlining. It's rare that you really need dynamic dispatch. There is a high performance cost for it.

The times when you need dynamic dispatch are those which you can't make a direct call, the callee is not known in advance. So things like generic callback mechanisms.

Re: Function Dispatch Tables in C (2019)

#16

Post by boffinAudio »

asveikau wrote: post #15

There is a vague reference to performance and runtime efficiency, as if function pointers will magically help. The syscalls table is said to be function pointers for performance reasons?? I feel the author does not understand this. The syscall ABI needs it because it's not a direct call, it's a generic mechanism to index into a list of functions whose implementations are completely abstract to the caller... I guarant…

Whats the performance cost exactly?

Re: Function Dispatch Tables in C (2019)

#18

Post by asveikau »

boffinAudio wrote: post #16
asveikau wrote: post #15

There is a vague reference to performance and runtime efficiency, as if function pointers will magically help. The syscalls table is said to be function pointers for performance reasons?? I feel the author does not understand this. The syscall ABI needs it because it's not a direct call, it's a generic mechanism to index into a list of functions whose implementations are completely abstract to the caller... I guarant…

Whats the performance cost exactly?

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 with a simple integer compare (1-2 instructions) inlined. In the former, you are jumping all over town, to jump targets loaded from RAM (not predictable). In the latter, one very small integer compare instruction, inline with the larger algorithm.

See also: qsort in c vs std::sort in c++

Re: Function Dispatch Tables in C (2019)

#19

Post by kibibu »

jacknews wrote: post #13

As others say I'm fairly sure switch/case creates a jump table under the hood, and it also checks bounds. Personally, I don't think a static dispatch table like this is a good example. It's really more useful where the dispatch table might be dynamic; for example if a plugin could add more maths functions.

There sure are lots of "fairly sure", "I feel" and "I think" comments in this thread.

I'm inclined to accept that Alice Goldfuss knows what theyre talking about, partly because their twitter is full of good tech stuff, and partly because I too have encountered situations where switching from a big branchy case statement to function pointers improved performance significantly.

Re: Function Dispatch Tables in C (2019)

#20

Post by vore »

boffinAudio wrote: post #17
nynx wrote: post #5

Definitely can be useful, but keep in mind that performance will usually be worse for function tables.

Why? And, if this is the case, why then do compilers turn switch statements into function tables?

While compilers do turn switch statements into jump tables, in this case storing function pointers and calling them you add the additional call overhead of saving registers, setting up the stack, etc in the function prolog and epilog.
Post reply on HN