Perfect Hashing as an Almost Perfect Subtype Test

Roland Ducournau 1
1 MAREL - Models And Reuse Engineering, Languages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Subtype tests are an important issue in the implementation of object-oriented programming languages. Many techniques have been proposed, but none of them perfectly fulfills the five requirements that we have identified: constant-time, linear-space, multiple inheritance, dynamic loading and inlining. In this paper, we propose a subtyping test implementation which presents a mixture of usual hashtables and Cohen's display, a well known technique for single inheritance hierarchies. This novel approach is based on \emph{perfect hashing}, an optimized and truly constant-time variant of hashing which applies to \emph{immutable} hashtables. We show that the resulting technique closely meets all five requirements. Furthermore, in the framework of \JAVA-like languages---characterized by single inheritance of classes and multiple subtyping of interfaces---perfect hashing also applies to method invocation when the receiver is typed by an interface. The proposed technique is compared to some alternatives, including the proposal by Palacz and Vitek [2003]. Time-efficiency is assessed at the cycle level in the framework of Driesen's pseudo-code and the linear-space criterion is validated by statistical simulation on benchmarks consisting of large-scale class hierarchies.
Type de document :
Article dans une revue
ACM Transactions on Programming Languages and Systems (TOPLAS), ACM, 2008, 30 (6), pp.56. 〈10.1145/1391956.1391960〉
Liste complète des métadonnées
Contributeur : Roland Ducournau <>
Soumis le : jeudi 31 janvier 2008 - 08:47:05
Dernière modification le : jeudi 11 janvier 2018 - 06:26:11

Lien texte intégral




Roland Ducournau. Perfect Hashing as an Almost Perfect Subtype Test. ACM Transactions on Programming Languages and Systems (TOPLAS), ACM, 2008, 30 (6), pp.56. 〈10.1145/1391956.1391960〉. 〈lirmm-00228321〉



Consultations de la notice