Perfect hashing as an almost perfect subtype test

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Perfect hashing as an almost perfect subtype test

Full text

Pdf (762 KB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 30 , Issue 6 (October 2008) table of contents

Article No. 33

Year of Publication: 2008

ISSN:0164-0925

Author

Roland Ducournau

LIRMM--CNRS and Université Montpellier II, France

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 29, Downloads (12 Months): 207, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1391956.1391960 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	R. Agrawal , A. Borgida , H. V. Jagadish, Efficient management of transitive relationships in large data and knowledge bases, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.253-262, June 1989, Portland, Oregon, United States
	2	Hassan Aït-Kaci , Robert Boyer , Patrick Lincoln , Roger Nasr, Efficient implementation of lattice operations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.1, p.115-146, Jan. 1989 [doi>10.1145/59287.59293]
	3	Hamed Seiied Alavi , Seth Gilbert , Rachid Guerraoui, Extensible encoding of type hierarchies, Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 07-12, 2008, San Francisco, California, USA
	4	Bowen Alpern , Anthony Cocchi , Stephen Fink , David Grove, Efficient implementation of Java interfaces: Invokeinterface considered harmless, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.108-124, October 14-18, 2001, Tampa Bay, FL, USA
	5	Alpern, B., Cocchi, A., and Grove, D. 2001b. Dynamic type checking in Jalapeño. In Proceedings of the USENIX JVM'01.
	6	David F. Bacon , Peter F. Sweeney, Fast static analysis of C++ virtual function calls, ACM SIGPLAN Notices, v.31 n.10, p.324-341, Oct. 1996
	7	John Barnes, Programming in Ada95, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1995
	8	Yves Caseau, Efficient handling of multiple inheritance hierarchies, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.271-287, September 26-October 01, 1993, Washington, D.C., United States
	9	G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
	10	Cliff Click , John Rose, Fast subtype checking in the HotSpot JVM, Proceedings of the 2002 joint ACM-ISCOPE conference on Java Grande, p.96-107, November 03-05, 2002, Seattle, Washington, USA [doi>10.1145/583810.583821]
	11	Norman H. Cohen, Type-extension type test can be performed in constant time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.626-629, Oct. 1991 [doi>10.1145/115372.115297]
	12	Suzanne Collin , Dominique Colnet , Olivier Zendra, Type Inference for Late Binding: The SmallEiffel Compiler, Proceedings of the Joint Modular Languages Conference on Modular Programming Languages, p.67-81, March 19-21, 1997
	13	Czech, Z. J. 1998. Quasi-perfect hashing. Comput. J. 41, 416--421.
	14	Zbigniew J. Czech , George Havas , Bohdan S. Majewski, Perfect hashing, Theoretical Computer Science, v.182 n.1-2, p.1-143, Aug. 1997 [doi>10.1016/S0304-3975(96)00146-6]
	15	Dijkstra, E. W. 1960. Recursive programming. Numer. Math. 2, 312--318.
	16	R. Dixon , T. McKee , M. Vaughan , P. Schweizer, A fast method dispatcher for compiled languages with multiple inheritance, Conference proceedings on Object-oriented programming systems, languages and applications, p.211-214, October 02-06, 1989, New Orleans, Louisiana, United States
	17	Driesen, K. 1993a. Method lookup strategies in dynamically typed object-oriented programming languages. M.S. dissertation, Vrije Universiteit Brussel.
	18	Karel Driesen, Selector table indexing & sparse arrays, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.259-270, September 26-October 01, 1993, Washington, D.C., United States
	19	Karel Driesen, Efficient Polymorphic Calls, Kluwer Academic Publishers, Norwell, MA, 2001
	20	Karel Driesen , Urs Hölzle, Minimizing row displacement dispatch tables, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.141-155, October 15-19, 1995, Austin, Texas, United States
	21	Karel Driesen , Urs Hölzle , Jan Vitek, Message Dispatch on Pipelined Processors, Proceedings of the 9th European Conference on Object-Oriented Programming, p.253-282, August 07-11, 1995
	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	Roland Ducournau, "Real World" as an Argument for Covariant Specialization in Programming and Modeling, Proceedings of the Workshops on Advances in Object-Oriented Information Systems, p.3-12, September 02, 2002
	27	Ducournau, R. 2006. Coloring, a versatile technique for implementing object-oriented languages. Rapport de Recherche 06-001, LIRMM, Université Montpellier 2.
	28	Margaret A. Ellis , Bjarne Stroustrup, The annotated C++ reference manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	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	Etienne M. Gagnon , Laurie J. Hendren, SableVM: a research framework for the efficient execution of java bytecode, Proceedings of the 2001 Symposium on Java^TM Virtual Machine Research and Technology Symposium, p.3-3, April 23-24, 2001, Monterey, California
	32	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	33	Joseph (Yossi) Gil , Yoav Zibin, Efficient subtyping tests with PQ-encoding, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.5, p.819-856, September 2005 [doi>10.1145/1086642.1086643]
	34	Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
	35	David Grove , Craig Chambers, A framework for call graph construction algorithms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.6, p.685-746, November 2001 [doi>10.1145/506315.506316]
	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	Michel Habib , Lhouari Nourine, Bit-Vector Encoding for Partially Ordered Sets, Proceedings of the International Workshop on Orders, Algorithms, and Applications, p.1-12, July 04-08, 1994
	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	Samuel P. Harbison, Modula-3, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
	40	Marianne Huchard , Herve Leblanc, Computing Interfaces in Java, Proceedings of the 15th IEEE international conference on Automated software engineering, p.317, September 11-15, 2000
	41	Jensen, T. R. and Toft, B. 1995. Graph Coloring Problems. Wiley, New York.
	42	Gregor Kiczales , Jim Des Rivieres, The Art of the Metaobject Protocol, MIT Press, Cambridge, MA, 1991
	43	Raymond Klefstad , Arvind S. Krishna , Douglas C. Schmidt, Design and Performance of a Modular Portable Object Adapter for Distributed, Real-Time, and Embedded CORBA Applications, On the Move to Meaningful Internet Systems, 2002 - DOA/CoopIS/ODBASE 2002 Confederated International Conferences DOA, CoopIS and ODBASE 2002, p.549-567, October 30-November 01, 2002
	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	Stanley B. Lippman, Inside the C++ object model, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1996
	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	K. Mehlhorn , A. Tsakalidis, Data structures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	50	Bertrand Meyer, Eiffel: the language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
	51	Bertrand Meyer, Object-oriented software construction (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
	52	Jon Meyer , Troy Downing, Java virtual machine, O'Reilly & Associates, Inc., Sebastopol, CA, 1997
	53	Microsoft. 2001. C# Language specifications, v0.28. Technical report, Microsoft Corporation, Seattle, WA.
	54	Robert Morris, Scatter storage techniques, Communications of the ACM, v.11 n.1, p.38-44, Jan. 1968 [doi>10.1145/362851.362882]
	55	Hanspeter Mössenböck, Object-oriented programming in Oberon-2, Springer-Verlag New York, Inc., New York, NY, 1993
	56	S. Muthukrishnan , Martin Müller, Time and space efficient method-lookup for object-oriented programs, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.42-51, January 28-30, 1996, Atlanta, Georgia, United States
	57	Andrew C. Myers, Bidirectional object layout for separate compilation, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.124-139, October 15-19, 1995, Austin, Texas, United States
	58	Odersky, M., Spoon, L., and Venners, B. 2008. Programming in Scala, A comprehensive step-by-step guide. Artima.
	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	Jean Privat , Roland Ducournau, Link-time static analysis for efficient separate compilation of object-oriented languages, Proceedings of the 6th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, September 05-06, 2005, Lisbon, Portugal
	63	William Pugh , Grant Weddell, Two-directional record layout for multiple inheritance, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.85-91, June 1990, White Plains, New York, United States
	64	Pugh, W. and Weddell, G. 1993. On object layout for multiple inheritance. Tech. Rep. CS-93-22, University of Waterloo.
	65	Christian Queinnec, Fast and compact dispatching for dynamic object-oriented languages, Information Processing Letters, v.64 n.6, p.315-321, Dec. 29, 1997 [doi>10.1016/S0020-0190(97)00192-0]
	66	Olivier Raynaud , Eric Thierry, A Quasi Optimal Bit-Vector Encoding of Tree Hierarchies. Application to Efficient Type Inclusion Tests, Proceedings of the 15th European Conference on Object-Oriented Programming, p.165-180, June 18-22, 2001
	67	Schmidt, D. C. 1990. GPERF: A perfect hash function generator. In Proceedings of the USENIX C++ Conference. 87--102.
	68	L. K. Schubert , M. A. Papalaskaris , J. Taugher, Determining Type, Part, Color, and Time Relationships, Computer, v.16 n.10, p.53-60, October 1983 [doi>10.1109/MC.1983.1654198]
	69	Andrew Shalit, The Dylan reference manual: the definitive guide to the new object-oriented dynamic language, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1996
	70	Renzo Sprugnoli, Perfect hashing functions: a single probe retrieving method for static sets, Communications of the ACM, v.20 n.11, p.841-850, Nov. 1977 [doi>10.1145/359863.359887]
	71	Guy Steele, Common Lisp: The Language, Digital Press, Newton, MA, 1990
	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.
	74	Takhedmit, P. 2003. Coloration de classes et de propriétés : étude algorithmique et heuristique. M.S. thesis, Université Montpellier 2.
	75	Robert Endre Tarjan , Andrew Chi-Chih Yao, Storing a sparse table, Communications of the ACM, v.22 n.11, p.606-611, Nov. 1979 [doi>10.1145/359168.359175]
	76	Jan Vitek , R. Nigel Horspool , Andreas Krall, Efficient type inclusion tests, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.142-157, October 05-09, 1997, Atlanta, Georgia, United States
	77	Jeffrey Scott Vitter , Philippe Flajolet, Average-case analysis of algorithms and data structures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	78	Henry S. Warren, Hacker's Delight, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
	79	N. Wirth, The programming language Oberon, Software—Practice & Experience, v.18 n.7, p.671-690, July 1988 [doi>10.1002/spe.4380180707]
	80	Olivier Zendra , Dominique Colnet , Suzanne Collin, Efficient dynamic dispatch without virtual function tables: the SmallEiffel compiler, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.125-141, October 05-09, 1997, Atlanta, Georgia, United States
	81	Yoav Zibin , Joseph (Yossi) Gil, Incremental algorithms for dispatching in dynamically typed languages, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.126-138, January 15-17, 2003, New Orleans, Louisiana, USA
	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.