Heap compression for memory-constrained Java environments

ABSTRACT

Java is becoming the main software platform for consumer and embedded devices such as mobile phones, PDAs, TV set-top boxes, and in-vehicle systems. Since many of these systems are memory constrained, it is extremely important to keep the memory footprint of Java applications under control.The goal of this work is to enable the execution of Java applications using a smaller heap footprint than that possible using current embedded JVMs. We propose a set of memory management strategies to reduce heap footprint of embedded Java applications that execute under severe memory constraints. Our first contribution is a new garbage collector, referred to as the Mark-Compact-Compress (MCC) collector, that allows an application to run with a heap smaller than its footprint. An important characteristic of this collector is that it compresses objects when heap compaction is not sufficient for creating space for the current allocation request. In addition to employing compression, we also consider a heap management strategy and associated garbage collector, called MCL (Mark-Compact-Lazy Allocate), based on lazy allocation of object portions. This new collector operates like the conventional Mark-Compact (MC) collector, but takes advantage of the observation that many Java applications create large objects, of which only a small portion is actually used. In addition, we also combine MCC and MCL, and present MCCL (Mark-Compact-Compress-Lazy Al-locate), which outperforms both MCC and MCL.We have implemented these collectors using KVM, and performed extensive experiments using a set of ten embedded Java applications. We have found our new garbage collection strategies to be useful in two main aspects. First, they reduce the minimum heap size necessary to execute an application without out-of-memory exception. Second, our strategies reduce the heap occupancy. That is, at a given time, they reduce the heap memory requirement of the application being executed. We have also conducted experiments with a more aggressive object compression strategy and discussed its main advantages.

REFERENCES

