Premium
Perfect class hashing and numbering for object‐oriented implementation
Author(s) -
Ducournau Roland,
Morandat Floréal
Publication year - 2011
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.1024
Subject(s) - computer science , dynamic perfect hashing , universal hashing , hash function , scalability , perfect hash function , theoretical computer science , class (philosophy) , k independent hashing , compile time , inheritance (genetic algorithm) , hash table , parallel computing , compiler , double hashing , programming language , database , artificial intelligence , biochemistry , chemistry , gene
Abstract 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 J AVA 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 J AVA ‐like multiple‐subtyping hierarchies. Furthermore, perfect class hashing is implemented in the P RM 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. Copyright © 2010 John Wiley & Sons, Ltd.