Join us on:

Language Implementation

Session Chair: Brent Hailpern, IBM
Optimizing Programs with Intended Semantics
Daniel Von Dincklage, Google Inc.
Amer Diwan, University of Colorado at Boulder

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 blindly 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, an 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. To optimize a program, IOpt identifies which assumptions the programmer should place, and where he should place them. IOpt ranks each assumption by (i) the likelihood 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' assumption burden low. Our case studies show that the programmer just needs to add a few assumptions to realize the 50% speedup.

Minimizing Dependencies within Generic Classes for Faster and Smaller Programs
Dan Tsafrir, IBM T.J. Watson Research Center
Robert W. Wisniewski, IBM T.J. Watson Research Center
David F. Bacon, IBM T.J. Watson Research Center
Bjarne Stroustrup, Texas A&M University

Generic classes can be used to improve performance by allowing compile-time polymorphism. But the applicability of compile-time polymorphism is narrower than that of runtime polymorphism, and it might bloat the object code. We advocate a programming principle whereby a generic class should be implemented in a way that minimizes the dependencies between its members (nested types, methods) and its generic type parameters. Conforming to this principle (1) reduces the bloat and (2) gives rise to a previously unconceived manner of using the language that expands the applicability of compile-time polymorphism to a wider range of problems. Our contribution is thus a programming technique that generates faster and smaller programs. We apply our ideas to GCC's STL containers and iterators, and we demonstrate notable speedups and reduction in object code size (real application runs 1.2x to 2.1x faster and STL code is 1x to 25x smaller). We conclude that standard generic APIs (like STL) should be amended to reflect the proposed principle in the interest of efficiency and compactness. Such modifications will not break old code, simply increase flexibility. Our findings apply to languages like C++, C#, and D, which realize generic programming through multiple instantiations.

Providing Rapid Feedback in Generated Modular Language Environments. Adding Error Recovery to Scannerless Generalized-LR Parsing
Lennart C. L. Kats, Delft University of Technology
Maartje De Jonge, Delft University of Technology
Emma Nilsson-Nyman, Lund University
Eelco Visser, Delft University of Technology

Integrated Development Environments (IDEs) increase programmer productivity, providing rapid, interactive feedback based on the syntax and semantics of a language. A heavy burden lies on developers of new languages to provide adequate IDE support. Code generation techniques provide a viable, efficient approach to semi-automatically produce IDE plugins. Key components for the realization of plugins are the language's grammar and parser. For embedded languages and language extensions, constituent IDE plugin modules and their grammars can be combined. Unlike conventional parsing algorithms, scannerless generalized-LR parsing supports the full set of context-free grammars, which is closed under composition, and hence can parse language embeddings and extensions composed from separate grammar modules. To apply this algorithm in an interactive environment, this paper introduces a novel error recovery mechanism, which allows it to be used with files with syntax errors — common in interactive editing. Error recovery is vital for providing rapid feedback in case of syntax errors, as most IDE services depend on the parser — from syntax highlighting to semantic analysis and cross-referencing. We base our approach on the principles of island grammars, and automatically generate new productions for existing grammars, making them more permissive of their inputs. To cope with the added complexity of these grammars, we adapt the parser to support backtracking. We evaluate the recovery quality and performance of our approach using a set of composed languages, based on Java and Stratego.

Please email any questions to . This e-mail address is being protected from spambots. You need JavaScript enabled to view it