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.
- 8/16 meg PalmPilot upgrades - prices. http://www.palmpilotupgrade.com/prices.html.]]Google Scholar
- Casio: CdmaOne C452CA. http://www.javamobiles.com/casio/c452ca/.]]Google Scholar
- Connected device configuration (CDC) specification. http://java.sun.com/j2me/.]]Google Scholar
- Connected limited device configuration (CLDC) specification. http://java.sun.com/j2me/.]]Google Scholar
- Java2 platform micro edition (J2ME) technology for creating mobile devices (white paper). http://java.sun.com/products/cldc/wp/KVMwp.pdf.]]Google Scholar
- Mobile information device profile (MIDP) specification. http://java.sun.com/j2me/.]]Google Scholar
- Palm product - Palm handheld comparison chart. http://www.palm.com/products/family.epl.]]Google Scholar
- TinyVM. http://tinyvm.sourceforge.net/index.html.]]Google Scholar
- 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.]]Google Scholar
- D. F. Bacon, P. Cheng, and V. T. Rajan. A real-time garbage collector with low overhead and consistent utilization. In the 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'03), pages 285--298, New Orleans, Lousiana, USA, Jan. 2003.]] Google ScholarDigital Library
- D. F. Bacon, S. J. Fink, and D. Grove. Space- and time-efficient implementation of the Java object model. In the 16th European Conference on Object-Oriented Programming (ECOOP'02), University of Malaga, Spain, June 2002.]] Google ScholarDigital Library
- S. M. Blackburn, R. Jones, K. S. McKinley, and J. E. B. Moss. Beltway: getting around garbage collection gridlock. In the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation (PLDI'02), pages 153--164, Berlin, Germany, June 2002.]] Google ScholarDigital Library
- S. M. Blackburn, S. Singhai, M. Hertz, K. S. McKinely, and J. E. B. Moss. Pretenuring for Java. In the Conference on Object Oriented Programming Systems Languages and Applications (OOPSLA'01), pages 342--352, Tampa Bay, FL, USA, 2001.]] Google ScholarDigital Library
- G. Chen, R. Shetty, M. Kandemir, N. Vijaykrishnan, M. J. Irwin, and M. Wolczko. Tuning garbage collection in an embedded Java environment. In the 8th International Symposium on High-Performance Computer Architecture (HPCA'02), Cambridge, MA, USA, Feb. 2002.]] Google ScholarDigital Library
- T. M. Chilimbi and J. R. Larus. Using generational garbage collection to implement cache-conscious data placement. In the 1st International Symposium on Memory Management (ISMM'98), pages 37--48, Vancouver, British Columbia, Canada, 1998.]] Google ScholarDigital Library
- J. D. Choi, M. Gupta, M. Serrano, V. Sreedhar, and S. Midkiff. Escape analysis for java. In ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA'99), Denver, CO, USA, Nov. 1999.]] Google ScholarDigital Library
- L. R. Clausen, U. P. Schultz, C. Consel, and G. Muller. Java bytecode compression for low-end embedded systems. ACM Transactions on Programming Languages and Systems (TOPLAS'00), 22(3):471--489, May 2000.]] Google ScholarDigital Library
- D. J. Craft. A fast hardware data compression algorithm and some algorithmic extensions. IBM Journal of Research and Development, 42(6), 1998.]] Google ScholarDigital Library
- S. Dieckmann and U. Holzle. A study of the allocation behavior of the SPECjvm98 Java benchmarks. In the 13th European Conference on Object-Oriented Programming (ECOOP'99), Lisbon, Portugal, June 1999.]] Google ScholarDigital Library
- N. Eckel and J. Gil. Empirical study of object-layout strategies and optimization techniques. In the 14th European Conference on Object-Oriented Programming (ECOOP'00), Sophia Antipolis and Cannes, France, June 2000.]] Google ScholarDigital Library
- 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.]]Google ScholarDigital Library
- G.Chen, M.Kandemir, N.Vijaykrishnan, and W.Wolf. Energy savings through compression in embedded Java environments. In the 10th International Symposium on Hardware/Software Codesign (CODES'02), Colorado, USA, May 2002.]] Google ScholarDigital Library
- M. Hirzel, J. Henkel, A. Diwan, and M. Hind. Understanding the connectivity of heap objects (ismm'02). In the 3rd International Symposium on Memory Management, pages 36--49, Berlin, Germany, 2002.]] Google ScholarDigital Library
- R. Jones. Garbage Collection: algorithms for automatic dynamic memory management. John Wiley & Sons, Ltd, 1999.]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- H. Lekatsas, J. Henkal, and W. Wolf. Code compression for low power embedded system design. In the 37th Conference on Design Automation (DAC'00), pages 294--299. ACM Press, 2000.]] Google ScholarDigital Library
- H. Lekatsas and W. Wolf. SAMC: a code compression algorithm for embedded processors. IEEE Transactions on CAD, 18(12):1689-1701, Dec. 1999.]]Google ScholarDigital Library
- P. Levis and D. Culler. Mate: A tiny virtual machine for sensor networks. In International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS'02), San Jose, CA, USA, Oct. 2002.]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- T. Lindholm and F. Yellin. The Java Virtual Machine Specification Second Edition. Addison-Wesley Pub Co, 1999.]] Google ScholarDigital Library
- S. McAteer. Java will be the dominant handset platform. http://www.microjava.com/articles/perspective/zelos.]]Google Scholar
- C. E. McDowell, B. R. Montague, M. R. Allen, E. A. Baldwin, and M. E. Montoreano. Javacam: Trimming Java down to size. IEEE Internet Computing, 2(3), May/June 1998.]] Google ScholarDigital Library
- W. Pugh. Compressing Java class files. In SIGPLAN Conference on Programming Language Design and Implementation (PLDI'99), pages 247--258, 1999.]] Google ScholarDigital Library
- L. Rizzo. A very fast algorithm for RAM compression. ACM SIGOPS Operating Systems Review, 31(2):36-45, Apr. 1997.]] Google ScholarDigital Library
- R. Shaham, E. K. Kolodner, and S. Sagiv. Heap profiling for space-efficient Java. In SIGPLAN Conference on Programming Language Design and Implementation (PLDI'01), pages 104--113, 2001.]] Google ScholarDigital Library
- N. Shaylor. A just-in-time compiler for memory constrained low-power devices. In USENIX Java Virtual Machine Research and Technology Symposium (JVM'02), San Francisco, CA, USA, Aug. 2002.]] Google ScholarDigital Library
- Y. Shuf, M. Gupta, R. Bordawekar, and J. P. Singh. Exploiting prolific types for memory management and optimizations. In Symposium on Principles of Programming Languages (POPL'02), pages 295--306, 2002.]] Google ScholarDigital Library
- Y. Shuf, M. Gupta, H. Franke, A. Appel, and J. P. Singh. Creating and preserving locality of java applications at allocation and garbage collection times. In the 2002 ACM Conference on Object-Oriented Programming, Systems, Languages and Applications (OOPSLA'02), Seattle, WA, USA, Nov. 2002.]] Google ScholarDigital Library
- Y. Shuf, M. J. Serrano, M. Gupta, and J. P. Singh. Characterizing the memory behavior of Java workloads: a structured view and opportunities for optimizations. In SIGMETRICS/Performance, pages 194--205, 2001.]] Google ScholarDigital Library
- C. van Reeuwijk and H. J. Sips. Adding tuples to Java: a study in lightweight data structures. In Joint ACM Java Grande - ISCOPE 2002 Conference, pages 185-191, Seattle, WA, USA, Nov. 2002.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- P. R. Wilson. Uniprocessor garbage collection techniques. In International Workshop on Memory Management, Saint-Malo, France, 1992. Springer-Verlag.]] Google ScholarDigital Library
- Y. Xie, W. Wolf, and H. Lekatsas. A code compression architecture for VLIW processors. In the 34th Annual International Symposium on Microarchitecture (MICRO'01), pages 66--75, Austin, TX, USA, 2001.]] Google ScholarDigital Library
Index Terms
- Heap compression for memory-constrained Java environments
Recommendations
Heap compression for memory-constrained Java environments
OOPSLA '03: Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applicationsJava 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 ...
Exploiting frequent field values in java objects for reducing heap memory requirements
VEE '05: Proceedings of the 1st ACM/USENIX international conference on Virtual execution environmentsThe capabilities of applications executing on embedded and mobile devices are strongly influenced by memory size limitations. In fact, memory limitations are one of the main reasons that applications run slowly or even crash in embedded/mobile devices. ...
Controlling garbage collection and heap growth to reduce the execution time of Java applications
In systems that support garbage collection, a tension exists between collecting garbage too frequently and not collecting it frequently enough. Garbage collection that occurs too frequently may introduce unnecessary overheads at the risk of not ...
Comments