Two-dimensional bidirectional object layout

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Two-dimensional bidirectional object layout

Full text

Pdf (617 KB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 30 , Issue 5 (August 2008) table of contents

Article No. 28

Year of Publication: 2008

ISSN:0164-0925

Authors

Joseph (Yossi) Gil	Technion—Israel Institute of Technology
William Pugh	Dept. of Computer Science, University of Maryland, College Park
Grant E. Weddell	University of Waterloo
Yoav Zibin	Technion—Israel Institute of Technology

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 41, Downloads (12 Months): 108, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1387673.1387677 What is a DOI?

ABSTRACT

Object layout schemes used in C++ and other languages rely on (sometimes numerous) compiler generated fields. We describe a language-independent object layout scheme, which is space optimal, that is, objects are contiguous, and contain no compiler generated fields other than a single type identifier. As in C++ and other multiple inheritance languages such as CECIL and DYLAN, the new scheme sometimes requires extra levels of indirection to access some of the fields. Using a data set of 28 hierarchies, totaling almost 50,000 types, we show that this scheme improves field access efficiency over standard implementations, and competes favorably with (the non-space-optimal) highly optimized C++ specific implementations. The benchmark includes an analytical model for computing the frequency of indirections in a sequence of field access operations. Our layout scheme relies on whole-program analysis, which requires about 10 microseconds per type on a contemporary architecture (Pentium III, 900Mhz, 256MB machine), even in very large hierarchies. We also present a layout scheme for separate compilation using the user-annotation of virtual inheritance edge that is used in C++.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Arnold, K. and Gosling, J. 1996. The Java Programming Language. The Java Series. Addison-Wesley Publishing Company, Reading, MA.
	2	Borning, A. H. and Ingalls, D. H. H. 1982. Multiple inheritance in Smalltalk80. In Proceedings of the 2nd National Conference on Artificial Intelligence. MIT Press, Cambridge, MA, 234--238.
	3	Cargill, T. A., Cox, B., Cook, W. R., Loomis, M., and Snyder, A. 1993. Is multiple inheritance essential to OOP? Panel discussion at the ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA'93).
	4	Chambers, C. 1993. The Cecil language, specification and rationale. Tech. rep. TR-93-03-05, University of Washington, Seattle.
	5	Dixon, R., McKee, T., Vaughan, M., and Schweizer, P. 1989. 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 (OOPSLA'89), N. K. Meyrowitz, Ed. ACM SIGPLAN Notices 24, 10, 211--214.
	6	Eckel, N. and Gil, J. 2000. Empirical study of object-layout strategies and optimization techniques. In Proceedings of the 14th European Conference on Object-Oriented Programming (ECOOP'00), E. Bertino, Ed. Lecture Notes in Computer Science, vol. 1850. Springer Verlag, 394--421.
	7	Gil, J. and Sweeney, P. F. 1999. Space- and time-efficient memory layout for multiple inheritance. In Proceedings of the 14th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'99). ACM SIGPLAN Notices 34, 10, 256--275.
	8	Goldberg, A. 1984. Smalltalk-80: The Interactive Programming Environment. Addison-Wesley, Reading, MA.
	9	Lippman, S. B. 1996. Inside The C++ Object Model 2nd ed. Addison-Wesley, Reading, MA.
	10	Magnussun, B., Meyer, B., et al. 1994. Who needs need multiple inheritance. In Proceedings of the International Conference on Technology of Object-Oriented Languages and Systems (TOOLS'94). Prentice-Hall, Englewood Cliffs, NJ.
	11	Moon, D. A. 1986. Object-oriented programming with flavors. In Proceedings of the 1st Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'86), N. K. Meyrowitz, Ed. ACM SIGPLAN Notices 21, 11, ON, 1--8.
	12	Myers, A. C. 1995. Bidirectional object layout for separate compilation. In Proceedings of the 10th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'95). ACM SIGPLAN Notices 30, 10, 124--139.
	13	Pascal, A. and Royer, J. 1992. Optimizing Method Search with Lookup Caches and Incremental Coloring. In Proceedings of the 7th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'92), A. Paepcke, Ed. ACM SIGPLAN Notices 27, 10, 110--126.
	14	Pugh, W. and Weddell, G. 1990. Two-directional record layout for multiple inheritance. In Proceedings of the Conference on Programming Language Design and Implementation (PLDI'90). ACM SIGPLAN Notices 25, 6, 85--91.
	15	Pugh, W. and Weddell, G. 1993. On object layout for multiple inheritance. Tech. rep. CS-93-22, Department of Computer Science, University of Waterloo.
	16	Shalit, A. 1997. The Dylan Reference Manual: The Definitive Guide to the New Object-Oriented Dynamic Language. Addison-Wesley Publishing Company, Reading, MA.
	17	Stroustrup, B. 1994. The Design and Evolution of C++. Addison-Wesley Publishing Company, Reading, MA.
	18	Stroustrup, B. 1997. The C++ Programming Language 3rd ed. Addison-Wesley Publishing Company, Reading, MA.
	19	Sweeney, P. F. and Burke, M. 2003. Quantifying and evaluating the space overhead for alternative C++ memory layouts. Softw. Pract. Exp. 33, 7, 595--636.
	20	Trotter, W. T. 1992. Combinatorics and Partially Ordered Sets: Dimension Theory. Johns Hopkins University Press, Baltimore, MD.
	21	Zendra, O., Colnet, D., and Collin, S. 1997. Efficient dynamic dispatch without virtual function tables: The SmallEiffel compiler. In Proceedings of the 12th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'97). ACM SIGPLAN Notices 32, 10, 125--141.
	22	Zibin, Y. and Gil, J. 2001. Efficient subtyping tests with PQ-encoding. In Proceedings of the 16th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'01). ACM SIGPLAN Notices 36, 11, 96--107.
	23	Zibin, Y. and Gil, J. 2002. Fast algorithm for creating space efficient dispatching tables with application to multi-dispatching. In Proceedings of the 17th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'02). ACM SIGPLAN Notices 37, 11, 142--160.
	24	Zibin, Y. and Gil, J. 2003. Incremental algorithms for dispatching in dynamically typed languages. In Proceedings of the 13th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'03). ACM Press, New York, NY, 126--138.