Vertical object layout and compression for fixed heaps

ABSTRACT

Research into embedded sensor networks has placed increased focus on the problem of developing reliable and flexible software for microcontroller-class devices. Languages such as nesC [8] and Virgil [14] have brought higher-level programming idioms to this lowest layer of software, thereby adding expressiveness. Both languages are marked by the absence of dynamic memory allocation, which removes the need for a runtime system to manage memory. To provide data structures, nesC offers modules, and Virgil offers the application an opportunity to allocate and initialize objects during compilation. This paper explores techniques for compressing fixed object heaps with the goal of reducing the RAM footprint of a program. We explore table-based compression and introduce a novel form of object layout called vertical object layout. We provide experimental results that measure the impact on RAM size, code size, and execution time for a set of Virgil programs. Our results show that compressed vertical layout has better execution time and code size than table-based compression while achieving more than 20% heap reduction on 6 of 12 benchmark programs.

REFERENCES

• 1: Ali-Reza Adl-Tabatabai , Jay Bharadwaj , Michal Cierniak , Marsha Eng , Jesse Fang , Brian T. Lewis , Brian R. Murphy , James M. Stichnoth, Improving 64-Bit Java IPF Performance by Compressing Heap References, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.100, March 20-24, 2004, Palo Alto, California
• 2: C. Scott Ananian , Martin Rinard, Data size optimizations for java programs, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 3: D. Bacon. Kava: a Java Dialect with a Uniform Object Model for Lightweight Classes. Concurrency and Computation: Practice and Experience 15(3-5): 185--206. 2003.
• 4: 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
• 5: R. Chapman, J. Barnes, and B. Dobbing. On the Principled Design of Object-Oriented Programming Languages for High-Integrity Systems. In the 2nd NASA/FAA Object-Oriented Technology Workshop. 2003.
• 6: G. Chen , M. Kandemir , N. Vijaykrishnan , M. J. Irwin , B. Mathiske , M. Wolczko, Heap compression for memory-constrained Java environments, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 7: Nathan Dean Cooprider , John David Regehr, Offline compression for on-chip ram, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 8: David Gay , Philip Levis , Robert von Behren , Matt Welsh , Eric Brewer , David Culler, The nesC language: A holistic approach to networked embedded systems, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 9: Chris Lattner , Vikram Adve, Automatic pool allocation for disjoint data structures, Proceedings of the 2002 workshop on Memory system performance, p.13-24, June 16-16, 2002, Berlin, Germany
• 10: Jeffrey C. Mogul , Joel F. Bartlett , Robert N. Mayo , Amitabh Srivastava, Performance implications of multiple pointer sizes, Proceedings of the USENIX 1995 Technical Conference Proceedings on USENIX 1995 Technical Conference Proceedings, p.16-16, January 16-20, 1995, New Orleans, Louisiana
• 11: Andrew C. Myers, Bidirectional object layout for separate compilation, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.124-139, October 15-19, 1995, Austin, Texas, United States
• 12: William Pugh , Grant Weddell, Two-directional record layout for multiple inheritance, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.85-91, June 1990, White Plains, New York, United States
• 13: W. Taha, S. Ellner, and H. Xi. Generating Imperative, Heap-Bounded Programs in a Functional Setting. In EMSOFT '03, the 3rd Annual International Conference on Embedded Software. Philadelphia, PA. October 2003.
• 14: Ben L. Titzer, Virgil: objects on the head of a pin, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 15: Ben L. Titzer , Jens Palsberg, Nonintrusive precision instrumentation of microcontroller software, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 16: Ben L. Titzer , Daniel K. Lee , Jens Palsberg, Avrora: scalable sensor network simulation with precise timing, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 17: P. Wilson. Operating system support for small objects. In Object Orientation in Operating Systems, pp.80--86, 1991.
• 18: Greg Wright , Matthew L. Seidl , Mario Wolczko, An object-aware memory architecture, Science of Computer Programming, v.62 n.2, p.145-163, 1 October 2006 [doi>10.1016/j.scico.2006.02.007]
• 19: Youtao Zhang , Rajiv Gupta, Compressing heap data for improved memory performance: Research Articles, Software—Practice & Experience, v.36 n.10, p.1081-1111, August 2006 [doi>10.1002/spe.v36:10]
• 20: Yoav Zibin , Joseph Yossi Gil, Efficient subtyping tests with PQ-encoding, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.96-107, October 14-18, 2001, Tampa Bay, FL, USA

INDEX TERMS

Primary Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Object representation

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Classes and objects

General Terms:
Languages, Management, Measurement, Performance

Keywords:
heap optimization, microcontrollers, object layout, pointer compression, program data compression, reference compression, vertical object layout