Split-stream dictionary program compression

ABSTRACT

This paper describes split-stream dictionary (SSD) compression, a new technique for transforming programs into a compact, interpretable form. We define a compressed program as interpretable when it can be decompressed at basic-block granularity with reasonable efficiency. The granularity requirement enables interpreters or just-in-time (JIT) translators to decompress basic blocks incrementally during program execution. Our previous approach to interpretable compression, the Byte-coded RISC (BRISC) program format [1], achieved unprecedented decompression speed in excess of 5 megabytes per second on a 450MHz Pentium II while compressing benchmark programs to an average of three-fifths the size of their optimized x86 representation. SSD compression combines the key idea behind BRISC with new observations about instruction re-use frequencies to yield four advantages over BRISC and other competing techniques. First, SSD is simple, requiring only a few pages of code for an effective implementation. Second, SSD compresses programs more effectively than any interpretable program compression scheme known to us. For example, SSD compressed a set of programs including the spec95 benchmarks and Microsoft Word97 to less than half the size, on average, of their optimized x86 representation. Third, SSD exceeds BRISC's decompression and JIT translation rates by over 50%. Finally, SSD's two-phased approach to JIT translation enables a virtual machine to provide graceful degradation of program execution time in the face of increasing RAM constraints. For example, using SSD, we ran Word97 using a JIT-translation buffer one-third the size of Word97's optimized x86 code, yet incurred only 27% execution time overhead.

REFERENCES

• 1: Jens Ernst , William Evans , Christopher W. Fraser , Todd A. Proebsting , Steven Lucco, Code compression, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.358-365, June 16-18, 1997, Las Vegas, Nevada, United States
• 2: http ://www'palm'c~m/h~me'html
• 3: J. M. Kahn , R. H. Katz , K. S. J. Pister, Next century challenges: mobile networking for “Smart Dust”, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.271-278, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313558]
• 4: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 5: Intel Corp., Pentium Processor User's Manual Volume 3: Architecture and Programming Manual, Intel Literature Sales, ISBN 1-55512-195-0.
• 6: http://developer.intel.com/design/ia64/microarch_ovw/index. htm.
• 7: Steve B. Furber, ARM System Architecture, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 8: S. Lucco, O. Sharp, and R. Wahbe, "Omniware: a universal substrate for web programming," in Fourth International World Wide Web Conference, Boston, Massachusetts, 12/95. http ://www.w3.org/Conferences/WWW4/Papers/165/.
• 9: Ali-Reza Adl-Tabatabai , Geoff Langdale , Steven Lucco , Robert Wahbe, Efficient and language-independent mobile programs, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.127-136, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 10: A. Lempel and J. Ziv, "On the complexity of finite sequences," IEEE Transactions on Information Theory 22(1):75-81, 1/76.
• 11: J. Ziv and A. Lempel, "Compression of individual sequences via variable-rate coding," IEEE Transactions on Information Theory 24(5):530-536, 9/78.
• 12: Christopher W. Fraser, Automatic inference of models for statistical code compression, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.242-246, May 01-04, 1999, Atlanta, Georgia, United States
• 13: Ken Arnold , James Gosling, The Java programming language (2nd ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1998
• 14: 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
• 15: "Architecture Neutral Distribution Format: a white paper," Open Software Foundation, 11/90.
• 16: Michael Franz , Thomas Kistler, Slim binaries, Communications of the ACM, v.40 n.12, p.87-94, Dec. 1997 [doi>10.1145/265563.265576]
• 17: M. Franz, "Adaptive compression of syntax trees and iterative dynamic code optimization: Two basic technologies for mobile-object systems," TR 97-04, Dept. of Information and Computer Science, University of California, Irvine, 2/97.
• 18: Ian H. Witten , Radford M. Neal , John G. Cleary, Arithmetic coding for data compression, Communications of the ACM, v.30 n.6, p.520-540, June 1987 [doi>10.1145/214762.214771]
• 19: Tong Lai Yu, Data compression for PC software distribution, Software—Practice & Experience, v.26 n.11, p.1181-1195, Nov. 1996 [doi>10.1002/(SICI)1097-024X(199611)26:11<1181::AID-SPE54>3.3.CO;2-O]
• 20: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING

  D. Software
  D.3 PROGRAMMING LANGUAGES

General Terms:
Design, Performance, Theory

Keywords:
compression, runtime system, virtual machine