Julian Dolby
ABSTRACT
Object-oriented languages like Java and Smalltalk provide a uniform object model that simplifies programming by providing a consistent, abstract model of object behavior. But direct implementations introduce overhead, removal of which requires aggressive implementation techniques (e.g. type inference, function specialization); in this paper, we introduce object inlining, an optimization that automatically inline allocates objects within containers (as is done by hand in C++) within a uniform model. We present our technique, which includes novel program analyses that track how inlinable objects are used throughout the program. We evaluated object inlining on several object-oriented benchmarks. It produces performance up to three times as fast as a dynamic model without inlining and roughly equal to that of manually-inlined codes.
- 1.O. Agesen, J. Palsberg, and M. Schwartzbach. Type inference of SELF' Analysis of objects with dynamic and multiple inheritance. In Proceedings of ECOOP '93, 1993. Google Scholar
Digital Library
- 2.Jennifer M. Anderson, Saman P. Amarasinghe, and Monica S. Lam. Data and computation transformations for multiprocessors. In Proceedings of Fifth Symposium on Principles and Practice of Parallel Programming, 1995. Google ScholarDigital Library
- 3.Apple Computer inc. The NewtonScript Program. ruing Language, December 1995. Available online from ftp://ftpdev.info.apple.com/Developer_Services/ Newton.Development/DOCS_PDF/NSCRIPTR.ZIP.Google Scholar
- 4.A. Black, N. Hutchinson, E. Jul, and H. Levy. Object structure in the emerald system. In Proceedings of OOPSLA '86, pag~ 78-86. ACM, September 1986. Google ScholarDigital Library
- 5.Brad Calder, Dirk Grunwald, and Benjamin Zorn. Quantifying differences between C and C++ programs. Technical Report CU-CS-698-94, University of Colorado, Boulder, January 1994.Google Scholar
- 6.C. Chambers and D. Ungar. Iterative type analysis and extended message splitting. In Proceedings of the SIG- PLAN Conference on Programming Language Design and Implementation, pages 150-60, 1990. Google ScholarDigital Library
- 7.Craig Chambers. The Cecil language: Specification and rationale, version 2.0. Technical report, Department of Computer Science and Engineering, University of Washington, Seattle, Washington, March 1995.Google Scholar
- 8.Andrew Chien, Julian Dolby, Bishwaroop Ganguly, Vijay Karamcheti, and Xingbin Zhang. Supporting high level programming with high performance: The illinois concert system. In Proceedings of the Second Inter. national Workshop on High-level Parallel Programming Models and Supportive Environments, April 1997. Google ScholarDigital Library
- 9.Andrew A. Chien, Uday S. Reddy, John Plevyak, and Julian Dolby. ICC++ - a C++ dialect for highperformance parallel computation. In Proceedings of the ~nd International Symposium on Object Technologies for Advanced Software, March 1996. Google ScholarDigital Library
- 10.Jeffrey Dean, Craig Chambers, and David Grove. Selective specialization for object-oriented languages. In Proceedings of the A CM SIGPLAN '95 Conference on Progrararnin g Language Design and Implementation, pages 93-102, La Jolla, CA, June 1995. Google ScholarDigital Library
- 11.Margaret A. Ellis and Bjarne Stroustrup. The Annotated C-t-4- Reference Manual Addison-Wesley, 1990. Google ScholarDigital Library
- 12.Tim Freeman and Frank Pfenning. Refinement types for ml. In Proceedings of the 1991 A CM SIGPLAN Conference on Programming Language Design and Implementation, June 1991. Google ScholarDigital Library
- 13.Adele Goldberg and David Robson. Smalltalk-80: The language and its implementation. Addison-Wesley, 1985. Google ScholarDigital Library
- 14.H. Mossenbock.Object-Oriented Programming in Oberon-2. Springer-Verlag, 1993. Google ScholarDigital Library
- 15.Cordelia Hall, Simon L. Peyton-Jones, and Patrick M. Sansom. Functional Programming, Glasgow 1994, chapter Unboxing Using Specialization. Workshops in Computing Science. Springer-Verlag, 1995.Google Scholar
- 16.Urs HSlzle, Craig Chambers, and David Ungar. Optimizing dynamically-typed object-oriented languages with polymorphic inline caches. In ECOOP'91 Conference Proceedings. Springer-Verlag, 1991. Lecture Notes in Computer Science 512. Google ScholarDigital Library
- 17.Urs HSlzle and David Ungar. Optimizing dynamicallydispatched calls with run-time type feedback. In Proceedings of the 199j ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 326-336, June 1994. Google ScholarDigital Library
- 18.Norman C. Hutchinson. Emerald: An Object-Based Language for Distributed Programming. PhD thesis, University of Washington, Department of Computer Science, Seattle, Washington, 1987. TR-87-01-01. Google ScholarDigital Library
- 19.Xavier Leroy. Unboxed objects and polymorphic typing. In Proceedings of the 19th Symposium on the Principles of Programming Languages, pages 177-188, 1992. Google ScholarDigital Library
- 20.N. Wirth and J. Gutknecht. Project Oberon: The Design of an Operating System and Compiler. Addison Wesley, 1992. Google ScholarDigital Library
- 21.J. Palsberg and M. Schwartzbach. Object-oriented type inference. In Proceedings of OOPSLA '91, pages 146- 61, 1991. Google ScholarDigital Library
- 22.John Plevyak. Optimization of Object-Orzented and Concurrent Programs. PhD thesis, University of Illinois at Urbana-Champaign, Urbana, Illinois, 1996. Google ScholarDigital Library
- 23.John Plevyak and Andrew A. Chien. Precise concrete type inference of object-oriented programs. In Proceedings of OOPSLA '9d, Object-Oriented Programming Systems, Languages and Architectures, pages 324-340, 1994. Google ScholarDigital Library
- 24.John Plevyak and Andrew A. Chien. Type directed cloning for object-oriented programs. In Proceedings of the Workshop for Languages and Compilers for Parallel Computing, pages 566-580, 1995. Google ScholarDigital Library
- 25.Zhong Shao, John Ill. Reppy, and Andrew W. Appel. Unrolling lists. In A CM Conference on Lisp and Functional Programming, June 1994. Google ScholarDigital Library
- 26.Olin Shivers. Topics in Advanced Language Imp&men. tation~ chapter Data-Flow Analysis and Type Recovery in Scheme, pages 47-88. MIT Press, Cambridge, MA, 1991.Google Scholar
- 27.Sun Microsystems Computer Corporation. The Java Language Specification, March 1995. Available at ht tp://j ava. sun. corn/1.0alp ha2/doc }java-whitepaper. ps.Google Scholar
- 28.Gregory V. Wilson and Paul Lu, editors. Parallel Programming Using C-t-4-. MIT Press, 1995.Google Scholar
- 29.Micheal E. Wolf and Monica S. Lam. A data locality optimizing algorithm. In Proceedings of the 1991 A CM SIGPLAN Conference on Programming Language Design and Implementation, June 1991. Google ScholarDigital Library
Index Terms
- Automatic inline allocation of objects
Recommendations
An evaluation of automatic object inline allocation techniques
OOPSLA '98: Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applicationsObject-oriented languages such as Java and Smalltalk provide a uniform object reference model, allowing objects to be conveniently shared. If implemented directly, these uniform reference models can suffer in efficiency due to additional memory ...
Automatic inline allocation of objects
Object-oriented languages like Java and Smalltalk provide a uniform object model that simplifies programming by providing a consistent, abstract model of object behavior. But direct implementations introduce overhead, removal of which requires ...
An evaluation of automatic object inline allocation techniques
Object-oriented languages such as Java and Smalltalk provide a uniform object reference model, allowing objects to be conveniently shared. If implemented directly, these uniform reference models can suffer in efficiency due to additional memory ...
Comments