function dispatch
Stephen Weeks
MLton@sourcelight.com
Wed, 13 Sep 2000 11:33:15 -0700 (PDT)
> I just finished reading `Efficient Dynamic Dispatch without Virtual Function
> Tables. Time SmallEiffel Compiler', OOPSLA 1997.
...
> The actual dispatch they generate (in C) is not a switch but a binary search.
> In a test where they have a loop doing function calls (which are NOT
> inlines), switching between 3 different possibilities (round robin) they find
> that on the 200 MHz Pentium Pro this is about twice as fast as calling
> indirectly. They then did tests where the dispatch has 50 choices, once
> where they went round robin again, and a separate benchmark where they always
> go to the same case. In both cases the binary search is epsilon slower (6%
> in the round robin case, 9% in the constant case).
So the correct conclusion for MLton, and in particular for the X86 backend, is
that we should always use binary searches? I am slightly confused by the
difference between indirecting through a code pointer and using a jump table.
Will they have roughly the same cost? Why does gcc often use jump tables
instead of binary searches?