Speaker: Karl Lieberherr PRL/CCIS/Northeastern University
Caches can be used to avoid running the same intermediate computation more than once, to speed up subsequent computations, and to reorganize computations by precomputing and storing certain intermediate computations, etc. All these techniques can lead to improved asymptotic runtime complexity of programs or to reduced constant factors.
There are two main drawbacks to expressing cache-based optimization aspects in AspectJ-like general purpose aspect-oriented programming languages, reduced safety and low-level of abstraction. In this paper we propose an AspectJ extension for expressing cache-based optimization aspects more safely at a higher level of abstraction.
We illustrate the language with well-known examples: Dijkstra's shortest path algorithm, topological ordering and the closest pair algorithm. We noticed that in algorithm textbooks a clean but not so efficient algorithm description is followed by an implementation paragraph which refines the algorithm into an efficient implementation. Our cache-based optimization aspects formalize the "implementation paragraphs" by expressing them in a programming language. We hope that our new language will encourage software developers to think more systematically about how to speedup their software while keeping it easy to read and understand.
Supported by Novartis.