Abstract
Minimizing Row Displacement Dispatch Tables
by: Karel Driesen and Urs Hï½lzle
Abstract:
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.
Keywords:
object-oriented languages, language implementation, messagedispatch, Holzle, Hoelzle
Date:
July 1995
Document: 1995-05
