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?