Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

A fundamental problem in the implementation of object-oriented languages is that of a frugal implementation of dynamic dispatching, that is, a small footprint data structure that supports quick response to runtime dispatching queries of the following format: which method should be executed in response to a certain message sent to a given object. Previous theoretical algorithms for this problem tend to be impractical due to their conceptual complexity and large hidden constants. In contrast, successful practical heuristics lack theoretical support.

The contribution of this article is in a novel type slicing technique, which results in two dispatching schemes: TS and CT_d. We make the case for these schemes both practically and theoretically. The empirical findings on a corpus of 35 hierarchies totaling some 64 thousand types from eight different languages, demonstrate improvement over previous results in terms of the space required for the representation, and the time required for computing it.

The theoretical analysis is with respect to ι, the best possible compression factor of the dispatching matrix. The results are expressed as a function of a parameter κ, which can be thought of as a metric of the complexity of the topology of a multiple inheritance hierarchy. In single inheritance hierarchies κ = 1, but although κ can be in the order of the size of the hierarchy, it is typically a small constant in actual use of inheritance; in our corpus, the median value of κ is 5, while its average is 6.4.

The TS scheme generalizes the famous interval containment technique to multiple inheritance. TS achieves a compression factor of ι/κ, that is, our generalization comes with an increase to the space requirement by a small factor of κ. The pay is in the dispatching time, which is no longer constant as in a naive matrix implementation, but logarithmic in the number of different method implementations. In practice, dispatching uses one indirect branch and, on average, only 2.5 binary branches.

The CT schemes are a sequence of algorithms CT₁, CT₂, CT₃, …, where CT_d uses d memory dereferencing operations during dispatch, and achieves a compression factor of 1/dι^1−1/d in a single inheritance setting. A generalization of these algorithms to a multiple inheritance setting, increases the space by a factor of (2κ)^1−1/d. This trade-off represents the first bounds on the compression ratio of constant-time dispatching algorithms. We also present an incremental variant of the CT_d suited for languages such as Java.

REFERENCES

• 1: 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
• 2: Ken Arnold , James Gosling , David Holmes, The Java Programming Language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 3: Bobrow, D. G., DeMichiel, L. G., Gabriel, R. P., Keene, S. E., Kiczales, G., and Moon, D. A. 1988. Common LISP object system specification. X3J13 Document 88-002R.
• 4: 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
• 5: Booth, K. S. and Leuker, G. S. 1976. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13, 3 (Dec.), 335--379.
• 6: Chambers, C. 1993. The Cecil language, specification and rationale. Tech. Rep. TR-93-03-05, University of Washington, Seattle, WA.
• 7: Craig Chambers , Weimin Chen, Efficient multiple and predicated dispatching, ACM SIGPLAN Notices, v.34 n.10, p.238-255, Oct. 1999
• 8: Cohen, T. and Gil, J. 2000. Self-calibration of metrics of Java methods. In Proceedings of the 37th International Conference on Technology of Object-Oriented Languages and Systems (TOOLS'00 Pacific) (Sydney, Australia). Prentice-Hall, Englewood Cliffs, NJ, 94--106.
• 9: Conroy, T. J. and Pelegri-Llopart, E. 1983. An assessment of method-lookup caches for Smalltalk-80 implementations. In Smalltalk-80: Bits of History, Words of Advice. Addison-Wesley, Reading, MA.
• 10: Brad J Cox, Object oriented programming: an evolutionary approach, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 11: 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]
• 12: P. Dietz , D. Sleator, Two algorithms for maintaining order in a list, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.365-372, January 1987, New York, New York, United States [doi>10.1145/28395.28434]
• 13: Martin Dietzfelbinger , Anna Karlin , Kurt Mehlhorn , Friedhelm Meyer auf der Heide , Hans Rohnert , Robert E. Tarjan, Dynamic Perfect Hashing: Upper and Lower Bounds, SIAM Journal on Computing, v.23 n.4, p.738-761, Aug. 1994 [doi>10.1137/S0097539791194094]
• 14: 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
• 15: 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
• 16: Karel Driesen, Software and Hardware Techniques for Efficient Polymorphic Calls, University of California at Santa Barbara, Santa Barbara, CA, 1999
• 17: 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
• 18: Karel Driesen , Urs Hölzle, The direct cost of virtual function calls in C++, ACM SIGPLAN Notices, v.31 n.10, p.306-323, Oct. 1996
• 19: Karel Driesen , Urs Holzle , Jan Vitek, Message Dispatch on Modern Computer Architectures, University of California at Santa Barbara, Santa Barbara, CA, 1995
• 20: 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
• 21: Dujardin, E. 1996. Efficient dispatch of multimethods in constant time using dispatch trees. Tech. Rep. RR-2892. Inria, Institut National de Recherche en Informatique et en Automatique.
• 22: 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]
• 23: 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
• 24: Margaret A. Ellis , Bjarne Stroustrup, The annotated C++ reference manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 25: 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
• 26: 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]
• 27: 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
• 28: 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
• 29: Adele Goldberg, SMALLTALK-80: the interactive programming environment, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 30: Holst, W., Szafron, D., Leontiev, Y., and Pang, C. 1998. Multi-method dispatch using single-receiver projections. Tech. Rep. TR-98-03, University of Alberta, Edmonton, Alb., Canada.
• 31: 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
• 32: ISE. 1997. ISE EIFFEL The Language Reference. ISE, Santa Barbara, CA.
• 33: 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]
• 34: 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
• 35: 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]
• 36: 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
• 37: 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
• 38: 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
• 39: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
• 40: Bjarne Stroustrup, The design and evolution of C++, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1995
• 41: Bjarne Stroustrup, The C++ Programming Language, Third Edition, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 42: van Emde Boas, P. E. 1977. Preserving order in a forest in less than logarithmic time and linear space. Inf. Proc. Lett. 6, 3, 80--82.
• 43: van Emde Boas, P. E., Kaas, R., and Zijlstra, E. 1977. Design and implementation of an efficient priority queue. Math. Syst. Theory 10, 99--127.
• 44: Vitek, J. 1995. Compact dispatch tables for dynamically typed programming languages. M.S. thesis, University of Victoria, Victoria, BC, Canada.
• 45: 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
• 46: 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
• 47: 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]
• 48: 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
• 49: Yoav Zibin , Joseph Yossi Gil, Efficient subtyping tests with PQ-encoding, ACM SIGPLAN Notices, v.36 n.11, p.96-107, 11/01/2001
• 50: Yoav Zibin , Joseph Yossi Gil, Fast algorithm for creating space efficient dispatching tables with application to multi-dispatching, ACM SIGPLAN Notices, v.37 n.11, November 2002
• 51: 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

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.5 Object-oriented Programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

Keywords:
CT (compact dispatch tables), dispatch, dynamic-typing, hierarchy, incremental, message, subtyping, type slicing