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. R. Agrawal, L. Demichiel, and B. Lindsay. Static type checking of multi-methods. In Proceedings of the Annual Conference on Object-Oriented Programming Systems, Languages, and Applications, Phoenix, Arizona, USA, Oct. 6-11 1991. OOPSLA'91, ACM SIGPLAN Notices 26(11) Nov. 1991.]]
2. B. Alpern, A. Cocchi, S. Fink, D. Grove, and D. Lieber. Efficient implementation of Java interfaces: invokeinterface considered harmless. In OOPSLA'01.]]
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. E. Amiel, O. Gruber, and E. Simon. Optimizing multi-method dispatch using compressed dispatch tables. In Proceedings of the 9th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 244--258, Portland, Oregon, USA, Oct. 23-27 1994. OOPSLA'94, ACM SIGPLAN Notices 29(10) Oct. 1994.]]
5. K. Arnold and J. Gosling. The Java Programming Language. The Java Series. Addison-Wesley, Reading, Massachusetts, 1996.]]
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. D. G. Bobrow, K. Kahn, G. Kiczales, L. Masinter, M. Stefik, and F. Zdybel. CommonLoops: Merging Lisp and object-oriented programming. In Proceedings of the 1st Annual Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 17--29, Portland, Oregon, USA, Sept. 29 - Oct. 2 1986. OOPSLA'86, ACM SIGPLAN Notices 21(11) Nov. 1986.]]
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. C. Chambers and W. Chen. Efficient multiple and predicate dispatching. In OOPSLA'99, pages 238--255.]]
11. W. Chen, V. Turau, and W. Klas. Efficient dynamic look up strategy for multi-methods. In Proceedings of the 8th European Conference on Object-Oriented Programming ECOOP:94, pages 408--431.]]
12. N. H. Cohen. Type-extension tests can be performed in constant time. ACM Trans. Prog. Lang. Syst., 13:626--629, 1991.]]
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. B. J. Cox. Object-Oriented Programming - An Evolutionary Approach. Addison-Wesley, Reading, Massachusetts, 1986.]]
16. P. Deutsch and A. Schiffman. Efficient implementation of the Smalltalk-80 system. In 11th Symposium on Principles of Programming Languages, POPL'84, pages 297--302, Salt Lake City, Utah, Jan. 1984. ACM SIGPLAN --- SIGACT, ACM Press.]]
17. P. F. Dietz. Maintaining order in a linked list. In Proc. of the 14th Ann. ACM Symp. on Theory of Computing, pages 122--127, San Francisco, California, United States, 1982. ACM Press.]]
18. P. F. Dietz and D. D. Sleator. Two algorithms for maintaining order in a list. In Proc. of the 19th Ann. ACM Symp. on Theory of Computing, pages 365--372, New York, New York, United States, 1987. ACM Press.]]
19. M. Dietzfelbinger, A. R. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, and R. E. Tarjan. Dynamic perfect hashing: Upper and lower bounds. SIAM J. Comput., 23(4):738--761, Aug. 1994.]]
20. R. Dixon, T. McKee, M. Vaughan, and P. Schweizer. A fast method dispatcher for compiled languages with multiple inheritance. In Proceedings of the 4th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 211--214, New Orleans, Louisiana, Oct. 1--6 1989. OOPSLA'89, ACM SIGPLAN Notices 24(10) Oct. 1989.]]
21. K. Driesen. Selector table indexing & sparse arrays. In OOPSLA'93, pages 259--270.]]
22. K. Driesen. Software and hardware techniques for efficient polymorphic calls. Technical Report TRCS99-24, University of California, Santa Barbara. Computer Science., July 15, 1999.]]
23. K. Driesen and U. Hölzle. Minimizing row displacement dispatch tables. In Proceedings of the 10th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 141--155, Austin, Texas, USA, Oct. 15--19 1995. OOPSLA'95, ACM SIGPLAN Notices 30(10) Oct. 1995.]]
24. K. Driesen and U. Hölzle. The direct cost of virtual functions calls in C++. In Proceedings of the 11th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 306--323, San Jose, California, Oct. 6--10 1996. OOPSLA'96, ACM SIGPLAN Notices 31(10) Oct. 1996.]]
25. K. Driesen, U. Hölzle, and J. Vitek. Message dispatch on modern computer architectures. Technical Report TRCS94-20, University of California, Santa Barbara. Computer Science., Feb. 9, 1995.]]
26. K. Driesen, U. Hölzle, and J. Vitek. Message dispatch on pipelined processors. In Proceedings of the 9th European Conference on Object-Oriented Programming, number 952 in Lecture Notes in Computer Science, pages 253--282, Aarhus, Denmark, Aug. 7--11 1995. ECOOP'95, Springer Verlag.]]
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. E. Dujardin, E. Amiel, and E. Simon. Fast algorithms for compressed multimethod dispatch table generation. ACM Trans. Prog. Lang. Syst., 20(1):116--165, Jan. 1998.]]
29. N. Eckel and J. Y. Gil. Empirical study of object-layout strategies and optimization techniques. In Proceedings of the 14th European Conference on Object-Oriented Programming, number 1850 in Lecture Notes in Computer Science, pages 394--421, Sophia Antipolis and Cannes, France, June 12--16 2000. ECOOP 2000, Springer Verlag.]]
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. Ellis and B. Stroustrup. The Annotated C++ Reference Manual. Addison-Wesley, Reading, Massachusetts, Jan. 1994.]]
34. A. Fall. Sparse term encoding for dynamic taxonomies. In P. W. Eklund, G. Ellis, and G. Mann, editors, Proceedings of the Fourth International Conference on Conceptual Structures (ICCS-96): Knowlegde Representation as Interlingua, volume 1115 of LNAI, pages 277--292, Berlin, Aug. 19--22 1996. Springer.]]
35. P. Ferragina and S. Muthukrishnan. Efficient dynamic method-lookup for object oriented languages. In J. Díaz and M. Serna, editors, Algorithms---ESA '96, Fourth Annual European Symposium, volume 1136 of Lecture Notes in Computer Science, pages 107--120, Barcelona, Spain, 25--27 Sept. 1996. Springer.]]
36. P. Ferragina, S. Muthukrishnan, and M. de Berg. Multi-method dispatching: A geometric approach with applications to string matching problems. In Proc. of the 31st Ann. ACM Symp. on Theory of Computing, pages 483--491, Atlanta, Georgia, United States, 1999. ACM Press.]]
37. H. N. Gabow, J. L. Bentley, and R. E. Tarjan. Scaling and related techniques for geometry problems. In Proc. of the 16th Ann. ACM Symp. on Theory of Computing, pages 135--143, Washington, DC, United States, 1984. ACM Press.]]
38. J. Gil and A. Itai. The complexity of type analysis of Object Oriented programs. In Proceedings of the 12th European Conference on Object-Oriented Programming, number 1445 in Lecture Notes in Computer Science, pages 601--634, Brussels, Belgium, July 20--24 1998. ECOOP'98, Springer Verlag.]]
39. J. Y. Gil and P. Sweeney. Space- and time-efficient memory layout for multiple inheritance. In OOPSLA'99, pages 256--275.]]
40. A. Goldberg. Smalltalk-80: The Interactive Programming Environment. Addison-Wesley, Reading, Massachusetts, 1984.]]
41. M. Habib and L. Nourine. Bit-vector encoding for partially ordered sets. In V. Bouchitte and M. Morvan, editors, International Workshop on Orders, Algorithms, and Applications (ORDAL'94), number 831 in Lecture Notes in Computer Science, pages 1--12, Lyon, France, July 1994. Springer Verlag.]]
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. U. Hölzle, C. Chambers, and D. Ungar. Optimizing dynamically-typed object-oriented languages with polymorphic inline caches. In Proceedings of the 5th European Conference on Object-Oriented Programming ECOOP:91.]]
44. H. Kaci, R. Boyer, P. Lincoln, and R. Nasr. Efficient implementation of lattice operation. ACM Trans. Prog. Lang. Syst., 11:115--146, 1989.]]
45. G. Kiczales and L. Rodriguez. Efficient method dispatch in PCL. In 1990 ACM Conference on Lisp and Functional Programming, pages 99--105, Nice, France, June 1990. ACM, ACM Press.]]
46. E. Kidd. Efficient Compression of Generic Function Dispatch Tables. Technical Report TR2001-404, Dartmouth College, Computer Science, Hanover, NH, June 2001.]]
47. A. Krall, J. Vitek, and R. N. Horspool. Efficient type inclusion tests. In OOPSLA'97, pages 142--157.]]
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. B. Meyer. EIFFEL the Language. Object-Oriented Series. Prentice-Hall, Hemel Hempstead, Hertfordshire, UK, 1992.]]
50. W. Mugridge, J. Hamer, and J. Hosking. Multi-methods in a statically-typed programming languages. In Proceedings of the 5th European Conference on Object-Oriented Programming ECOOP:91.]]
51. S. Muthukrishnan and M. Müller. Time and space efficient method-lookup for object-oriented programs. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 42--51, New York/Philadelphia, Jan. 28--30 1996. ACM/SIAM.]]
52. M. Naik and R. Kumar. Efficient message dispatch in object-oriented systems. ACM SIG-PLAN Notices, 35(3):49--58, Mar. 2000.]]
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. C. Pang, W. Holst, Y. Leontiev, and D. Szaforon. Multi-method dispatch using multiple row displacement. In Pang, et al. ECOOP:99, pages 304--328.]]
58. O. Raynaud and E. Thierry. A quasi optimal bit-vector encoding of tree hierarchies. application to efficient type inclusion tests. In J. Knudsen, editor, Proceedings of the 15th European Conference on Object-Oriented Programming, number 1850 in Lecture Notes in Computer Science, pages 165--181, Budapest, Hungary, June 12--16 2001. ECOOP 2001, Springer Verlag.]]
59. A. Royer. Optimizing Method Search with Lookup Caches and Incremental Coloring. In Proceedings of the 7th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 110--126, Vancouver, British Columbia, Canada, Oct.18--22 1992. OOPSLA'92, ACM SIGPLAN Notices 27(10) Oct. 1992.]]
60. A. Shalit. The Dylan Reference Manual: The Definitive Guide to the New Object-Oriented Dynamic Language. Addison-Wesley, Reading, Mass., 1997.]]
61. B. Stroustrup. The C++ Programming Language. Addison-Wesley, Reading, Massachusetts, 3rd edition, 1997.]]
62. M. F. van Bommel and T. J. Beck. Incremental encoding of multiple inheritance hierarchies. In Proceedings of the 8th International Conference on Information Knowledgement (CIKM-99), pages 507--513, N.Y., Nov. 2--6 2000. ACM Press.]]
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. J. Vitek and R. N. Horspool. Taming message passing: Efficient method lookup for dynamically typed object-oriented languages. In Proceedings of the 8th European Conference on Object-Oriented Programming ECOOP:94.]]
67. J. Vitek and R. N. Horspool. Compact dispatch tables for dynamically typed object oriented languages. In T. Gyimothy, editor, Compiler Construction, 6th International Conference, volume 1060 of Lecture Notes in Computer Science, pages 309--325, Linköping, Sweden, 24--26 Apr. 1996. Springer.]]
68. D. E. Willard. New trie data structures which support very fast search operations. J. Comput. Sys. Sci., 28:379--394, 1984.]]
69. O. Zendra, C. Colnet, and S. Collin. Efficient dynamic dispatch without virtual function tables: The SmallEiffel compiler. In OOPSLA'97 OOPSLA:97, pages 125--141.]]
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. Y. Zibin and J. Y. Gil. Efficient subtyping tests with PQ-encoding. In OOPSLA'01, pages 96--107.]]