Profile-guided meta-programming

ABSTRACT

Contemporary compiler systems such as GCC, .NET, and LLVM incorporate profile-guided optimizations (PGOs) on low-level intermediate code and basic blocks, with impressive results over purely static heuristics. Recent work shows that profile information is also useful for performing source-to-source optimizations via meta-programming. For example, using profiling information to inform decisions about data structures and algorithms can potentially lead to asymptotic improvements in performance. We present a design for profile-guided meta-programming in a general-purpose meta-programming system. Our design is parametric over the particular profiler and meta-programming system. We implement this design in two different meta-programming systems---the syntactic extensions systems of Chez Scheme and Racket---and provide several profile-guided meta-programs as usability case studies.

References

1. Matthew Arnold, Stephen Fink, Vivek Sarkar, and Peter F. Sweeney. A Comparative Study of Static and Profilebased Heuristics for Inlining. In Proc. of the ACM SIGPLAN Workshop on Dynamic and Adaptive Compilation and Optimization (DYNAMO), 2000. http://doi.acm.org/ 10.1145/351397.351416
2. Thomas Ball and James R. Larus. Optimally Profiling and Tracing Programs. ACM Transactions on Programming Languages and Systems (TOPLAS) 16(4), pp. 1319–1360, 1994. http://doi.acm.org/10.1145/183432.183527
3. Eli Barzilay and John Clements. Laziness Without All the Hard Work: Combining Lazy and Strict Languages for Teaching. In Proc. of the Workshop on Functional and Declarative Programming in Education (FDPE), 2005. http://doi. acm.org/10.1145/1085114.1085118
4. Robert G. Burger and R. Kent Dybvig. An infrastructure for profile-driven dynamic recompilation. In Proc. of the International Conference on Computer Languages (ICCL), 1998. http://dx.doi.org/10.1109/ICCL.1998.
5. 674174
6. Eugene Burmako. Scala Macros: Let Our Powers Combine!: On How Rich Syntax and Static Types Work with Metaprogramming. In Proc. of the Workshop on Scala (SCALA), 2013. http://doi.acm.org/10.1145/2489837.
7. 2489840
8. Deheo Chen, Neil Vachharajani, Robert Hundt, Shih-wei Liao, Vinodha Ramasamy, Paul Yuan, Wenguang Chen, and Weimin Zheng. Taming Hardware Event Samples for FDO Compilation. In Proc. of the IEEE/ACM International Symposium on Code Generation and Optimization (CGO), 2010. http://doi.acm.org/10.1145/ 1772954.1772963
9. Hu Chen, Wenguang Chen, Jian Huang, Bob Robert, and H. Kuhn. MPIPP: An Automatic Profile-guided Parallel Process Placement Toolset for SMP Clusters and Multiclusters. In Proc. of the International Conference on Supercomputing (ICS), 2006. http://doi.acm.org/10.1145/ 1183401.1183451
10. Wen-ke Chen, Sanjay Bhansali, Trishul Chilimbi, Xiaofeng Gao, and Weihaw Chuang. Profile-guided Proactive Garbage Collection for Locality Optimization. In Proc. of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2006. http://doi.acm. org/10.1145/1133981.1134021
11. B. Dawes and D. Abrahams. Boost C++ Libraries. 2009. http://www.boost.org
12. Saumya Debray and William Evans. Profile-guided Code Compression. In Proc. of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2002. http://doi.acm.org/10.1145/ 512529.512542
13. R. Kent Dybvig. Chez Scheme Version 8 User’s Guide. 8.4 edition. Cadence Research Systems, 2011. http://www. scheme.com/csug8
14. R. Kent Dybvig, Robert Hieb, and Carl Bruggeman. Syntactic Abstraction in Scheme. LISP and Symbolic Computation 5(4), pp. 295–326, 1993. http://dx.doi.org/10. 1007/BF01806308
15. Sebastian Erdweg, Tillmann Rendel, Christian Kästner, and Klaus Ostermann. SugarJ: Library-based Syntactic Language Extensibility. In Proc. of the ACM International Conference on Object Oriented Programming Systems Languages and Applications (OOPSLA), 2011. http://doi.acm.org/ 10.1145/2048066.2048099
16. Andrew Farmer, Andy Gill, Ed Komp, and Neil Sculthorpe. The HERMIT in the Machine: A Plugin for the Interactive Transformation of GHC Core Language Programs. In Proc. of the ACM SIGPLAN Haskell Symposium (Haskell), 2012. http://doi.acm.org/10. 1145/2364506.2364508
17. Matthew Flatt and PLT. Reference: Racket. PLT Inc., PLTTR-2010-1, 2010. http://racket-lang.org/tr1/
18. Michael Furr, Jong-hoon (David) An, and Jeffrey S. Foster. Profile-guided Static Typing for Dynamic Scripting Languages. In Proc. of the ACM SIGPLAN Conference on Object Oriented Programming Systems Languages and Applications (OOPSLA), 2009. http://doi.acm.org/10. 1145/1640089.1640110
19. David Grove, Jeffrey Dean, Charles Garrett, and Craig Chambers. Profile-guided receiver class prediction. In Proc. of the ACM SIGPLAN Conference on Objectoriented Programming Systems, Languages, and Applications (OOPSLA), 1995. http://doi.acm.org/10.1145/ 217838.217848
20. Rajiv Gupta, Eduard Mehofer, and Youtao Zhang. Profile Guided Code Optimization. 2002.
21. Peter Hawkins, Alex Aiken, Kathleen Fisher, Martin Rinard, and Mooly Sagiv. Data Representation Synthesis. In Proc. of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2011. http://doi. acm.org/10.1145/1993498.1993504
22. Peter Hawkins, Alex Aiken, Kathleen Fisher, Martin Rinard, and Mooly Sagiv. Concurrent Data Representation Synthesis. In Proc. of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2012. http: //doi.acm.org/10.1145/2254064.2254114
23. Urs Hölzle and David Ungar. Optimizing Dynamicallydispatched Calls with Run-time Type Feedback. In Proc. of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 1994. http://doi. acm.org/10.1145/178243.178478
24. Kingshuk Karuri, Mohammad Abdullah Al Faruque, Stefan Kraemer, Rainer Leupers, Gerd Ascheid, and Heinrich Meyr. Fine-grained application source code profiling for ASIP design. In Proc. of the Design Automation Conference (DAC), 2005. http://doi.acm.org/10.1145/ 1065579.1065666
25. Andrew W. Keep and R. Kent Dybvig. A Nanopass Framework for Commercial Compiler Development. In Proc. of the ACM SIGPLAN International Conference on Functional Programming (ICFP), 2013. http://doi.acm.org/10. 1145/2500365.2500618
26. Oleg Kiselyov. The Design and Implementation of BER MetaOCaml. Functional and Logic Programming 8475, pp. 86–102, 2014. http://dx.doi.org/10. 1007/978-3-319-07151-0_6
27. Chris Lattner and Vikram Adve. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. In Proc. of the IEEE/ACM International Symposium on Code Generation and Optimization (CGO), 2004. http: //dx.doi.org/10.1109/CGO.2004.1281665
28. Chris Arthur Lattner. LLVM: An Infrastructure for Multi-Stage Optimization. Master dissertation, University of Illinois, 2002.
29. Lixia Liu and Silvius Rus. Perflint: A Context Sensitive Performance Advisor for C++ Programs. In Proc. of the IEEE/ACM International Symposium on Code Generation and Optimization (CGO), 2009. http://dx.doi.org/ 10.1109/CGO.2009.36
30. Chi-Keung Luk, Robert Muth, Harish Patil, Richard Weiss, P. Geoffrey Lowney, and Robert Cohn. Profile-guided Post-link Stride Prefetching. In Proc. of the International Conference on Supercomputing (ICS), 2002. http://doi.acm.org/ 10.1145/514191.514217
31. Martin Odersky, Philippe Altherr, Vincent Cremet, Burak Emir, Sebastian Maneth, Stéphane Micheloud, Nikolay Mihaylov, Michel Schinz, Erik Stenman, and Matthias Zenger. An Overview of the Scala Programming Language. EPFL Lausanne, IC/2004/64, 2004. http://infoscience. epfl.ch/record/52656?ln=en
32. Jon Rafkind and Matthew Flatt. Honu: Syntactic Extension for Algebraic Notation Through Enforestation. In Proc. of the International Conference on Generative Programming and Component Engineering (GPCE), 2012. http://doi. acm.org/10.1145/2371401.2371420
33. Tiark Rompf and Martin Odersky. Lightweight Modular Staging: A Pragmatic Approach to Runtime Code Generation and Compiled DSLs. In Proc. of the International Conference on Generative Programming and Component Engineering (GPCE), 2010. http://doi.acm.org/10.1145/ 1868294.1868314
34. Tim Sheard and Simon Peyton Jones. Template Metaprogramming for Haskell. In Proc. of the ACM SIGPLAN Workshop on Haskell (Haskell), 2002. http://doi.acm. org/10.1145/581690.581691
35. Arvind K. Sujeeth, Kevin J. Brown, Hyoukjoong Lee, Tiark Rompf, Hassan Chafi, Martin Odersky, and Kunle Olukotun. Delite: A Compiler Architecture for Performance-Oriented Embedded Domain-Specific Languages. ACM Transactions on Embedded Computing Systems (TECS) 13(4s), 2014. http://doi.acm.org/10.1145/2584665
36. Arvind K. Sujeeth, Austin Gibbons, Kevin J. Brown, HyoukJoong Lee, Tiark Rompf, Martin Odersky, and Kunle Olukotun. Forge: Generating a High Performance DSL Implementation from a Declarative Specification. In Proc. of the International Conference on Generative Programming: Concepts & Experiences (GPCE), 2013. http://doi.acm. org/10.1145/2517208.2517220
37. Walid Taha and Tim Sheard. MetaML and multi-stage programming with explicit annotations. Theoretical Computer Science 248(1–2), pp. 211–242, 2000. http://dx.doi. org/10.1016/S0304-3975(00)00053-0
38. Sam Tobin-Hochstadt and Matthias Felleisen. The Design and Implementation of Typed Scheme. In Proc. of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), 2008. http://doi.acm.org/ 10.1145/1328438.1328486
39. Sam Tobin-Hochstadt, Vincent St-Amour, Ryan Culpepper, Matthew Flatt, and Matthias Felleisen. Languages As Libraries. In Proc. of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2011. http://doi.acm.org/10.1145/ 1993498.1993514

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers

    • General programming languages

      • Language features