Incremental algorithms for dispatching in dynamically typed languages

ABSTRACT

A fundamental problem in the implementation of object-oriented languages is that of a frugal dispatching data structure, i.e., support for quick response to dispatching queries combined with compact representation of the type hierarchy and the method families. Previous theoretical algorithms tend to be impractical due to their complexity and large hidden constant. In contrast, successful practical heuristics, including Vitek and Horspool's compact dispatch tables (CT) [16] designed for dynamically typed languages, lack theoretical support. In subjecting CT to theoretical analysis, we are not only able to improve and generalize it, but also provide the first non-trivial bounds on the performance of such a heuristic.Let n,ml denote the total number of types, messages, and different method implementations, respectively. Then, the dispatching matrix, whose size isnm, can be compressed by a factor of at most ι ≡ (nm)/l. Our main variant to CT achieves a compression factor of ½ √ι. More generally, we describe a sequence of algorithms CT1, CT2, CT3,..., where CTd achieves compression by a factor of (at least) ¹overdι^1—1/d, while using d memory dereferencing operations during dispatch. This tradeoff represents the first bounds on the compression ratio of constant-time dispatching algorithms.A generalization of these algorithms to a multiple-inheritance setting, increases the space by a factor of κ^1-1/d, where κ is a metric of the complexity of the topology of the inheritance hierarchy, which (as indicated by our measurements) is typically small. The most important generalization is an incremental variant of the CTd scheme for a single-inheritance setting. This variant uses at most twice the space of CTd, and its time of inserting a new type into the hierarchy is optimal. We therefore obtain algorithms for efficient management of dispatching in dynamic-typing, dynamic-loading languages, such as Smalltalk and even the Java invokeinterface instruction.

REFERENCES

• 1: Ken Arnold , James Gosling , David Holmes, The Java Programming Language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 2: 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]
• 3: 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]
• 4: 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
• 5: 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
• 6: 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
• 7: 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
• 8: Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
• 9: 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
• 10: 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
• 11: 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
• 12: 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
• 13: 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]
• 14: Bjarne Stroustrup, The design and evolution of C++, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1995
• 15: 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
• 16: 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
• 17: 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
• 18: Yoav Zibin , Joseph Yossi Gil, Fast algorithm for creating space efficient dispatching tables with application to multi-dispatching, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.5 Object-oriented Programming
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Inheritance

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE

General Terms:
Algorithms, Design, Measurement, Performance, Theory

Keywords:
CT, dispatch, dynamic-typing, hierarchy, incremental, message