Parallel incremental whole-program optimizations for Scala.js
Abstract
Whole-program optimizations are powerful tools that can dramatically improve performance, size and other aspects of programs. Because they depend on global knowledge, they must typically be reapplied to the whole program when small changes are made, which makes them too slow for the development cycle. This is an issue for some environments that require, or benefit a lot from, whole-program optimizations, such as compilation to JavaScript or to the Dalvik VM, because their development cycle is slowed down either by the lack of optimizations, or by the time spent on applying them.
We present a new approach to designing incremental whole-program optimizers for object-oriented and functional languages: when part of a program changes, only the portions affected by the changes are reoptimized. An incremental optimizer using this approach for Scala.js, the Scala to JavaScript compiler, demonstrates speedups from 10x to 100x compared to its batch version. As a result, the optimizer's running time becomes insignificant compared to separate compilation, making it fit for use on every compilation run during the development cycle. We also show how to parallelize the incremental algorithm to take advantage of multicore hardware.
References
[1]
Octane, the JavaScript benchmark suite for the modern web, 2015. {Online; accessed 30-November-2015}.
[2]
M. Burke and L. Torczon. Interprocedural optimization: Eliminating unnecessary recompilation. ACM Trans. Program. Lang. Syst., 15(3):367–399, July 1993.
[3]
E. Burmako. Scala macros: Let our powers combine!: On how rich syntax and static types work with metaprogramming. In Proceedings of the 4th Workshop on Scala, SCALA ’13, pages 3:1–3:10, New York, NY, USA, 2013.
[4]
C. Chambers, J. Dean, and D. Grove. A framework for selective recompilation in the presence of complex intermodule dependencies. In Proceedings of the 17th International Conference on Software Engineering, ICSE ’95, pages 221–230, New York, NY, USA, 1995.
[5]
K. D. Cooper, K. Kennedy, and L. Torczon. Interprocedural optimization: Eliminating unnecessary recompilation. In Proceedings of the 1986 SIGPLAN Symposium on Compiler Construction, SIGPLAN ’86, pages 58–67, New York, NY, USA, 1986.
[6]
J. A. Dean. Whole-program Optimization of Object-oriented Languages. PhD thesis, 1996. AAI9716832.
[7]
S. Doeraene, T. Schlatter, and N. Stucki. Scala.js, 2015.
[8]
I. Lakhin. Papa carlo, 2015.
[9]
H. Li. Autowire, 2015.
[10]
Y. Lu, L. Shang, X. Xie, and J. Xue. An incremental points-to analysis with CFL-reachability. In Proceedings of the 22Nd International Conference on Compiler Construction, CC’13, pages 61–81, Berlin, Heidelberg, 2013. Springer-Verlag.
[11]
H. Miller, P. Haller, E. Burmako, and M. Odersky. Instant pickles: Generating object-oriented pickler combinators for fast and extensible serialization. In Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA ’13, pages 183–202, New York, NY, USA, 2013.
[12]
L. L. Pollock and M. L. Soffa. Incremental compilation of optimized code. In Proceedings of the 12th ACM SIGACTSIGPLAN Symposium on Principles of Programming Languages, POPL ’85, pages 152–164, New York, NY, USA, 1985.
[13]
L. L. Pollock and M. L. Soffa. Incremental global reoptimization of programs. ACM Trans. Program. Lang. Syst., 14(2): 173–200, Apr. 1992.
[14]
A. Prokopec, N. G. Bronson, P. Bagwell, and M. Odersky. Concurrent tries with efficient non-blocking snapshots. In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’12, pages 151–160, New York, NY, USA, 2012.
[15]
D. Saha and C. R. Ramakrishnan. Incremental and demanddriven points-to analysis using logic programming. In Proceedings of the 7th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming, PPDP ’05, pages 117–128, New York, NY, USA, 2005.
[16]
A. Sewe, J. Jochem, and M. Mezini. Next in line, please!: Exploiting the indirect benefits of inlining by accurately predicting further inlining. In Proceedings of the Compilation of the Co-located Workshops on DSM’11, TMC’11, AGERE!’11, AOOPES’11, NEAT’11, & VMIL’11, SPLASH ’11 Workshops, pages 317–328, New York, NY, USA, 2011.
[17]
A. L. Souter and L. L. Pollock. Incremental call graph reanalysis for object-oriented software maintenance. In Proceedings of the IEEE International Conference on Software Maintenance (ICSM’01), ICSM ’01, pages 682–, Washington, DC, USA, 2001.
[18]
L. Stadler, T. Würthinger, and H. Mössenböck. Partial escape analysis and scalar replacement for Java. In Proceedings of Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO ’14, pages 165:165–165:174, New York, NY, USA, 2014.
[19]
F. Vivien and M. Rinard. Incrementalized pointer and escape analysis. In Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation, PLDI ’01, pages 35–46, New York, NY, USA, 2001.
[20]
J.-S. Yur, B. G. Ryder, W. A. Landi, and P. Stocks. Incremental analysis of side effects for C software system. In Proceedings of the 19th International Conference on Software Engineering, ICSE ’97, pages 422–432, New York, NY, USA, 1997.
Index Terms
- Parallel incremental whole-program optimizations for Scala.js
Recommendations
Parallel incremental whole-program optimizations for Scala.js
OOPSLA 2016: Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and ApplicationsWhole-program optimizations are powerful tools that can dramatically improve performance, size and other aspects of programs. Because they depend on global knowledge, they must typically be reapplied to the whole program when small changes are made, ...
Whole-program compilation in MLton
ML '06: Proceedings of the 2006 workshop on MLMLton is a stable, robust, widely ported, Standard ML (SML) compiler that generates efficient executables. Whole-program compilation is the key to MLton's success, significantly improving both correctness and efficiency. Whole-program compilation makes ...
Incremental whole program optimization and compilation
CGO '17: Proceedings of the 2017 International Symposium on Code Generation and OptimizationMost modern compilers for statically typed high level languages perform whole program optimization and compilation in order to generate highly optimized code. Whole program analysis and optimization has the advantage of providing the compiler with ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2016
915 pages
October 2016915 pages
Copyright © 2016 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 the author(s) 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].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 19 October 2016
Published in SIGPLAN Volume 51, Issue 10
Check for updates
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 210Total Downloads
- Downloads (Last 12 months)5
- Downloads (Last 6 weeks)0
Reflects downloads up to 22 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in