More Web Proxy on the site http://driver.im/

research-article

Reify your collection queries for modularity and speed!

Authors:

Paolo G. Giarrusso,

Klaus Ostermann,

Michael Eichberg,

Tillmann Rendel,

Christian KästnerAuthors Info & Claims

AOSD '13: Proceedings of the 12th annual international conference on Aspect-oriented software development

Pages 1 - 12

https://doi.org/10.1145/2451436.2451438

Published: 24 March 2013 Publication History

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.

References

[1]

S. Ackermann, V. Jovanovic, T. Rompf, and M. Odersky. Jet: An embedded DSL for high performance big data processing. In Int'l Workshop on End-to-end Management of Big Data (BigData), 2012.

[2]

G. M. Bierman, E. Meijer, and M. Torgersen. Lost in translation: formalizing proposed extensions to C#. In OOPSLA, pages 479--498. ACM, 2007.

Digital Library

[3]

C. Chambers, A. Raniwala, F. Perry, S. Adams, R. R. Henry, R. Bradshaw, and N. Weizenbaum. FlumeJava: easy, efficient data-parallel pipelines. In PLDI, pages 363--375. ACM, 2010.

Digital Library

[4]

O. Eini. The pain of implementing LINQ providers. Commun. ACM, 54(8):55--61, 2011.

Digital Library

[5]

C. Elliott, S. Finne, and O. de Moor. Compiling embedded languages. JFP, 13(2):455--481, 2003.

Digital Library

[6]

L. Fegaras and D. Maier. Optimizing object queries using an effective calculus. ACM Trans. Database Systems (TODS), 25:457--516, 2000.

Digital Library

[7]

P. J. Fleming and J. J. Wallace. How not to lie with statistics: the correct way to summarize benchmark results. Commun. ACM, 29(3):218--221, Mar. 1986.

Digital Library

[8]

M. Garcia, A. Izmaylova, and S. Schupp. Extending Scala with database query capability. Journal of Object Technology, 9(4):45--68, 2010.

[9]

A. Georges, D. Buytaert, and L. Eeckhout. Statistically rigorous Java performance evaluation. In OOPSLA, pages 57--76. ACM, 2007.

Digital Library

[10]

P. G. Giarrusso, K. Ostermann, M. Eichberg, R. Mitschke, T. Rendel, and C. Kästner. Reify your collection queries for modularity and speed! CoRR, abs/1210.6284, 2012. URL http://arxiv.org/abs/1210.6284

[11]

A. Gill, J. Launchbury, and S. L. Peyton Jones. A short cut to deforestation. In FPCA, pages 223--232. ACM, 1993.

Digital Library

[12]

D. Gluche, T. Grust, C. Mainberger, and M. Scholl. Incremental updates for materialized OQL views. In Deductive and Object-Oriented Databases, volume 1341 of LNCS, pages 52--66. Springer, 1997.

Digital Library

[13]

T. Grust. Comprehending queries. PhD thesis, University of Konstanz, 1999.

[14]

T. Grust and M. H. Scholl. How to comprehend queries functionally. Journal of Intelligent Information Systems, 12:191--218, 1999.

Digital Library

[15]

T. Grust, M. Mayr, J. Rittinger, and T. Schreiber. FERRY: database-supported program execution. In Proc. Int'l SIGMOD Conf. on Management of Data (SIGMOD), pages 1063--1066. ACM, 2009.

Digital Library

[16]

E. Hajiyev, M. Verbaere, and O. de Moor. CodeQuest: Scalable source code queries with Datalog. In ECOOP, pages 2--27. Springer, 2006.

Digital Library

[17]

D. Hovemeyer and W. Pugh. Finding bugs is easy. SIGPLAN Notices, 39(12):92--106, 2004.

Digital Library

[18]

G. Kiczales, J. Lamping, A. Menhdhekar, C. Maeda, C. Lopes, J.-M. Loingtier, and J. Irwin. Aspect-orientedprogramming. In ECOOP, pages 220--242, 1997.

[19]

D. Leijen and E. Meijer. Domain specific embedded compilers. In DSL, pages 109--122. ACM, 1999.

Digital Library

[20]

E. Meijer, B. Beckman, and G. Bierman. LINQ: reconciling objects, relations and XML in the .NET framework. In Proc. Int'l SIGMOD Conf. on Management of Data (SIGMOD), page 706. ACM, 2006.

