Perfect class hashing and numbering for object-oriented implementation

摘要

Late binding and subtyping create run-time overhead for object-oriented languages, especially in the context of both multiple inheritance and dynamic loading, for instance for JAVA interfaces. In a previous article, we proposed a novel approach based on 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 aspect, and on large-scale benchmarks for the space aspect. The conclusions were that the technique was promising but required further research in order to assess its scalability. This article presents some new results on perfect class hashing that enhance its interest. We propose and test both new hashing functions and an inverse problem that amounts to selecting the best class identifiers in order to minimize the overall hashtable size. This optimizing approach is proven to be optimal for single-inheritance hierarchies. Experiments within an extended testbed with random class loading and under cautious assumptions about what should be a sensible class-loading order show that perfect class hashing scales up gracefully, especially on JAVA-like multiple-subtyping hierarchies. Furthermore, perfect class hashing is implemented in the Prm compiler testbed, and compared here with the coloring technique, which amounts to maintaining the single-inheritance implementation in multiple inheritance. The overall conclusion is that the approach is efficient from both time and space standpoints with the bit-wise and hashing function. In contrast, the poor time efficiency of modulus hashing function on most processors is confirmed.