Minimizing Row Displacement Dispatch Tables

Karel Driesen, Urs Hölzle

Abstract: Row displacement dispatch tables implement message dispatching for dynamically-typed languages with a run time overhead of one memory indirection plus an equality test. The technique is similar to virtual function table lookup, which is, however, restricted to statically typed languages like C++. We show how to reduce the space requirements of dispatch tables to approximately the same size as virtual function tables. The scheme is then generalized for multiple inheritance. Experiments on a number of class libraries from five different languages demonstrate that the technique is effective for a broad range of programs. Finally, we discuss optimizations of the row displacement algorithm that allow dispatch table construction of these large samples to take place in a few seconds.

Technical Report TRCS95-05, Computer Science Department, University of California, Santa Barbara, July 1995, also in Proceedings of OOPSLA'95 Conference, Austin, Texas, October 1995.

To get the PostScript file, click here (or uncompressed PostScript or PDF).