Digital Library

[21]

S. S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997. ISBN 1-55860-320-4.

Digital Library

[22]

M. Odersky and A. Moors. Fighting bit rot with types (experience report: Scala collections). In IARCS Conf. Foundations of Software Technology and Theoretical Computer Science, volume 4, pages 427--451, 2009.

[23]

M. Odersky, L. Spoon, and B. Venners. Programming in Scala. Artima Inc, 2 edition, 2011.

[24]

S. Peyton Jones and S. Marlow. Secrets of the Glasgow Haskell Compiler inliner. JFP, 12(4-5):393--434, 2002.

Digital Library

[25]

F. Pfenning and C. Elliot. Higher-order abstract syntax. In PLDI, pages 199--208. ACM, 1988.

Digital Library

[26]

T. Rompf and M. Odersky. Lightweight modular staging: a pragmatic approach to runtime code generation and compiled DSLs. In GPCE, pages 127--136. ACM, 2010.

Digital Library

[27]

T. Rompf, A. K. Sujeeth, H. Lee, K. J. Brown, H. Cha, M. Odersky, and K. Olukotun. Building-blocks for performance oriented DSLs. In DSL, pages 93--117, 2011.

[28]

T. Rompf, A. K. Sujeeth, N. Amin, K. J. Brown, V. Jovanovic, H. Lee, M. Jonnalagedda, K. Olukotun, and M. Odersky. Optimizing data structures in high-level programs: new directions for extensible compilers based on staging. In POPL, pages 497--510. ACM, 2013.

Digital Library

[29]

D. Spiewak and T. Zhao. ScalaQL: Language-integrated database queries for Scala. In Proc. Conf. Software Language Engineering (SLE), 2009.

Digital Library

[30]

