{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:38:15Z","timestamp":1750307895690,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2008,8,1]],"date-time":"2008-08-01T00:00:00Z","timestamp":1217548800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["128\/02"],"award-info":[{"award-number":["128\/02"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p>\n            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\n            <jats:italic>no compiler generated fields<\/jats:italic>\n            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\n            <jats:italic>virtual inheritance edge<\/jats:italic>\n            that is used in C++.\n          <\/jats:p>","DOI":"10.1145\/1387673.1387677","type":"journal-article","created":{"date-parts":[[2008,9,4]],"date-time":"2008-09-04T12:51:35Z","timestamp":1220532695000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Two-dimensional bidirectional object layout"],"prefix":"10.1145","volume":"30","author":[{"given":"Joseph (Yossi)","family":"Gil","sequence":"first","affiliation":[{"name":"Technion\u2014Israel Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"William","family":"Pugh","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science, University of Maryland, College Park"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Grant E.","family":"Weddell","sequence":"additional","affiliation":[{"name":"University of Waterloo"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoav","family":"Zibin","sequence":"additional","affiliation":[{"name":"Technion\u2014Israel Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,9,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Arnold K. and Gosling J. 1996. The Java Programming Language. The Java Series. Addison-Wesley Publishing Company Reading MA.   Arnold K. and Gosling J. 1996. The Java Programming Language. The Java Series. Addison-Wesley Publishing Company Reading MA."},{"volume-title":"Proceedings of the 2nd National Conference on Artificial Intelligence. MIT Press","author":"Borning A. H.","key":"e_1_2_1_2_1","unstructured":"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. 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."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/165854.165923"},{"volume-title":"The Cecil language, specification and rationale. Tech. rep. TR-93-03-05","author":"Chambers C.","key":"e_1_2_1_4_1","unstructured":"Chambers , C. 1993. The Cecil language, specification and rationale. Tech. rep. TR-93-03-05 , University of Washington , Seattle. Chambers, C. 1993. The Cecil language, specification and rationale. Tech. rep. TR-93-03-05, University of Washington, Seattle."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/74877.74900"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 14th European Conference on Object-Oriented Programming (ECOOP'00)","volume":"1850","author":"Eckel N.","unstructured":"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. 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."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/320384.320408"},{"volume-title":"Smalltalk-80: The Interactive Programming Environment","author":"Goldberg A.","key":"e_1_2_1_8_1","unstructured":"Goldberg , A. 1984. Smalltalk-80: The Interactive Programming Environment . Addison-Wesley , Reading, MA . Goldberg, A. 1984. Smalltalk-80: The Interactive Programming Environment. Addison-Wesley, Reading, MA."},{"key":"e_1_2_1_9_1","volume-title":"Inside The C++ Object Model","author":"Lippman S. B.","unstructured":"Lippman , S. B. 1996. Inside The C++ Object Model 2 nd ed. Addison-Wesley , Reading, MA . Lippman, S. B. 1996. Inside The C++ Object Model 2nd ed. Addison-Wesley, Reading, MA.","edition":"2"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the International Conference on Technology of Object-Oriented Languages and Systems (TOOLS'94)","author":"Magnussun B.","year":"1994","unstructured":"Magnussun , B. , Meyer , B. , 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. 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."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/28697.28698"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/217838.217849"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/141936.141947"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/93542.93556"},{"key":"e_1_2_1_15_1","unstructured":"Pugh W. and Weddell G. 1993. On object layout for multiple inheritance. Tech. rep. CS-93-22 Department of Computer Science University of Waterloo.  Pugh W. and Weddell G. 1993. On object layout for multiple inheritance. Tech. rep. CS-93-22 Department of Computer Science University of Waterloo."},{"volume-title":"The Dylan Reference Manual: The Definitive Guide to the New Object-Oriented Dynamic Language","author":"Shalit A.","key":"e_1_2_1_16_1","unstructured":"Shalit , A. 1997. The Dylan Reference Manual: The Definitive Guide to the New Object-Oriented Dynamic Language . Addison-Wesley Publishing Company , Reading, MA . Shalit, A. 1997. The Dylan Reference Manual: The Definitive Guide to the New Object-Oriented Dynamic Language. Addison-Wesley Publishing Company, Reading, MA."},{"volume-title":"The Design and Evolution of C++","author":"Stroustrup B.","key":"e_1_2_1_17_1","unstructured":"Stroustrup , B. 1994. The Design and Evolution of C++ . Addison-Wesley Publishing Company , Reading, MA . Stroustrup, B. 1994. The Design and Evolution of C++. Addison-Wesley Publishing Company, Reading, MA."},{"key":"e_1_2_1_18_1","volume-title":"The C++ Programming Language","author":"Stroustrup B.","unstructured":"Stroustrup , B. 1997. The C++ Programming Language 3 rd ed. Addison-Wesley Publishing Company, Reading , MA. Stroustrup, B. 1997. The C++ Programming Language 3rd ed. Addison-Wesley Publishing Company, Reading, MA.","edition":"3"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.519"},{"volume-title":"Combinatorics and Partially Ordered Sets: Dimension Theory","author":"Trotter W. T.","key":"e_1_2_1_20_1","unstructured":"Trotter , W. T. 1992. Combinatorics and Partially Ordered Sets: Dimension Theory . Johns Hopkins University Press , Baltimore, MD . Trotter, W. T. 1992. Combinatorics and Partially Ordered Sets: Dimension Theory. Johns Hopkins University Press, Baltimore, MD."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/263698.263728"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/504282.504290"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/582419.582434"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/604131.604143"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1387673.1387677","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1387673.1387677","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:47:26Z","timestamp":1750258046000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1387673.1387677"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.1145\/1387673.1387677"],"URL":"https:\/\/doi.org\/10.1145\/1387673.1387677","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[2008,8]]},"assertion":[{"value":"2006-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-09-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}