On the side-effects of code abstraction

ABSTRACT

More and more devices contain computers with limited amounts of memory. As a result, code compaction techniques are gaining popularity, especially when they also improve performance and power consumption, or at least not degrade it. This paper quantifies the side-effects of code abstraction on performance using extensive measurements and simulations on the SPECint2000 benchmark suite and some additional C++ programs. We show how to use profile information in order to obtain almost all the code size reduction benefits of code abstraction, yet experience almost none of its disadvantages.

REFERENCES

• 1: Andrew Ayers , Richard Schooler , Robert Gottlieb, Aggressive inlining, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.134-145, June 16-18, 1997, Las Vegas, Nevada, United States
• 2: B. S. Baker and U. Manber. Deducing similarities in Java sources from bytecodes. In USENIX Annual Technical Conference, pages 179--190, June 1998.
• 3: Jeffrey P. Bradford , Russell Quong, An empirical study on how program layout affects cache miss rates, ACM SIGMETRICS Performance Evaluation Review, v.27 n.3, p.28-42, Dec. 1999 [doi>10.1145/340242.340326]
• 4: D. Burger, T. M. Austin, and S. Bennett. Evaluating future microprocessors: The SimpleScalar tool set. Technical report, Computer Sciences Department, University of Wisconsin-Madison, July 1996.
• 5: W.-K. Chen, R. Gupta, and B. Li. Code compaction of matching single-entry multiple-exit regions. In Proceedings of the the 10th Annual International Static Analysis Symposium, June 2003. To appear.
• 6: 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]
• 7: Keith D. Cooper , Nathaniel McIntosh, Enhanced code compression for embedded RISC processors, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.139-149, May 01-04, 1999, Atlanta, Georgia, United States
• 8: Keith D. Cooper , Mary W. Hall , Linda Torczon, Unexpected side effects of inline substitution: a case study, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.22-32, March 1992 [doi>10.1145/130616.130619]
• 9: Bjorn De Sutter , Bruno De Bus , Koen De Bosschere, Sifting out the mud: low level C++ code reuse, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 10: Bjorn De Sutter , Bruno De Bus , Koen De Bosschere , Saumya Debray, Combining Global Code and Data Compaction, Proceedings of the ACM SIGPLAN workshop on Languages, compilers and tools for embedded systems, p.29-38, August 2001, Snow Bird, Utah, United States
• 11: 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]
• 12: William S. Evans , Christopher W. Fraser, Bytecode compression via profiled grammar rewriting, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.148-155, June 2001, Snowbird, Utah, 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: C. Fraser and T. Proebsting. Custom instruction sets for code compression. http://research.microsoft.com/~toddpro, 1995.
• 15: O. Kaser and C. Ramakrishnan. Evaluating inlining techniques. Computer Languages, 24:55--72, 1998.
• 16: Raghavan Komondoor , Susan Horwitz, Using Slicing to Identify Duplication in Source Code, Proceedings of the 8th International Symposium on Static Analysis, p.40-56, July 16-18, 2001
• 17: Jens Krinke, Identifying Similar Code with Program Dependence Graphs, Proceedings of the Eighth Working Conference on Reverse Engineering (WCRE'01), p.301, October 02-05, 2001
• 18: Rainer Leupers , Peter Marwedel, Function inlining under code size constraints for embedded processors, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.253-256, November 07-11, 1999, San Jose, California, United States
• 19: Karl Pettis , Robert C. Hansen, Profile guided code positioning, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.16-27, June 1990, White Plains, New York, United States
• 20: http://www.spec.org.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

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

  E. Data
  E.4 CODING AND INFORMATION THEORY

General Terms:
Experimentation, Performance

Keywords:
code abstraction, code compaction, performance