PPMexe: Program compression

ABSTRACT

With the emergence of software delivery platforms, code compression has become an important system component that strongly affects performance. This article presents PPMexe, a compression mechanism for program binaries that analyzes their syntax and semantics to achieve superior compression ratios. We use the generic paradigm of prediction by partial matching (PPM) as the foundation of our compression codec. PPMexe combines PPM with two preprocessing steps: (i) instruction rescheduling to improve prediction rates and (ii) heuristic partitioning of a program binary into streams with high autocorrelation. We improve the traditional PPM algorithm by (iii) using an additional alphabet of frequent variable-length supersymbols extracted from the input stream of fixed-length symbols. In addition, PPMexe features (iv) a low-overhead mechanism that enables decompression starting from an arbitrary instruction of the executable, a property pivotal for runtime software delivery. We implemented PPMexe for x86 binaries and tested it on several large applications. Binaries compressed using PPMexe were 18--24% smaller than files created using off-the-shelf PPMD, one of the best available compressors

REFERENCES

• 1: Guido Araujo , Paolo Centoducatte , Rodolfo Azevedo , Ricardo Pannain, Expression-tree-based algorithms for code compresion on embedded RISC architectures, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.5, p.530-533, Oct., 2000 [doi>10.1109/92.894158]
• 2: Baker, B. S. and Manber, U. 1998. Deducing similarities in Java sources from bytecodes. In Proceedings of the USENIX Annual Technical Conference. 179--190.
• 3: Bunton, S. 1997. Semantically motivated improvements for PPM variants. Comput. J. 40, 2/3, 76--93.
• 4: Burrows, M. and Wheeler, D. 1994. A block-sorting lossless data compression algorithm. Tech. Rep., Digital Equipment Corporation.
• 5: Martin Burtscher , Ilya Ganusov , Sandra J. Jackson , Jian Ke , Paruj Ratanaworabhan , Nana B. Sam, The VPC Trace-Compression Algorithms, IEEE Transactions on Computers, v.54 n.11, p.1329-1344, November 2005 [doi>10.1109/TC.2005.186]
• 6: Gregory J. Chaitin, On the Length of Programs for Computing Finite Binary Sequences, Journal of the ACM (JACM), v.13 n.4, p.547-569, Oct. 1966 [doi>10.1145/321356.321363]
• 7: Gregory J. Chaitin, On the Length of Programs for Computing Finite Binary Sequences: statistical considerations, Journal of the ACM (JACM), v.16 n.1, p.145-159, Jan. 1969 [doi>10.1145/321495.321506]
• 8: Cleary, J. and Witten, I. 1984. Data compression using adaptive coding and partial string matching. IEEE Trans. Commun. 32, 4, 396--402.
• 9: Saumya K. Debray , William Evans , Robert Muth , Bjorn De Sutter, Compiler techniques for code compaction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.378-415, March 2000 [doi>10.1145/349214.349233]
• 10: 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
• 11: Michael Franz , Thomas Kistler, Slim binaries, Communications of the ACM, v.40 n.12, p.87-94, Dec. 1997 [doi>10.1145/265563.265576]
• 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: Christopher W. Fraser , Eugene W. Myers , Alan L. Wendt, Analyzing and compressing assembly code, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.117-121, June 17-22, 1984, Montreal, Canada
• 14: Gilchrist, J. 2000. The archive compression test. http://compression.ca.
• 15: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 16: Lee W. Hoevel , Michael J. Flynn, The structure of directly executed languages: a new theory of interpretive system design, Stanford University, Stanford, CA, 1977
• 17: Inki Hong , Darko Kirovski , Miodrag Potkonjak, Potential-driven statistical ordering of transformations, Proceedings of the 34th annual conference on Design automation, p.347-352, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266161]
• 18: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 19: Paul Glor Howard, The design and analysis of efficient lossless data compression systems, Brown University, Providence, RI, 1993
• 20: Howard, P. and Vitter, J. 1993. Design and analysis of fast text compression based on quasi-arithmetic coding. In Proceedings of the Data Compression Conference. 98--107.
• 21: Huffman, D. 1952. A method for construction of minimum redundancy codes. Proc. IEEE 40, 1098--1101.
• 22: Intel Corp. 1999a. http://www.intel.com/design/pentiumiii.
• 23: Intel Corp. 1999b. Intel architecture software developer's manual, vol. 2: Instruction set reference manual. http://developer.intel.com/design/processor/.
• 24: Intel Corp. 2000. http://www.intel.com/design/pentium4.
• 25: Darko Kirovski , Johnson Kin , William H. Mangione-Smith, Procedure based program compression, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.204-213, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 26: Kolmogorov, A. N. 1965. Three approaches to the quantitative definition of information. Problems Inf. Transmission 1, 1, 1--7.
• 27: L. N. Korolev, Coding and Code Compression, Journal of the ACM (JACM), v.5 n.4, p.328-330, Oct. 1958 [doi>10.1145/320941.320944]
• 28: Jeremy Lau , Stefan Schoenmackers , Timothy Sherwood , Brad Calder, Reducing code size with echo instructions, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951724]
• 29: Haris Lekatsas , Wayne Wolf, Random Access Decompression using Binary Arithmetic Coding, Proceedings of the Conference on Data Compression, p.306, March 29-31, 1999
• 30: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steven Tjiang , Albert Wang, Storage assignment to decrease code size, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.3, p.235-253, May 1996 [doi>10.1145/229542.229543]
• 31: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang, Instruction selection using binate covering for code size optimization, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.393-399, November 05-09, 1995, San Jose, California, United States
• 32: Steven Lucco, Split-stream dictionary program compression, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.27-34, June 18-21, 2000, Vancouver, British Columbia, Canada
• 33: Moffat, A. 1990. Implementing the PPM data compression scheme. IEEE Trans. Commun. 38, 11, 1917--1921.
• 34: Mohney, D. 2003. It's all about the last mile. http://www.theinquirer.net.
• 35: Thomas P. Murtagh, An improved storage management scheme for block structured languages, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.3, p.372-398, July 1991 [doi>10.1145/117009.117016]
• 36: Todd A. Proebsting, Optimizing an ANSI C interpreter with superoperators, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.322-332, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199526]
• 37: 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
• 38: Amit Rao , Santosh Pande, Storage assignment optimizations to generate compact and efficient code on embedded DSPs, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.128-138, May 01-04, 1999, Atlanta, Georgia, United States
• 39: Rissanen, J. 1978. Modeling by shortest data description. Automatica 14, 465--471.
• 40: Rissanen, J. and Mohiuddin, K. M. 1989. A multiplication-free multialphabet arithmetic code. IEEE Trans. Commun. 37, 3, 129--146.
• 41: Theodore H. Romer , Dennis Lee , Geoffrey M. Voelker , Alec Wolman , Wayne A. Wong , Jean-Loup Baer , Brian N. Bershad , Henry M. Levy, The structure and performance of interpreters, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.150-159, October 01-04, 1996, Cambridge, Massachusetts, United States
• 42: Shannon, C. 1951. Prediction and entropy of printed English. Bell Syst. Tech. J. 50--64.
• 43: Srivastava, A. and Vo, H. 2001. Vulcan: Binary transformation in a distributed environment. Tech. Rep. MSR-TR-2001-50. Microsoft Research.
• 44: Tarja Systä , Kai Koskimies , Hausi Müller, Shimba—an environment for reverse engineering Java software systems, Software—Practice & Experience, v.31 n.4, p.371-394, April 10, 2001 [doi>10.1002/spe.386]
• 45: Thomas E. Truman , Trevor Pering , Roger Doering , Robert W. Brodersen, The InfoPad Multimedia Terminal: A Portable Device for Wireless Information Access, IEEE Transactions on Computers, v.47 n.10, p.1073-1087, October 1998 [doi>10.1109/12.729791]
• 46: Weaver, C. 2000. SPEC2000 binaries. http://www.simplescalar.org.
• 47: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 48: Andrew Wolfe , Alex Chanin, Executing compressed programs on an embedded RISC architecture, Proceedings of the 25th annual international symposium on Microarchitecture, p.81-91, December 01-04, 1992, Portland, Oregon, United States
• 49: Xiangyu Zhang , Rajiv Gupta, Whole execution traces and their applications, ACM Transactions on Architecture and Code Optimization (TACO), v.2 n.3, p.301-334, September 2005 [doi>10.1145/1089008.1089012]
• 50: Ziv, J. and Lempel, A. 1978. Compression of individual sequences via variable-rate coding. IEEE Trans. Inf. Theor. IT-24, 530--536.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

General Terms:
Algorithms, Performance

Keywords:
Instruction scheduling, prediction by partial matching, random access compression, software compression, software distribution