research-article

Open access

Perfect hashing as an almost perfect subtype test

Author:

Roland DucournauAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 30, Issue 6

Article No.: 33, Pages 1 - 56

https://doi.org/10.1145/1391956.1391960

Published: 30 October 2008 Publication History

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 article, we propose a subtyping test implementation that involves a combination of usual hashtables and Cohen's display, which is a well-known technique for single inheritance hierarchies. This novel approach is based on perfect hashing, that is, an optimized and truly constant-time variant of hashing that applies to 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.

References

[1]

Agrawal, R., Borgida, A., and Jagadish, H. 1989. Efficient management of transitive relationships in large data and knowledge bases. In Proceedings of SIGMOD'89. ACM SIGMOD Record, 18, 2, 253--262.

Digital Library

[2]

Aït-Kaci, H., Boyer, R., Lincoln, P., and Nasr, R. 1989. Efficient implementation of lattice operations. ACM Trans. Program. Lang. Syst. 11, 1, 115--146.

Digital Library

[3]

Alavi, H. S., Gilbert, S., and Guerraoui, R. 2008. Extensible encoding of type hierarchies. In Proceedings of the 35th ACM Symposium on Principles of Programming Languages (POPL'08). ACM, 349--358.

Digital Library

[4]

Alpern, B., Cocchi, A., Fink, S., and Grove, D. 2001a. Efficient implementation of Java interfaces: Invokeinterface considered harmless. In Proceedings of the 16th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'01). SIGPLAN Notices, 36, 10, ACM, New York, 108--124.

Digital Library

[5]

Alpern, B., Cocchi, A., and Grove, D. 2001b. Dynamic type checking in Jalapeño. In Proceedings of the USENIX JVM'01.

Digital Library

[6]

Bacon, D. and Sweeney, P. 1996. Fast static analysis of C++ virtual function calls. In Proceedings of the 11th Annual on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'96). SIGPLAN Notices, 31, 10, ACM, New York, 324--341.

Digital Library

[7]

Barnes, J. 1995. Programming In Ada 95, first edition. Addison-Wesley, Reading, MA.

Digital Library

[8]

Caseau, Y. 1993. Efficient handling of multiple inheritance hierarchies. In Proceedings of the 8th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'93). ACM, New York, 271--287.

Digital Library

[9]

Chaitin, G. J. 1982. Register allocation & spilling via graph coloring. In Proceedings of the 1982 ACM SIGPLAN Symposium on Compiler Construction. ACM, New York, 98--105.

Digital Library

[10]

Click, C. and Rose, J. 2002. Fast subtype checking in the Hotspot JVM. In Proceedings of the ACM-ISCOPE conference on Java Grande (JGI'02). ACM, New York, 96--107.

Digital Library

[11]

Cohen, N. 1991. Type-extension type tests can be performed in constant time. ACM Trans. Program. Lang. Syst. 13, 4, 626--629.

Digital Library

[12]

Collin, S., Colnet, D., and Zendra, O. 1997. Type inference for late binding. the SmallEiffel compiler. In Proceedings of the Joint Modular Languages Conference. Lecture Notes in Computer Science, vol. 1204. Springer-Verlag, New York, 67--81.

Digital Library

[13]

Czech, Z. J. 1998. Quasi-perfect hashing. Comput. J. 41, 416--421.

[14]

Czech, Z. J., Havas, G., and Majewski, B. S. 1997. Perfect hashing. Theoret. Comput. Sci. 182, 1-2, 1--143.

Digital Library

[15]

Dijkstra, E. W. 1960. Recursive programming. Numer. Math. 2, 312--318.

Digital Library

[16]

Dixon, R., McKee, T., Schweitzer, P., and Vaughan, M. 1989. A fast method dispatcher for compiled languages with multiple inheritance. In Proceedings of the Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'89). ACM, New York, 211--214.

Digital Library

[17]

Driesen, K. 1993a. Method lookup strategies in dynamically typed object-oriented programming languages. M.S. dissertation, Vrije Universiteit Brussel.

[18]

Driesen, K. 1993b. Selector table indexing and sparse arrays. In Proceedings of the 8th Annual on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'93). ACM, New York, 259--270.

Digital Library

[19]

Driesen, K. 2001. Efficient Polymorphic Calls. Kluwer Academic Publisher.

Digital Library

[20]

Driesen, K. and Hölzle, U. 1995. Minimizing row displacement dispatch tables. Proceedings of the Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'95). ACM, New York, 141--155.

Digital Library

[21]

Driesen, K., Hölzle, U., and Vitek, J. 1995. Message dispatch on pipelined processors. In Proceedings of the European Conference on Object-Oriented Programming (ECOOP'95). Lecture Notes in Computer Science, vol. 952. Springer-Verlag, New York, 253--282.

Digital Library

[22]

Ducournau, R. 1991. Yet Another Frame-based Object-Oriented Language: YAFOOL Reference Manual. Sema Group, Montrouge, France.

[23]

Ducournau, R. 1997. La compilation de l'envoi de message dans les langages dynamiques. L'Objet 3, 3, 241--276.

[24]

Ducournau, R. 2002a. Implementing statically typed object-oriented programming languages. Rapport de Recherche 02-174, LIRMM, Université Montpellier 2.

[25]

Ducournau, R. 2002b. La coloration pour l'implémentation des langages à objets à typage statique. In Actes LMO'2002 in L'Objet vol. 8, M. Dao and M. Huchard, Eds. Lavoisier, 79--98.

[26]

Ducournau, R. 2002c. “Real World” as an argument for covariant specialization in programming and modeling. In Proceedings of the Workshops on Advances in Object-Oriented Information Systems (OOIS'02) . J.-M. Bruel and Z. Bellahsène, Eds. Lecture Notes in Computer Science, vol. 2426. Springer-Verlag, New York, 3--12.

Digital Library

[27]

Ducournau, R. 2006. Coloring, a versatile technique for implementing object-oriented languages. Rapport de Recherche 06-001, LIRMM, Université Montpellier 2.

[28]

Ellis, M. and Stroustrup, B. 1990. The Annotated C++ Reference Manual. Addison-Wesley, Reading, MA, US.

Digital Library

[29]

Fall, A. 1995. Heterogeneous encoding. In Proceedings of the International Conference on Knowledge Retrieval and Storage for Efficiency (KRUSE'95). 162--167.

[30]

Fall, A. 1998. The foundations of taxonomic encoding. Computat. Intell. 14, 598--642.

[31]

Gagnon, E. M. and Hendren, L. 2001. SableVM: A research framework for the efficient execution of Java bytecode. In Proceedings of the USENIX JVM'01. 27--40.

Digital Library

[32]

Garey, M. and Johnson, D. 1979. Computers and Intractability. A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA.

Digital Library

[33]

Gil, J. and Zibin, Y. 2005. Efficient subtyping tests with PQ-encoding. ACM Trans. Program. Lang. Syst. 27, 5, 819--856.

Digital Library

[34]

Goldberg, A. and Robson, D. 1983. Smalltalk-80, the Language and its Implementation. Addison-Wesley, Reading, MA.

Digital Library

[35]

Grove, D. and Chambers, C. 2001. A framework for call graph construction algorithms. ACM Trans. Program. Lang. Syst. 23, 6, 685--746.

Digital Library

[36]

Habib, M., Huchard, M., and Nourine, L. 1995. Embedding partially ordered sets into chain-products. In Proceedings of the International Conference on Knowledge Retrieval and Storage for Efficiency (KRUSE'95). 147--161.

[37]

Habib, M. and Nourine, L. 1994. Bit-vector encoding for partially ordered sets. In ORDAL, V. Bouchitté and M. Morvan, Eds. Lecture Notes in Computer Science, vol. 831. Springer-Verlag, New York, 1--12.

Digital Library

[38]

Habib, M., Nourine, L., and Raynaud, O. 1997. A new lattice-based heuristic for taxonomy encoding. In Proceedings of the International Conference on Knowledge Retrieval and Storage for Efficiency (KRUSE'97). 60--71.

[39]

Harbinson, S. P. 1992. Modula-3. Prentice-Hall, Englewood, Cliffs, NJ.

Digital Library

[40]

Huchard, M. and Leblanc, H. 2000. Computing interfaces in Java. In Proceedings of the IEEE International Conference on Automated Software Engineering (ASE'2000). 317--320.

Digital Library

[41]

Jensen, T. R. and Toft, B. 1995. Graph Coloring Problems. Wiley, New York.

[42]

Kiczales, G., des Rivières, J., and Bobrow, D. 1991. The Art of the Meta-Object Protocol. MIT Press, Cambridge, MA.

Digital Library

[43]

Klefstad, R., Krishna, A., and Schmidt, D. 2002. Design and performance of a modular portable object adapter for distributed, real-time, and embedded CORBA applications. In Proceedings of the 4th International Symposium on Distributed Objects and Applications. OMG.

Digital Library

[44]

Knuth, D. E. 1973. The Art of Computer Programming, Sorting and Searching. Vol. 3. Addison-Wesley, Reading, MA.

[45]

Krall, A. and Grafl, R. 1997. CACAO—a 64 bits JavaVM just-in-time compiler. Concur: Pract. Exper. 9, 11, 1017--1030.

[46]

Krall, A., Vitek, J., and Horspool, R. 1997. Near optimal hierarchical encoding of types. In Proceedings of the European Conference on Object-Oriented Programming (ECOOP'97), M. Aksit and S. Matsuoka, Eds. Lecture Notes in Computer Science, vol. 1241. Springer-Verlag, New York, 128--145.

[47]

Lippman, S. 1996. Inside the C++ Object Model. Addison-Wesley, Reading, MA.

Digital Library

[48]

Liskov, B., Curtis, D., Day, M., Ghemawat, S., Gruber, R., Johnson, P., and Myers, A. C. 1995. THETA reference manual. Technical report. MIT, Cambridge, MA.

[49]

Mehlhorn, K. and Tsakalidis, A. 1990. Data structures. In Algorithms and Complexity. Handbook of Theretical Computer Science, vol. 1, Chap. 6, Elsevier, Amsterdam, The Netherlands, 301--341.

Digital Library

[50]

Meyer, B. 1992. Eiffel: The Language. Prentice-Hall, Englewood Cliffs, NJ.

Digital Library

[51]

Meyer, B. 1997. Object-Oriented Software Construction, second ed. Prentice-Hall, Englewood Cliffs, NJ.

Digital Library

[52]

Meyer, J. and Downing, T. 1997. JAVA Virtual Machine. O'Reilly.

Digital Library

[53]

Microsoft. 2001. C&num; Language specifications, v0.28. Technical report, Microsoft Corporation, Seattle, WA.

[54]

Morris, R. 1968. Scatter storage techniques. Commun. ACM 11, 1, 38--44.

Digital Library

[55]

Mössenböck, H. 1993. Object-Oriented Programming in Oberon-2. Springer-Verlag, New York.

Digital Library

[56]

Muthukrishnan, S. and Muller, M. 1996. Time and space efficient method lookup for object-oriented languages. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. ACM/SIAM, New York, 42--51.

Digital Library

[57]

Myers, A. 1995. Bidirectional object layout for separate compilation. In Proceedings of the 10th ACM Conference on Object-Oriented Programming, Languages and Applications, OOPSLA'95. SIGPLAN Notices, 30(10). ACM, New York, 124--139.

Digital Library

[58]

Odersky, M., Spoon, L., and Venners, B. 2008. Programming in Scala, A comprehensive step-by-step guide. Artima.

Digital Library

[59]

Palacz, K. and Vitek, J. 2003. Java subtype tests in real-time. In Proceedings of the 17th European Conference on Object-Oriented Programming (ECOOP'03). Lecture Notes in Computer Science, vol. 2743. Springer-Verlag, New York, 378--404.

[60]

Pfister, B. H. C. and Templ, J. 1991. Oberon technical notes. Tech. Rep. 156, Eidgenossische Techniscle Hochschule Zurich--Departement Informatik.

[61]

Privat, J. 2006. PRM, the language. version 0.2. Rapport de Recherche 06-029, LIRMM, Université Montpellier 2.

[62]

Privat, J. and Ducournau, R. 2005. Link-time static analysis for efficient separate compilation of object-oriented languages. In Proceedings of the ACM Workshop on Programming Analysis Software Tools Engin. (PASTE'05). 20--27.

Digital Library

[63]

Pugh, W. and Weddell, G. 1990. Two-directional record layout for multiple inheritance. In Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI). ACM SIGPLAN Notices, 25, 6. ACM, New York. 85--91.

Digital Library

[64]

Pugh, W. and Weddell, G. 1993. On object layout for multiple inheritance. Tech. Rep. CS-93-22, University of Waterloo.

[65]

Queinnec, C. 1998. Fast and compact dispatching for dynamic object-oriented languages. Inf. Proc. Lett. 64, 6, 315--321.

Digital Library

[66]

Raynaud, O. and Thierry, E. 2001. A quasi optimal bit-vector encoding of tree hierarchies. application to efficient type inclusion tests. In Proceedings of the 15th European Conference on Object-Oriented Programming (ECOOP'01). Lecture Notes in Computer Science, vol. 2072. Springer-Verlag, New York, 165--180.

Digital Library

[67]

Schmidt, D. C. 1990. GPERF: A perfect hash function generator. In Proceedings of the USENIX C++ Conference. 87--102.

[68]

Schubert, L., Papalaskaris, M., and Taugher, J. 1983. Determining type, part, color and time relationship. Computer 16, 53--60.

Digital Library

[69]

Shalit, A. 1997. The Dylan Reference Manual: The Definitive Guide to the New Object-Oriented Dynamic Language. Addison-Wesley, Reading, MA.

Digital Library

[70]

Sprugnoli, R. 1977. Perfect hashing functions: a single probe retrieving method for static sets. Commun. ACM 20, 11, 841--850.

Digital Library

[71]

Steele, G. 1990. Common Lisp, the Language, Second ed. Digital Press.

Digital Library

[72]

Stroustrup, B. 1998. The C++ Programming Language, 3^e ed. Addison-Wesley, Reading, MA.

[73]

Taft, S. T., Duff, R. A., Brukardt, R. L., Ploedereder, E., and Leroy, P., Eds. 2006. Ada 2005 Reference Manual: Language and Standard Libraries. Lecture Notes in Computer Science, vol. 4348. Springer-Verlag, New York.

Digital Library

[74]

Takhedmit, P. 2003. Coloration de classes et de propriétés : étude algorithmique et heuristique. M.S. thesis, Université Montpellier 2.

[75]

Tarjan, R. E. and Yao, A. C. C. 1979. Storing a sparse table. Commun. ACM 22, 11, 606--611.

Digital Library

[76]

Vitek, J., Horspool, R., and Krall, A. 1997. Efficient type inclusion tests. In Proceedings of the 12th ACM Conference on Object-Oriented Programming, Languages and Applications (OOPSLA'97). ACM, New York. 142--157.

Digital Library

[77]

Vitter, J. S. and Flajolet, P. 1990. Average-case analysis of algorithms and data structures. In Algorithms and Complexity. Handbook of Theretical Computer Science, vol. 1, J. van Leeuwen, Ed. Elsevier, Amsterdam, The Netherlands. Chapter 9, 431--524.

Digital Library

[78]

Warren, H. S. 2003. Hacker's Delight. Addison-Wesley, Reading, MA.

Digital Library

[79]

Wirth, N. 1988. The programming language Oberon. Softw. Pract. Exper. 18, 7, 671--690.

Digital Library

[80]

Zendra, O., Colnet, D., and Collin, S. 1997. Efficient dynamic dispatch without virtual function tables: The SmallEiffel compiler. In Proceedings of the 12th ACM Conference on Object-Oriented Programming, Languages and Applications (OOPSLA'97). ACM, New York, 125--141.

Digital Library

[81]

Zibin, Y. and Gil, J. 2003a. Incremental algorithms for dispatching in dynamically typed languages. In Proceedings of the Programming Languages (POPL'97)). ACM, New York, 126--138.

Digital Library

[82]

Zibin, Y. and Gil, J. 2003b. Two-dimensional bi-directional object layout. In Proceedings of the 17th European Conference on Object-Oriented Programming. Lecture Notes in Computer Science, vol. 2743. Springer-Verlag, New York, 329--350.

Cited By

Zhou YWang XGuo SWen YHe J(2021)A cost-effective adaptive random testing algorithm for object-oriented software testingJournal of Intelligent & Fuzzy Systems10.3233/JIFS-189701(1-9)Online publication date: 8-Mar-2021
https://doi.org/10.3233/JIFS-189701
Chen JZhao LZhou MLiu YQin S(2020)An Approach to Determine the Optimal k-Value of K-means Clustering in Adaptive Random Testing2020 IEEE 20th International Conference on Software Quality, Reliability and Security (QRS)10.1109/QRS51102.2020.00032(160-167)Online publication date: Dec-2020
https://doi.org/10.1109/QRS51102.2020.00032
Padhye RSen KBonetta DLiu Y(2019)Efficient fail-fast dynamic subtype checkingProceedings of the 11th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages10.1145/3358504.3361229(32-37)Online publication date: 22-Oct-2019
https://dl.acm.org/doi/10.1145/3358504.3361229
Show More Cited By

Index Terms

Perfect hashing as an almost perfect subtype test

Recommendations

Implementing statically typed object-oriented programming languages

Object-oriented programming represents an original implementation issue due to its philosophy of making the program behavior depend on the dynamic type of objects. This is expressed by the late binding mechanism, aka message sending. The underlying ...
Empirical assessment of object-oriented implementations with multiple inheritance and static typing
OOPSLA '09

Object-oriented languages involve a threefold tradeoff between runtime efficiency, expressiveness (multiple inheritance), and modularity, i.e. open-world assumption (OWA). Runtime efficiency is conditioned by both the implementation technique and ...
Empirical assessment of object-oriented implementations with multiple inheritance and static typing
OOPSLA '09: Proceedings of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications

Object-oriented languages involve a threefold tradeoff between runtime efficiency, expressiveness (multiple inheritance), and modularity, i.e. open-world assumption (OWA). Runtime efficiency is conditioned by both the implementation technique and ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 30, Issue 6

October 2008

245 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/1391956

Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 October 2008

Accepted: 01 January 2008

Revised: 01 December 2006

Received: 01 December 2005

Published in TOPLAS Volume 30, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Conseil Régional Languedoc-Roussillon

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
802
Total Downloads

Downloads (Last 12 months)111
Downloads (Last 6 weeks)22

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhou YWang XGuo SWen YHe J(2021)A cost-effective adaptive random testing algorithm for object-oriented software testingJournal of Intelligent & Fuzzy Systems10.3233/JIFS-189701(1-9)Online publication date: 8-Mar-2021
https://doi.org/10.3233/JIFS-189701
Chen JZhao LZhou MLiu YQin S(2020)An Approach to Determine the Optimal k-Value of K-means Clustering in Adaptive Random Testing2020 IEEE 20th International Conference on Software Quality, Reliability and Security (QRS)10.1109/QRS51102.2020.00032(160-167)Online publication date: Dec-2020
https://doi.org/10.1109/QRS51102.2020.00032
Padhye RSen KBonetta DLiu Y(2019)Efficient fail-fast dynamic subtype checkingProceedings of the 11th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages10.1145/3358504.3361229(32-37)Online publication date: 22-Oct-2019
https://dl.acm.org/doi/10.1145/3358504.3361229
Ducournau R(2019)Coloring, a versatile technique for implementing object-oriented languagesSoftware—Practice & Experience10.1002/spe.102241:6(627-659)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1002/spe.1022
Ducournau RPrivat J(2018)Metamodeling semantics of multiple inheritanceScience of Computer Programming10.1016/j.scico.2010.10.00676:7(555-586)Online publication date: 31-Dec-2018
https://dl.acm.org/doi/10.1016/j.scico.2010.10.006
Solodkyy YDos Reis GStroustrup B(2012)Open and efficient type switch for C++ACM SIGPLAN Notices10.1145/2398857.238468647:10(963-982)Online publication date: 19-Oct-2012
https://dl.acm.org/doi/10.1145/2398857.2384686
Solodkyy YDos Reis GStroustrup BLeavens GDwyer M(2012)Open and efficient type switch for C++Proceedings of the ACM international conference on Object oriented programming systems languages and applications10.1145/2384616.2384686(963-982)Online publication date: 19-Oct-2012
https://dl.acm.org/doi/10.1145/2384616.2384686
Sonntag BColnet D(2012)Efficient compilation strategy for object-oriented languages under the closed-world assumptionSoftware: Practice and Experience10.1002/spe.217444:5(565-592)Online publication date: 26-Nov-2012
https://doi.org/10.1002/spe.2174
Ducournau R(2011)Implementing statically typed object-oriented programming languagesACM Computing Surveys10.1145/1922649.192265543:3(1-48)Online publication date: 29-Apr-2011
https://dl.acm.org/doi/10.1145/1922649.1922655
Morandat FDucournau R(2010)Empirical assessment of C++-like implementations for multiple inheritanceProceedings of the Workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems10.1145/1925801.1925803(1-5)Online publication date: 22-Jun-2010
https://dl.acm.org/doi/10.1145/1925801.1925803
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents