Efficient subtyping tests with PQ-encoding

ABSTRACT

Subtyping test, i.e., determining whether one type is a subtype of another, are a frequent operation during the execution of object-oriented programs. The challenge is in encoding the hierarchy in a small space, while simulataneously making sure that subtyping tests have efficient implmentation. We present a new scheme for encoding multiple and single inheritance hierarchies, which, in the standardized hierarchies, reduces the footprint of all previsously published schemes. The scheme is called PQ-encoding 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 requirement for single inheritance hierarchies is zero. In the PQ-encoding subtyping tests are constant time, and use only two comparisons. Other than PQ-trees, PQ-encoding uses several novel optimization techniques. These techniques are applicable also in improving the performance of otehr, 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: Ken Arnold , James Gosling, The Java programming language (2nd ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1998
• 3: Giuseppe D Battista , Roberto Tamassia, On-Line Planarity Testing, Brown University, Providence, RI, 1989
• 4: Giuseppe Di Battista , Roberto Tamassia, On-line graph algorithms with SPQR-trees, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.598-611, July 1990, Warwick University, England
• 5: G. D. Battista and R. Tamassia. On-line maintenance of triconnected components with SPQR-trees. Algorithmica, 15(4):302-318, Apr. 1996.
• 6: 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.
• 7: 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
• 8: L. Cardelli , J. Donahue , M. Jordan , B. Kalsow , G. Nelson, The Modula–3 type system, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.202-212, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75295]
• 9: Yves Caseau, Efficient handling of multiple inheritance hierarchies, ACM SIGPLAN Notices, v.28 n.10, p.271-287, Oct. 1, 1993
• 10: C. Chambers. The Cecil language, specification and rationale. Technical report, University of Washington, Seattle, 1993.
• 11: 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]
• 12: Brad J Cox, Object oriented programming: an evolutionary approach, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 13: E. W. Dijkstra. Recursive programming. Numerische Mathematik, 2:312-318, 1960.
• 14: 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
• 15: A. Fall. Heterogeneous encoding. In Proceedings of International KRUSE'95 Conference : Knowledge Use, Retrieval and Storage for Efficiency, pages 162-167, Aug. 1995.
• 16: 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
• 17: 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
• 18: Adele Goldberg, SMALLTALK-80: the interactive programming environment, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 19: R. Grafl. CACAO: Ein 64bit JavaVM just-in-time compiler. Master's thesis, University of Vienna, 1996.
• 20: 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
• 21: 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]
• 22: M. Junger, S. Leipert, and P. Mutzel. On computing a maximal planar subgraph using PQ-trees. Technical report, Informatik, Universit~t zu K~ln, 1996.
• 23: M. Junger, S. Leipert, and P. Mutzel. A note on computing a maximal planar subgraph using PQ-trees. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 17(7), 1998.
• 24: A. Krall and R. Grafl. CACAO - a 64 bit JavaVM just-in-time compiler. In G. C. Fox and W. Li, editors, PPoPP'97 Workshop on Java for Science and Engineering Computation, Las Vegas, June 1997.
• 25: 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
• 26: A. Krall, J. Vitek, and R. N. Horspool. Near optimal hierarchical encoding of types. In M. Aksit and S. Matsuoka, editors, Proceedings of the 11th European Conference on Object-Oriented Programming, number 1241 in Lecture Notes in Computer Science, pages 128-145, Jyvaskyla, Finland, June 9-13 1997. ECOOP'97, Springer Verlag.
• 27: S. Leipert. PQ-trees, an implementation as template class in C++. Technical report, Informatik, Universitat zu Koln, 1997.
• 28: L. N. M. Habib, Y. Caseau and O. Raynaud. Encoding of multiple inheritance hierarchie and partial orders. In Computational Intelligence, volume 15, pages 50-62, 1999.
• 29: Bertrand Meyer, Eiffel: the language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 30: 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
• 31: M. A. Schubert, P. L.K., and J. Taugher. Determining type, part, colour, and time relationships. Computer, 16 (special issue on Knowledge Representation):53-60, Oct. 1983.
• 32: Bjarne Stroustrup, The C++ programming language (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 33: 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]

INDEX TERMS

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

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

General Terms:
Algorithms