M. Stonebraker, S. Madden, D. J. Abadi, S. Harizopoulos, N. Hachem, and P. Helland. The end of an architectural era: (it's time for a complete rewrite). In Proc. Int'l Conf. Very Large Data Bases (VLDB), pages 1150--1160. VLDB Endowment, 2007.

Digital Library

[31]

J. Vitek and T. Kalibera. Repeatability, reproducibility, and rigor in systems research. In Proc. Int'l Conf. Embedded Software (EMSOFT), pages 33--38. ACM, 2011.

Digital Library

[32]

P. Wegrzynowicz and K. Stencel. The good, the bad, and the ugly: three ways to use a semantic code query system. In OOPSLA, pages 821--822. ACM, 2009.

Digital Library

[33]

D. Willis, D. Pearce, and J. Noble. Efficient object querying for Java. In ECOOP, pages 28--49. Springer, 2006.

Digital Library

[34]

D. Willis, D. J. Pearce, and J. Noble. Caching and incrementalisation in the Java Query Language. In OOPSLA, pages 1--18. ACM, 2008.

Digital Library

[35]

Y. Yu, M. Isard, D. Fetterly, M. Budiu, U. Erlingsson, P. K. Gunda, and J. Currey. DryadLINQ: a system for general-purpose distributed data-parallel computing using a high-level language. In Proc. Conf. Operating systems design and implementation, OSDI'08, pages 1--14. USENIX Association, 2008.

Digital Library

Cited By

Hinkel GHeinrich RReussner R(2019)An extensible approach to implicit incremental model analysesSoftware and Systems Modeling (SoSyM)10.1007/s10270-019-00719-y18:5(3151-3187)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s10270-019-00719-y
Alcocer JDenker MBergel AAcurana YLaval JEtien A(2016)Dynamically Composing Collection Operations through Collection PromisesProceedings of the 11th edition of the International Workshop on Smalltalk Technologies10.1145/2991041.2991049(1-5)Online publication date: 23-Aug-2016
https://dl.acm.org/doi/10.1145/2991041.2991049
Cazzola WShaqiri AFuentes LBatory DCzarnecki K(2016)Modularity and optimization in synergyProceedings of the 15th International Conference on Modularity10.1145/2889443.2889445(70-81)Online publication date: 14-Mar-2016
https://dl.acm.org/doi/10.1145/2889443.2889445
Show More Cited By

Index Terms

Reify your collection queries for modularity and speed!
1. Information systems
  1. Data management systems
    1. Query languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Functional languages

Recommendations

Reifying and optimizing collection queries for modularity
SPLASH '12: Proceedings of the 3rd annual conference on Systems, programming, and applications: software for humanity

Conventional collection libraries do not perform automatic collection-specific optimizations. Instead, performance-critical code using collections must be hand-optimized, leading to non-modular, brittle, and redundant code.

We propose SQuOpt, the Scala ...
Reifying and optimizing collection queries for modularity
SPLASH '12: Proceedings of the 3rd annual conference on Systems, programming, and applications: software for humanity

Conventional collection libraries do not perform automatic collection-specific optimizations. Instead, performance-critical code using collections must be hand-optimized, leading to non-modular, brittle, and redundant code.

We propose SQuOpt, the Scala ...
Eclipse OMR garbage collection for tracing JIT-based virtual machines
CASCON '21: Proceedings of the 31st Annual International Conference on Computer Science and Software Engineering

The RPython framework provides a toolchain with reusable tracing Just-In-Time (JIT) compilation, and garbage collection (GC) that Virtual Machines (VMs) written in it inherit. This toolchain has provided an efficient way over the years for implementing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

AOSD '13: Proceedings of the 12th annual international conference on Aspect-oriented software development

March 2013

232 pages

ISBN:9781450317665

DOI:10.1145/2451436

General Chair:
Hidehiko Masuhara
The University of Tokyo, Japan
,
Program Chairs:
Jörg Kienzle
McGill University, Canada
,
Elisa Baniassad
Australian National University, Australia
,
David H. Lorenz
The Open University of Israel, Israel

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

AOSA: Aspect-Oriented Software Association

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 March 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

AOSD '13

Sponsor:

AOSA

AOSD '13: Aspect-Oriented Software Development

March 24 - 29, 2013

Fukuoka, Japan

Acceptance Rates

Overall Acceptance Rate 41 of 139 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
162
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hinkel GHeinrich RReussner R(2019)An extensible approach to implicit incremental model analysesSoftware and Systems Modeling (SoSyM)10.1007/s10270-019-00719-y18:5(3151-3187)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s10270-019-00719-y
Alcocer JDenker MBergel AAcurana YLaval JEtien A(2016)Dynamically Composing Collection Operations through Collection PromisesProceedings of the 11th edition of the International Workshop on Smalltalk Technologies10.1145/2991041.2991049(1-5)Online publication date: 23-Aug-2016
https://dl.acm.org/doi/10.1145/2991041.2991049
Cazzola WShaqiri AFuentes LBatory DCzarnecki K(2016)Modularity and optimization in synergyProceedings of the 15th International Conference on Modularity10.1145/2889443.2889445(70-81)Online publication date: 14-Mar-2016
https://dl.acm.org/doi/10.1145/2889443.2889445
Cazzola WVacchi E(2016)Language components for modular DSLs using traitsComputer Languages, Systems and Structures10.1016/j.cl.2015.12.00145:C(16-34)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1016/j.cl.2015.12.001
Scherr MChiba S(2015)Almost first-class language embedding: taming staged embedded DSLsACM SIGPLAN Notices10.1145/2936314.281421751:3(21-30)Online publication date: 26-Oct-2015
https://dl.acm.org/doi/10.1145/2936314.2814217
Scherr MChiba SKästner CGokhālé A(2015)Almost first-class language embedding: taming staged embedded DSLsProceedings of the 2015 ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/2814204.2814217(21-30)Online publication date: 26-Oct-2015
https://dl.acm.org/doi/10.1145/2814204.2814217
Mitschke RErdweg SKöhler MMezini MSalvaneschi G(2014)i3QLACM SIGPLAN Notices10.1145/2714064.266024249:10(417-432)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2714064.2660242
Cai YGiarrusso PRendel TOstermann K(2014)A theory of changes for higher-order languagesACM SIGPLAN Notices10.1145/2666356.259430449:6(145-155)Online publication date: 9-Jun-2014
https://dl.acm.org/doi/10.1145/2666356.2594304
Mitschke RErdweg SKöhler MMezini MSalvaneschi GBlack AMillstein T(2014)i3QLProceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications10.1145/2660193.2660242(417-432)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2660193.2660242
Eichberg MHermann BArzt SSantelices R(2014)A software product line for static analysesProceedings of the 3rd ACM SIGPLAN International Workshop on the State of the Art in Java Program Analysis10.1145/2614628.2614630(1-6)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2614628.2614630
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents