Fast algorithm for creating space efficient dispatching tables with application to multi-dispatching

ABSTRACT

The dispatching problem can be solved very efficiently in the single-inheritance~(SI) setting. In this paper we show how to extend one such solution to the multiple-inheritance~(MI) setting. This generalization comes with an increase to the space requirement by a small factor of κ This factor can be thought of as a metric of the complexity of the topology of the inheritance hierarchy.On a data set of~35 hierarchies totaling some~64 thousand types, our dispatching data structure, based on a novel type slicing technique, exhibits very significant improvements over previous dispatching techniques, not only in terms of the time for creating the underlying data structure, but also in terms of total space used.The cost is in the dispatching time, which is no longer constant, but doubly logarithmic in the number of types. Conversely, by using a simple binary search, dispatching time is logarithmic in the number of different implementations. In practice dispatching uses one indirect branch and, on average, only~2.5 binary branches.Our results also have applications to the space-efficient implementation of the more general problem of dispatching multi-methods.A by-product of our type slicing technique is an incremental algorithm for constant-time subtyping tests with favorable memory requirements. (The incremental version of the subtyping problem is to maintain the subtyping data structure in presence of additions of types to the inheritance hierarchy.)

REFERENCES

• 1: Rakesh Agrawal , Linda G. Demichiel , Bruce G. Lindsay, Static type checking of multi-methods, Conference proceedings on Object-oriented programming systems, languages, and applications, p.113-128, October 06-11, 1991, Phoenix, Arizona, United States
• 2: 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
• 3: B. Alpern, A. Cocchi, and D. Grove. Dynamic type checking in Jalapeño. In J. Clifford, B. G. Lindsay, and D. Maier, editors, Java Virtual Machine Research and Technology Symposium, Monterey, California, Apr. 2001. USENIX.
• 4: Eric Amiel , Olivier Gruber , Eric Simon, Optimizing multi-method dispatch using compressed dispatch tables, Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applications, p.244-258, October 23-28, 1994, Portland, Oregon, United States
• 5: Ken Arnold , James Gosling, The Java programming language (2nd ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1998
• 6: D. G. Bobrow, L. G. DeMichiel, R. P. Gabriel, S. E. Keene, G. Kiczales, and D. A. Moon. Common Lisp object system specification. X3J13 Document 88-002R, June 1988.
• 7: Daniel G. Bobrow , Kenneth Kahn , Gregor Kiczales , Larry Masinter , Mark Stefik , Frank Zdybel, CommonLoops: merging Lisp and object-oriented programming, Conference proceedings on Object-oriented programming systems, languages and applications, p.17-29, September 29-October 02, 1986, Portland, Oregon, United States
• 8: K. S. Booth and G. S. Leuker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Sys. Sci., 13(3):335--379, Dec. 1976.
• 9: C. Chambers. The Cecil language, specification and rationale. Technical Report TR-93-03-05, University of Washington, Seattle, 1993.
• 10: Craig Chambers , Weimin Chen, Efficient multiple and predicated dispatching, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.238-255, November 01-05, 1999, Denver, Colorado, United States
• 11: Weimin Chen , Volker Turau , Wolfgang Klas, Efficient Dynamic Look-Up Strategy for Multi-Methods, Proceedings of the 8th European Conference on Object-Oriented Programming, p.408-431, July 04-08, 1994
• 12: 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]
• 13: T. Cohen and J. Y. Gil. Self-calibration of metrics of Java methods. In Proceedings of the International Conference on Technology of Object-Oriented Languages and Systems, pages 94--106, Sydney, Australia, Nov. 20-23 2000. TOOLS Pacific 2000, Prentice-Hall.
• 14: T. J. Conroy and E. Pelegri-Llopart. An Assessment of Method-Lookup Caches for Smalltalk-80 Implementations. Addison-Wesley, Menlo Park,CA 94025, 1983.
• 15: Brad J Cox, Object oriented programming: an evolutionary approach, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 16: L. Peter Deutsch , Allan M. Schiffman, Efficient implementation of the smalltalk-80 system, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.297-302, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800542]
• 17: Paul F. Dietz, Maintaining order in a linked list, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.122-127, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802184]
• 18: P. Dietz , D. Sleator, Two algorithms for maintaining order in a list, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.365-372, January 1987, New York, New York, United States [doi>10.1145/28395.28434]
• 19: Martin Dietzfelbinger , Anna Karlin , Kurt Mehlhorn , Friedhelm MeyerAuf Der, Dynamic Perfect Hashing: Upper and Lower Bounds, SIAM Journal on Computing, v.23 n.4, p.738-761, Aug. 1994 [doi>10.1137/S0097539791194094]
• 20: 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
• 21: 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
• 22: Karel Driesen, Software and Hardware Techniques for Efficient Polymorphic Calls, University of California at Santa Barbara, Santa Barbara, CA, 1999
• 23: 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
• 24: Karel Driesen , Urs Hölzle, The direct cost of virtual function calls in C++, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.306-323, October 06-10, 1996, San Jose, California, United States
• 25: Karel Driesen , Urs Holzle , Jan Vitek, Message Dispatch on Modern Computer Architectures, University of California at Santa Barbara, Santa Barbara, CA, 1995
• 26: 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
• 27: E. Dujardin. Efficient dispatch of multimethods in constant time using dispatch trees. Technical Report RR-2892, Inria, Institut National de Recherche en Informatique et en Automatique, 1996.
• 28: Eric Dujardin , Eric Amiel , Eric Simon, Fast algorithms for compressed multimethod dispatch table generation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.1, p.116-165, Jan. 1998 [doi>10.1145/271510.271521]
• 29: Natalie Eckel , Joseph Gil, Empirical Study of Object-Layout Strategies and Optimization Techniques, Proceedings of the 14th European Conference on Object-Oriented Programming, p.394-421, June 12-16, 2000
• 30: ECOOP'91. Proceedings of the 5th European Conference on Object-Oriented Programming, number 512 in Lecture Notes in Computer Science, Geneva, Switzerland, July15--19 1991. Springer Verlag.
• 31: ECOOP'94. Proceedings of the 8th European Conference on Object-Oriented Programming, number 821 in Lecture Notes in Computer Science, Bologna, Italy, July 4--8 1994. Springer Verlag.
• 32: ECOOP'99. Proceedings of the 13th European Conference on Object-Oriented Programming, number 1628 in Lecture Notes in Computer Science, Lisbon, Portugal, June 14--18 1999. Springer Verlag.
• 33: Margaret A. Ellis , Bjarne Stroustrup, The annotated C++ reference manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 34: Andrew Fall, Sparse Term Encoding for Dynamic Taxonomies, Proceedings of the 4th International Conference on Conceptual Structures: Knowledge Representation as Interlingua, p.277-292, August 19-22, 1996
• 35: Paolo Ferragina , S. Muthukrishnan, Efficient Dynamic Method-Lookup for Object Oriented Languages (Extended Abstract), Proceedings of the Fourth Annual European Symposium on Algorithms, p.107-120, September 25-27, 1996
• 36: Paolo Ferragina , S. Muthukrishnan , Mark de Berg, Multi-method dispatching: a geometric approach with applications to string matching problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.483-491, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301378]
• 37: Harold N. Gabow , Jon Louis Bentley , Robert E. Tarjan, Scaling and related techniques for geometry problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.135-143, December 1984 [doi>10.1145/800057.808675]
• 38: Joseph Gil , Alon Itai, The Complexity of Type Analysis of Object Oriented Programs, Proceedings of the 12th European Conference on Object-Oriented Programming, p.601-634, July 20-24, 1998
• 39: Peter F. Sweeney , Joseph (Yossi) Gil, Space and time-efficient memory layout for multiple inheritance, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.256-275, November 01-05, 1999, Denver, Colorado, United States
• 40: Adele Goldberg, SMALLTALK-80: the interactive programming environment, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 41: 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
• 42: W. Holst, D. Szafron, Y. Leontiev, and C. Pang. Multi-method dispatch using single-receiver projections. Technical Report TR-98-03, University of Alberta, Edmonton, Alberta, Canada, 1998.
• 43: Urs Hölzle , Craig Chambers , David Ungar, Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches, Proceedings of the European Conference on Object-Oriented Programming, p.21-38, July 15-19, 1991
• 44: 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]
• 45: Gregor Kiczales , Luis Rodriguez, Efficient method dispatch in PCL, Proceedings of the 1990 ACM conference on LISP and functional programming, p.99-105, June 27-29, 1990, Nice, France [doi>10.1145/91556.91600]
• 46: Eric Kidd, Efficient Compression of Generic Function Dispatch Tables, Dartmouth College, Hanover, NH, 2001
• 47: 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
• 48: A. Krall, J. Vitek, and R. N. Horspool. Near optimal hierarchical encoding of types. In Proceedings of the 11th European Conference on Object-Oriented Programming, number 1241 in Lecture Notes in Computer Science, pages 128--145, Jyväskylä, Finland, June 9-13 1997. ECOOP'97, Springer Verlag.
• 49: Bertrand Meyer, Eiffel: the language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 50: Warwick B. Mugridge , John Hamer , John G. Hosking, Multi-Methods in a Statically-Typed Programming Language, Proceedings of the European Conference on Object-Oriented Programming, p.307-324, July 15-19, 1991
• 51: 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
• 52: Mayur Naik , Rajeev Kumar, Efficient message dispatch in object-oriented systems, ACM SIGPLAN Notices, v.35 n.3, p.49-58, March 2000 [doi>10.1145/351159.351174]
• 53: OOPSLA'01. Proceedings of the 16th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications, Tampa Bay, Florida, Oct. 14--18 2001. ACM SIGPLAN Notices 36(10) Oct. 2001.
• 54: OOPSLA'93. Proceedings of the 8th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications, Washington, DC, USA, Sept. 26 - Oct. 1 1993. ACM SIGPLAN Notices 28(10) Oct. 1993.
• 55: OOPSLA'97. Proceedings of the 12th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications, Atlanta, Georgia, Oct. 5-9 1997. ACM SIGPLAN Notices 32(10) Oct. 1997.
• 56: OOPSLA'99. Proceedings of the 14th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications, Denver, Colorado, Nov.1--5 1999. ACM SIGPLAN Notices 34(10) Nov. 1999.
• 57: Candy Pang , Wade Holst , Yuri Leontiev , Duane Szafron, Multi-method Dispatch Using Multiple Row Displacement, Proceedings of the 13th European Conference on Object-Oriented Programming, p.304-328, June 14-18, 1999
• 58: 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
• 59: Pascal André , Jean-Claude Royer, Optimizing method search with lookup caches and incremental coloring, conference proceedings on Object-oriented programming systems, languages, and applications, p.110-126, October 18-22, 1992, Vancouver, British Columbia, Canada
• 60: 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
• 61: Bjarne Stroustrup, The C++ Programming Language, Third Edition, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 62: M. F. van Bommel , T. J. Beck, Incremental encoding of multiple inheritance hierarchies, Proceedings of the eighth international conference on Information and knowledge management, p.507-513, November 02-06, 1999, Kansas City, Missouri, United States [doi>10.1145/319950.320057]
• 63: P. van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters, 6(3):80--82, 1977.
• 64: P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Math. Systems Theory, 10:99--127, 1977.
• 65: J. Vitek. Compact dispatch tables for dynamically typed programming languages. Master's thesis, University of Victoria, 1995.
• 66: Jan Vitek , R. Nigel Horspool, Taming Message Passing: Efficient Method Look-Up for Dynamically Typed Languages, Proceedings of the 8th European Conference on Object-Oriented Programming, p.432-449, July 04-08, 1994
• 67: Jan Vitek , R. Nigel Horspool, Compact Dispatch Tables for Dynamically Typed Object Oriented Languages, Proceedings of the 6th International Conference on Compiler Construction, p.309-325, April 24-26, 1996
• 68: Dan E. Willard, New trie data structures which support very fast search operations, Journal of Computer and System Sciences, v.28 n.3, p.379-394, June 1984 [doi>10.1016/0022-0000(84)90020-5]
• 69: 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
• 70: Y. Zibin and J. Y. Gil. Theory and practice of incremental subtyping tests and message dispatching. http://www.cs.technion.ac.il/~zyoav. Manuscript.
• 71: Yoav Zibin , Joseph Yossi Gil, Efficient subtyping tests with PQ-encoding, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.96-107, October 14-18, 2001, Tampa Bay, FL, USA