Optimizing programs with intended semantics

ABSTRACT

Modern object-oriented languages have complex features that cause programmers to overspecify their programs. This overspecification hinders automatic optimizers, since they must preserve the overspecified semantics. If an optimizer knew which semantics the programmer intended, it could do a better job.

Making a programmer clarify his intentions by placing assumptions into the program is rarely practical. This is because the programmer does not know which parts of the programs' overspecified semantics hinder the optimizer. Therefore, the programmer has to guess which assumption to add. Since the programmer can add many different assumptions to a large program, he will need to place many such assumptions before he guesses right and helps the optimizer.

We present IOpt, a practical optimizer that uses a specification of the programmers' intended semantics to enable additional optimizations. That way, our optimizer can significantly improve the performance of a program. We present case studies in which we use IOpt to speed up two programs by a factor of 2.

To make specifying the intended semantics practical, IOpt communicates with the programmer. IOpt identifies which assumptions the programmer should place, and where he should place them. IOpt ranks each assumption by (i) the likelyhood that the assumption conforms to the programmers' intended semantics and (ii) how much the assumption will help IOpt improve the programs' performance. IOpt proposes ranked assumptions to the programmer, who just picks those that conform to his intended semantics.With this approach, IOpt keeps the programmers' specification burden low. In our case studies, programmers had to add just a few assumptions to realize significant performance speedups.

REFERENCES

• 1: Keith D. Cooper, MaryW. Hall, Robert T. Hood, Ken Kennedy, Kathryn S. McKinley, John M. Mellor-Crummey, Linda Torczon, and Scott K.Warren. The ParaScope parallel programming environment. Proceedings of the IEEE, 81(2):244--263, 1993.
• 2: Christian Doerr, Douglas Sicker, and Dirk Grunwald. What a cognitive radio network can learn from a school of fish. Third Annual Wireless Internet Conference (WICON), 2007.
• 3: Joseph Hummel, Ana Azevedo, David Kolson, and Alexandru Nicolau. Annotating the Java bytecodes in support of optimization. Concurrency: Practice and Experience, 9(11):1003--1016, 1997.
• 4: Shih-Wei Liao, Amer Diwan, Robert P. Bosch Jr., Anwar M. Ghuloum, and Monica S. Lam. SUIF explorer: An interactive and interprocedural parallelizer. In Principles Practice of Parallel Programming, pages 37--48, 1999.
• 5: I. Pechtchanski and V. Sarkar. Immutability specification and its applications, 2002.
• 6: Patrice Pominville, Feng Qian, Raja Vallee-Rai, Laurie Hendren, and Clark Verbrugge. A framework for optimizing Java using attributes. In R. Wilhelm, editor, CC 2001, volume 2027 of Lecture Notes in Computer Science, pages 334+, 2001.
• 7: Standard performance evaluation corporation. SPECjbb2000 (Java Business Benchmark). http://www.spec.org/jbb2000.
• 8: Standard performance evaluation corporation. SPECjvm98 benchmarks. http://www.spec.org/jvm98.
• 9: Daniel von Dincklage and Amer Diwan. Explaining failures of program analyses. In PLDI '08: Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, pages 260--269, New York, NY, USA, 2008. ACM.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.6 Programming Environments

General Terms:
Performance

Keywords:
intended semantics, optimization