Minimizing Row Displacement Dispatch Tables

Row displacement dispatch tables implement message dispatching fordynamically-typed languages with a run time overhead of one memory indirectionplus an equality test. The technique is similar to virtual function tablelookup, which is, however, restricted to statically typed languages like C++.We show how to reduce the space requirements of dispatch tables toapproximately the same size as virtual function tables. The scheme is thengeneralized for multiple inheritance. Experiments on a number of classlibraries from five different languages demonstrate that the technique iseffective for a broad range of programs. Finally, we discuss optimizations ofthe row displacement algorithm that allow dispatch table construction of theselarge samples to take place in a few seconds.