More Results on Perfect Hashing for Implementing Object-Oriented Languages
Abstract
Late binding and subtyping create run-time overhead for object-oriented languages, especially in the context of both \emph{multiple inheritance} and \emph{dynamic loading}, for instance for \JAVA interfaces. In a previous paper, we have proposed a novel approach based on \emph{perfect hashing} and truly constant-time hashtables for implementing subtype testing and method invocation in a dynamic loading setting. In this first study, we based our efficiency assessment on Driesen's abstract computational model for the time standpoint, and on large-scale benchmarks for the space standpoint. The conclusions were that the technique was promising but required further research in order to assess its scalability. This article presents some new results about this approach that reinforces its interest. We propose and test both new hashing functions and an inverted problem which amounts to selecting the best class identifiers in order to minimize the overall hashtable size. Experiments within an extended testbed with random class loading and under careful assumptions about what should be a sensible class loading order show that perfect hashing scales up gracefully. Furthermore, we tested perfect hashing for subtype testing and method invocation in the \PRM compiler and we compare it with the coloring technique that amounts to maintain in multiple inheritance the single inheritance implementation. The result exceeds our expectations.