Google Research

Optimizing Programs with Intended Semantics

Proceedings of OOPSLA, ACM Press (2009) (to appear)


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 over 50%.

To make specifying the intended semantics practical, IOpt communicates with the programmer. IOpt identifies which assumptions the programmer textit{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. Our case studies show that the programmer just needs to add a few assumptions to realize the 50% speedup.

Research Areas

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work