• 1: 8/16 meg PalmPilot upgrades - prices. http://www.palmpilotupgrade.com/prices.html.
• 2: Casio: CdmaOne C452CA. http://www.javamobiles.com/casio/c452ca/.
• 3: Connected device configuration (CDC) specification. http://java.sun.com/j2me/.
• 4: Connected limited device configuration (CLDC) specification. http://java.sun.com/j2me/.
• 5: Java2 platform micro edition (J2ME) technology for creating mobile devices (white paper). http://java.sun.com/products/cldc/wp/KVMwp.pdf.
• 6: Mobile information device profile (MIDP) specification. http://java.sun.com/j2me/.
• 7: Palm product - Palm handheld comparison chart. http://www.palm.com/products/family.epl.
• 8: TinyVM. http://tinyvm.sourceforge.net/index.html.
• 9: US mobile devices to 2006: A land of opportunity. Based on an extensive research program conducted by Datamonitor on mobile device markets in the US.
• 10: David F. Bacon , Perry Cheng , V. T. Rajan, A real-time garbage collector with low overhead and consistent utilization, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.285-298, January 15-17, 2003, New Orleans, Louisiana, USA
• 11: David F. Bacon , Stephen J. Fink , David Grove, Space- and Time-Efficient Implementation of the Java Object Model, Proceedings of the 16th European Conference on Object-Oriented Programming, p.111-132, June 10-14, 2002
• 12: Stephen M Blackburn , Richard Jones , Kathryn S. McKinley , J Eliot B Moss, Beltway: getting around garbage collection gridlock, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 13: Stephen M. Blackburn , Sharad Singhai , Matthew Hertz , Kathryn S. McKinely , J. Eliot B. Moss, Pretenuring for Java, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.342-352, October 14-18, 2001, Tampa Bay, FL, USA
• 14: G. Chen , R. Shetty , M. Kandemir , N. Vijaykrishnan , M. J. Irwin , M. Wolczko, Tuning Garbage Collection in an Embedded Java Environment, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.92, February 02-06, 2002
• 15: Trishul M. Chilimbi , James R. Larus, Using generational garbage collection to implement cache-conscious data placement, Proceedings of the 1st international symposium on Memory management, p.37-48, October 17-19, 1998, Vancouver, British Columbia, Canada
• 16: 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
• 17: Lars Ræder Clausen , Ulrik Pagh Schultz , Charles Consel , Gilles Muller, Java bytecode compression for low-end embedded systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.3, p.471-489, May 2000 [doi>10.1145/353926.353933]
• 18: D. J. Craft, A fast hardware data compression algorithm and some algorithmic extensions, IBM Journal of Research and Development, v.42 n.6, p.733-745, November 1998
• 19: Sylvia Dieckmann , Urs Hölzle, A Study of the Allocation Behavior of the SPECjvm98 Java Benchmark, Proceedings of the 13th European Conference on Object-Oriented Programming, p.92-115, June 14-18, 1999
• 20: 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
• 21: P. A. Franaszek, P. Heidelberger, D. E. Poff, and J. T. Robison. Algorithms and data structures for compressed-memory machines. IBM Journal of Research and Development, 45(2):245--258, Mar. 2001.
• 22: G. Chen , M. Kandemir , N. Vijaykrishnan , M. J. Irwin , W. Wolf, Energy savings through compression in embedded Java environments, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado [doi>10.1145/774789.774823]
• 23: Martin Hirzel , Johannes Henkel , Amer Diwan , Michael Hind, Understanding the connectivity of heap objects, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
• 24: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 25: M. Kjelso, M. Gooch, , and S. Jones. Performance evaluation of computer architectures with main memory data compression. Elsevier Science, Journal of Systems Architecture, 45:571--590, 1999.
• 26: Haris Lekatsas , Jörg Henkel , Wayne Wolf, Code compression for low power embedded system design, Proceedings of the 37th conference on Design automation, p.294-299, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337423]
• 27: H. Lekatsas and W. Wolf. SAMC: a code compression algorithm for embedded processors. IEEE Transactions on CAD, 18(12):1689-1701, Dec. 1999.
• 28: Philip Levis , David Culler, Maté: a tiny virtual machine for sensor networks, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 29: D. Lidsky and J. Rabaey. Low-power design of memory intensive functions case study: Vector quantization. In 1994 IEEE Workshop on VLSI Signal Processing, pages 26--28, La Jolla, CA, USA, Oct. 1994.
• 30: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 31: S. McAteer. Java will be the dominant handset platform. http://www.microjava.com/articles/perspective/zelos.
• 32: Charles E. McDowell , Bruce R. Montague , Michael R. Allen , Elizabeth A. Baldwin , Marcelo E. Montoreano, Javacam: Trimming Java Down to Size, IEEE Internet Computing, v.2 n.3, p.53-59, May 1998 [doi>10.1109/4236.683800]
• 33: William Pugh, Compressing Java class files, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.247-258, May 01-04, 1999, Atlanta, Georgia, United States
• 34: Luigi Rizzo, A very fast algorithm for RAM compression, ACM SIGOPS Operating Systems Review, v.31 n.2, p.36-45, April 1997 [doi>10.1145/250007.250012]
• 35: Ran Shaham , Elliot K. Kolodner , Mooly Sagiv, Heap profiling for space-efficient Java, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.104-113, June 2001, Snowbird, Utah, United States
• 36: Nik Shaylor, A Just-in-Time Compiler for Memory-Constrained Low-Power Devices, Proceedings of the 2nd Java™ Virtual Machine Research and Technology Symposium, p.119-126, August 01-02, 2002
• 37: Yefim Shuf , Manish Gupta , Rajesh Bordawekar , Jaswinder Pal Singh, Exploiting prolific types for memory management and optimizations, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.295-306, January 16-18, 2002, Portland, Oregon
• 38: Yefim Shuf , Manish Gupta , Hubertus Franke , Andrew Appel , Jaswinder Pal Singh, Creating and preserving locality of java applications at allocation and garbage collection times, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 39: Yefim Shuf , Mauricio J. Serrano , Manish Gupta , Jaswinder Pal Singh, Characterizing the memory behavior of Java workloads: a structured view and opportunities for optimizations, ACM SIGMETRICS Performance Evaluation Review, v.29 n.1, p.194-205, June 2001
• 40: C. van Reeuwijk , H. J. Sips, Adding tuples to Java: a study in lightweight data structures, Proceedings of the 2002 joint ACM-ISCOPE conference on Java Grande, p.185-191, November 03-05, 2002, Seattle, Washington, USA [doi>10.1145/583810.583831]
• 41: N. Vijaykrishnan, M. Kandemir, S. Kim, S. Tomar, A. Sivasubramaniam, and M. J. Irwin. Energy behavior of Java applications from the memory perspective. In USENIX Java Virtual Machine Research and Technology Symposium (JVM'01), Monterey, CA, USA, Apr. 2001.
• 42: Paul R. Wilson, Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.1-42, September 17-19, 1992
• 43: Yuan Xie , Wayne Wolf , Haris Lekatsas, A code decompression architecture for VLIW processors, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Dynamic storage management

General Terms:
Algorithms, Languages

Keywords:
Java virtual machine, garbage collection, heap, memory compression