Efficient subtyping tests with PQ-encoding

ABSTRACT

Given a type hierarchy, a subtyping test determines whether one type is a direct or indirect descendant of another type. Such tests are a frequent operation during the execution of object-oriented programs. The implementation challenge is in a space-efficient encoding of the type hierarchy that simultaneously permits efficient subtyping tests. We present a new scheme for encoding multiple- and single-inheritance hierarchies, which, in the standard benchmark hierarchies, reduces the footprint of all previously published schemes. Our scheme is called PQ-encoding (PQE) after PQ-trees, a data structure previously used in graph theory for finding the orderings that satisfy a collection of constraints. In particular, we show that in the traditional object layout model, the extra memory requirements for single-inheritance hierarchies is zero. In the PQE subtyping, tests are constant time, and use only two comparisons. The encoding creation time of PQE also compares favorably with previous results. It is less than 1 s on all standard benchmarks on a contemporary architecture, while the average time for processing a type is less than 1 ms. However, PQE is not an incremental algorithm. Other than PQ-trees, PQE employs several novel optimization techniques. These techniques are applicable also in improving the performance of other, previously published, encoding schemes.

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: Alpern, B., Cocchi, A., and Grove, D. 2001. Dynamic type checking in Jalapeño. In Java Virtual Machine Research and Technology Symposium, J. Clifford, B. G. Lindsay, and D. Maier, Eds. USENIX, Monterey, California.
• 3: Ken Arnold , James Gosling, The Java programming language (2nd ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1998
• 4: Giuseppe D Battista , Roberto Tamassia, On-Line Planarity Testing, Brown University, Providence, RI, 1989
• 5: Giuseppe Di Battista , Roberto Tamassia, On-Line Graph Algorithms with SPQR-Trees, Proceedings of the 17th International Colloquium on Automata, Languages and Programming, p.598-611, July 16-20, 1990
• 6: Battista, G. D. and Tamassia, R. 1996. On-line maintenance of triconnected components with SPQR-trees. Algorithmica 15, 4 (Apr.), 302--318.
• 7: 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. Sys. Sci. 13, 3 (Dec.), 335--379.
• 8: Proceedings of the International Workshop on Orders, Algorithms, and Applications, July 1994
• 9: Christian Capelle, Representation of an Order as Union of Interval Orders, Proceedings of the International Workshop on Orders, Algorithms, and Applications, p.143-161, July 04-08, 1994
• 10: Yves Caseau, Efficient handling of multiple inheritance hierarchies, ACM SIGPLAN Notices, v.28 n.10, p.271-287, Oct. 1, 1993
• 11: Chambers, C. 1993. The Cecil language, specification and rationale. Tech. rep. TR-93-03-05. University of Washington, Seattle, WA.
• 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: Angelo Corsaro , Ron K. Cytron, Efficient memory-reference checks for real-time java, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 14: Brad J Cox, Object oriented programming: an evolutionary approach, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 15: Dijkstra, E. W. 1960. Recursive programming. Numer. Math. 2, 312--318.
• 16: 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
• 17: Fall, A. 1995. Heterogeneous encoding. In Proceedings of International KRUSE'95 Conference: Knowledge Use, Retrieval and Storage for Efficiency, G. Ellis, R. Levinson, A. Fall, and V. Dahl, Eds. Department of Computer Science, University of California, Santa Cruz, Santa Cruz, CA, 162--167.
• 18: 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
• 19: Robert E. Filman, Polychotomic Encoding: A Better Quasi-Optimal Bit-Vector Encoding of Tree Hierarchies, Proceedings of the 16th European Conference on Object-Oriented Programming, p.545-561, June 10-14, 2002
• 20: 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]
• 21: 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
• 22: Adele Goldberg, SMALLTALK-80: the interactive programming environment, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 23: Grafl, R. 1996. ACAO: Ein 64bit JavaVM just-in-time compiler. M.S. thesis, University of Vienna, Vienna, Austria.
• 24: Habib, M., Caseau, Y., Nourine, L., and Raynaud, O. 1999. Encoding of multiple-inheritance hierarchies and partial orders. Computat. Intell. 15, 50--62.
• 25: 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
• 26: Yoav Hollander , Matthew Morley , Amos Noy, The e Language: A Fresh Separation of Concerns, Proceedings of the Technology of Object-Oriented Languages and Systems, p.41, March 12-14, 2001
• 27: Junger, M., Leipert, S., and Mutzel, P. 1996. On computing a maximal planar subgraph using PQ-trees. Tech. rep. Informatik, Universität zu Köln, Cologne, Germany.
• 28: Junger, M., Leipert, S., and Mutzel, P. 1998. A note on computing a maximal planar subgraph using PQ-trees. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 17, 7 (Jul.), 609--612.
• 29: 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]
• 30: Krall, A. 2001. Personal communication.
• 31: Krall, A. and Grafl, R. 1997. CACAO---a 64 bit JavaVM just-in-time compiler. In PPoPP'97 Workshop on Java for Science and Engineering Computation (Las Vegas, NV), G. C. Fox and W. Li, Eds. ACM Press, New York, NY.
• 32: Krall, A., Vitek, J., and Horspool, R. N. 1997. Near optimal hierarchical encoding of types. In Proceedings of the 11th European Conference on Object-Oriented Programming (ECOOP '97, Jyväskylä, Finland). Lecture Notes in Computer Science, vol. 1241. Springer-Verlag, Berlin, Germany, 128--145.
• 33: Leipert, S. 1997. PQ-trees, an implementation as template class in C++. Tech. rep. Informatik, Universität zu Köln, Cologne, Germany.
• 34: Lempel, A., Even, S., and Cederbaum, I. 1967. An algorithm for planarity testing of graphs. In Theory of Graphs, International Symposium. Gordon and Breach, New York, NY, 215--232.
• 35: Bertrand Meyer, Eiffel: the language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 36: 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, Darmstadt, Germany.
• 37: 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
• 38: Schubert, L. K., Papalaskaris, M. A., and Taugher, J. 1983. Determining type, part, color, and time relationships. IEEE Comput (special issue on Knowledge Representation) 16, 10, 53--60.
• 39: Bjarne Stroustrup, The C++ Programming Language, Third Edition, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 40: 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]
• 41: van Emde Boas, P. 1977. Preserving order in a forest in less than logarithmic time and linear space. Inf. Process. Lett. 6, 3, 80--82.
• 42: van Emde Boas, P., Kaas, R., and Zijlstra, E. 1977. Design and implementation of an efficient priority queue. Math. Systems Theory 10, 99--127.
• 43: 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
• 44: 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]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

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: Data types and structures

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

Keywords:
Casting, PQ, PQE, encoding, hierarchy, inheritance, partially ordered sets, subtyping, type inclusion