Paper Info
Title
Reify your collection queries for modularity and speed!
Abstract
Modularity and efficiency are often contradicting requirements, such that programers have to trade one for the other. We analyze this dilemma in the context of programs operating on collections. Performance-critical code using collections need often to be hand-optimized, leading to non-modular, brittle, and redundant code. In principle, this dilemma could be avoided by automatic collection-specific optimizations, such as fusion of collection traversals, usage of indexing, or reordering of filters. Unfortunately, it is not obvious how to encode such optimizations in terms of ordinary collection APIs, because the program operating on the collections is not reified and hence cannot be analyzed. We propose SQuOpt, the Scala Query Optimizer--a deep embedding of the Scala collections API that allows such analyses and optimizations to be defined and executed within Scala, without relying on external tools or compiler extensions. SQuOpt provides the same "look and feel" (syntax and static typing guarantees) as the standard collections API. We evaluate SQuOpt by re-implementing several code analyses of the FindBugs tool using SQuOpt, show average speedups of 12x with a maximum of 12800x and hence demonstrate that SQuOpt can reconcile modularity and efficiency in real-world applications.
Year
DOI
Venue
2013
10.1145/2451436.2451438
aspect-oriented software development
Keywords
DocType
Volume
redundant code,performance-critical code,code analysis,program operating,ordinary collection apis,collection traversal,scala collections api,scala query optimizer,automatic collection-specific optimizations,standard collection,collection query,modularity,query languages,optimization
Conference
abs/1210.6284
ISSN
Citations 
PageRank 
Proceedings of the 12th annual international conference on Aspect-oriented software development (AOSD '13), 2013. ACM, New York, NY, USA, 1-12
10
0.68
References 
Authors
24
6
Name
Order
Citations
PageRank
Paolo G. Giarrusso12719.97
Klaus Ostermann245723.97
Michael Eichberg334828.34
Ralf Mitschke4905.18
Tillmann Rendel539216.15
Christian Kästner63591135.92