function dispatch

[Henry Cejtin]

I  just finished reading `Efficient Dynamic Dispatch without Virtual Function
Tables.  Time  SmallEiffel  Compiler',  OOPSLA  1997.   It  is  really  quite
interesting in relation to MLton.  The analogue to calling an unknown closure
is, as usual in object oriented languages, calling  a  method  in  an  object
whose  type  is  a  subtype  of some fixed type.  Just like MLton, instead of
indirecting through a code pointer, they do defunctionalization and  dispatch
by doing a `switch' on an integer.  Just like MLton they point out that a big
advantage of this is that they can then inline the method bodies.   It  isn't
clear  how precise their analysis is, but it is truly astoundingly fast: on a
self-compilation test, they can translate the  compiler  to  C  code  (50,000
lines  of Eiffel => 65,000 lines of C) in 10 CPU seconds on a 200 MHz Pentium
Pro.

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).  Note, it is vital for
this that  they  use  a  binary  search  (unwound).   With  that  they  do  6
comparisons, while with a linear search it would be 25 average.

Note,  they  don't inline the dispatch function, but have a different one for
each set of classes that the object might be (just lik MLton again).