Optimistic stack allocation for java-like languages

ABSTRACT

Stack allocation of objects offers more efficient use of cache memories on modern computers, but finding objects that can be safely stack allocated is difficult, as interprocedural escape analysis is imprecise in the presence of virtual method dispatch and dynamic class loading. We present a new technique for doing optimistic stack allocation of objects. Our technique does not require interprocedural analysis and is effective in the presence of dynamic class loading, reflection and exception handling. Moreover, we usually achieve higher proportions of stack allocated data than static strategies. In this paper we present optimistic stack-allocation for Java-like languages. For experiments we use traces of running Java programs to drive simulations of various garbage collection and allocation strategies.

REFERENCES

• 1: Andrew W. Appel and Zhong Shao. An empirical and analytic study of stack vs. heap cost for languages with closures. Technical Report CS-TR-450-94, 1994. Available from: http://citeseer.nj.nec.com/appel94empirical.html.
• 2: Henry G. Baker, CONS should not CONS its arguments, or, a lazy alloc is a smart alloc, ACM SIGPLAN Notices, v.27 n.3, p.24-34, March 1992 [doi>10.1145/130854.130858]
• 3: Stephen M. Blackburn , Antony L. Hosking, Barriers: friend or foe?, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029891]
• 4: Bruno Blanchet, Escape analysis for object-oriented languages: application to Java, ACM SIGPLAN Notices, v.34 n.10, p.20-34, Oct. 1999
• 5: Yannis Bres, Bernard P. Serpette, and Manuel Serrano. Bigloo.NET: compiling Scheme to .NET CLR. Journal of Object Technology, 3(9):71--94, 2004. Available from: http://www.jot.fm/issues/issue_2004_10/article4.
• 6: Lars Birkedal , Mads Tofte , Magnus Vejlstrup, From region inference to von Neumann machines via region representation inference, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.171-183, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237771]
• 7: Vidal Burgoa. Implementation of CPU resource accounting for Java (M.Sc, U. of Geneva). ftp://cui.unige.ch/pub/tios/papers/Diploma-Vidal.pdf, 2001.
• 8: Jong-Deok Choi , Manish Gupta , Mauricio Serrano , Vugranam C. Sreedhar , Sam Midkiff, Escape analysis for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-19, November 01-05, 1999, Denver, Colorado, United States
• 9: Perry Cheng , Robert Harper , Peter Lee, Generational stack collection and profile-driven pretenuring, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.162-173, June 17-19, 1998, Montreal, Quebec, Canada
• 10: Erik Corry. Stack allocation for object-oriented languages (M.Sc. thesis, Department of Computer Science - Daimi, University of Aarhus). http://www.daimi.au.dk/corry/corrythesis.pdf, 2004.
• 11: Sigmund Cherem , Radu Rugina, Region analysis and transformation for Java programs, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029884]
• 12: Amer Diwan , David Tarditi , Eliot Moss, Memory Subsystem Performance of Programs with Intensive Heap Allocation, Carnegie Mellon University, Pittsburgh, PA, 1993
• 13: Martin Elsman. Program Modules, Separate Compilation,and Intermodule Optimisation. PhD thesis, Departmentof Computer Science, University of Copenhagen, January 1999. Available from: http://www.it.edu/people/mael/mypapers/phd.ps.gz.
• 14: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 15: David Gay , Bjarne Steensgaard, Fast Escape Analysis and Stack Allocation for Object-Based Programs, Proceedings of the 9th International Conference on Compiler Construction, p.82-93, March 25-April 02, 2000
• 16: Niels Hallenberg , Martin Elsman , Mads Tofte, Combining region inference and garbage collection, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 17: Intel. The IA-32 Intel architecture software developer's manual, volume 3: System programming guide. Available from: http://www.intel.com/design/pentium4/manuals/253668.htm.
• 18: Intel. Intel XScale microarchitecture for the PXA250 and PXA210 applications processors. Available from: http://developer.intel.com/design/pca/prodbref/pxa250.pdf.
• 19: Intel. IA-32 Intel architecture optimization reference manual, 2000. Available from: http://www.intel.com/design/pentium4/manuals/248966.htm.
• 20: H. Prokop. Cache-Oblivious Algorithms, June 1999. Master's thesis, MIT Department of Electrical Engineering and Computer Science. Available from: http://citeseer.ist.psu.edu/prokop99cacheobliviou.html.
• 21: Feng Qian , Laurie Hendren, An adaptive, region-based allocator for java, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
• 22: Mark B. Reinhold, Cache performance of garbage-collected programs, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.206-217, June 20-24, 1994, Orlando, Florida, United States
• 23: Alastair Reid, John McCorquodale, Jason Baker, Wilson Hsieh, and Joseph Zachary. The need for predictable garbage collection. In Proceedings of the ACM SIGPLAN Workshop on Compiler Support for System Software (WCSSS'99), May 1999. Available from: http://www.cs.utah.edu/flux/papers/gc-wcsss99.ps.gz.
• 24: Erik Ruf, Effective synchronization removal for Java, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.208-218, June 18-21, 2000, Vancouver, British Columbia, Canada
• 25: Darko Stefanovic , J. Eliot Moss, Properties of age-based automatic memory reclamation algorithms, 1999
• 26: Mads Tofte , Lars Birkedal , Martin Elsman , Niels Hallenberg, A Retrospective on Region-Based Memory Management, Higher-Order and Symbolic Computation, v.17 n.3, p.245-265, September 2004 [doi>10.1023/B:LISP.0000029446.78563.a4]
• 27: R. L. While and A. J. Field. The Non-stop Spineless Tagless G-machine. Available from: http://citeseer.nj.nec.com/while96nonstop.html.
• 28: Benjamin Zorn. Barrier methods for garbage collection. Technical Report CU-CS-494-90, 1990. Available from: http://citeseer.nj.nec.com/zorn90barrier.html.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection)

General Terms:
Languages, Performance

Keywords:
Java, garbage collection, stack allocation