research-article

Profile-guided meta-programming

Authors:

William J. Bowman,

Vincent St-Amour,

R. Kent DybvigAuthors Info & Claims

PLDI '15: Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 403 - 412

https://doi.org/10.1145/2737924.2737990

Published: 03 June 2015 Publication History

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.

Supplementary Material

Auxiliary Archive (p403-bowman-s.zip)

An archive of all publically available source materials at the date of publication. This includes the Racket implementation and case studies discussed in the paper, but not the Chez Scheme implementations.

Download
56.64 KB

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

Digital Library

[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

Digital Library

[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

Digital Library

[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.

Digital Library

[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.

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

Cited By

Flatt MAllred TAngle NDe Gabrielle SFindler RFirth JGopinathan KGreenman BKasivajhula SKnauth AMcCarthy JPhillips SPorncharoenwase SSøgaard JTobin-Hochstadt S(2023)Rhombus: A New Spin on Macros without All the ParenthesesProceedings of the ACM on Programming Languages10.1145/36228187:OOPSLA2(574-603)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622818
Gottschall BEeckhout LJahre M(2021)TIP: Time-Proportional Instruction ProfilingMICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3466752.3480058(15-27)Online publication date: 18-Oct-2021
https://dl.acm.org/doi/10.1145/3466752.3480058
Hao MXu BLiang JZhang BYin X(2020)Chinese Short Text Classification with Mutual-Attention Convolutional Neural NetworksACM Transactions on Asian and Low-Resource Language Information Processing10.1145/338897019:5(1-13)Online publication date: 4-Aug-2020
https://dl.acm.org/doi/10.1145/3388970
Show More Cited By

Index Terms

Profile-guided meta-programming
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language features

Recommendations

Profile-guided meta-programming
PLDI '15

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 ...
Directly reflective meta-programming

Existing meta-programming languages operate on encodings of programs as data. This paper presents a new meta-programming language, based on an untyped lambda calculus, in which structurally reflective programming is supported directly, without any ...
Leveraging .NET meta-programming components from F#: integrated queries and interoperable heterogeneous execution
ML '06: Proceedings of the 2006 workshop on ML

Language-integrated meta-programming and extensible compilation have been recurring themes of programming languages since the invention of LISP. A recent real-world application of these techniques is the use of small meta-programs to specify database ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '15: Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation

June 2015

630 pages

ISBN:9781450334686

DOI:10.1145/2737924

General Chair:
David Grove
IBM Research, USA
,
Program Chair:
Steve Blackburn
Australian National University, Australia

ACM SIGPLAN Notices Volume 50, Issue 6
PLDI '15
June 2015
630 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2813885
Editor:
Andy Gill
University of Kansas, Lawrence, KS
Issue’s Table of Contents

Copyright © 2015 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].

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 June 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PLDI '15

Sponsor:

SIGPLAN

PLDI '15: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 13 - 17, 2015

OR, Portland, USA

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
426
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)5

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Flatt MAllred TAngle NDe Gabrielle SFindler RFirth JGopinathan KGreenman BKasivajhula SKnauth AMcCarthy JPhillips SPorncharoenwase SSøgaard JTobin-Hochstadt S(2023)Rhombus: A New Spin on Macros without All the ParenthesesProceedings of the ACM on Programming Languages10.1145/36228187:OOPSLA2(574-603)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622818
Gottschall BEeckhout LJahre M(2021)TIP: Time-Proportional Instruction ProfilingMICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3466752.3480058(15-27)Online publication date: 18-Oct-2021
https://dl.acm.org/doi/10.1145/3466752.3480058
Hao MXu BLiang JZhang BYin X(2020)Chinese Short Text Classification with Mutual-Attention Convolutional Neural NetworksACM Transactions on Asian and Low-Resource Language Information Processing10.1145/338897019:5(1-13)Online publication date: 4-Aug-2020
https://dl.acm.org/doi/10.1145/3388970
Concas FXu PHoque MLu JTarkoma S(2020)Multiple Set Matching with Bloom Matrix and Bloom VectorACM Transactions on Knowledge Discovery from Data10.1145/337240914:2(1-21)Online publication date: 9-Feb-2020
https://dl.acm.org/doi/10.1145/3372409
Lin BLuo WLuo ZWang BDeng SYin JZhou M(2020)Bradykinesia Recognition in Parkinson’s Disease via Single RGB VideoACM Transactions on Knowledge Discovery from Data10.1145/336943814:2(1-19)Online publication date: 9-Feb-2020
https://dl.acm.org/doi/10.1145/3369438
Chiariotti FPielli CLaurenti NZanella AZorzi M(2019)A Game-Theoretic Analysis of Energy-Depleting Jamming Attacks with a Learning CounterstrategyACM Transactions on Sensor Networks10.1145/336583816:1(1-25)Online publication date: 22-Nov-2019
https://dl.acm.org/doi/10.1145/3365838
Dimri ASingh HAggarwal NRaman BRamakrishnan KBansal D(2019)BaroSenseACM Transactions on Sensor Networks10.1145/336469716:1(1-24)Online publication date: 11-Nov-2019
https://dl.acm.org/doi/10.1145/3364697
Istomin TIova OPicco GKiraly C(2019)Route or Flood? Reliable and Efficient Support for Downward Traffic in RPLACM Transactions on Sensor Networks10.1145/335599716:1(1-41)Online publication date: 18-Oct-2019
https://dl.acm.org/doi/10.1145/3355997
Fard ACunningham S(2019)Assessing the Readiness of Academia in the Topic of False and Unverified InformationJournal of Data and Information Quality10.1145/331378811:4(1-27)Online publication date: 21-Aug-2019
https://dl.acm.org/doi/10.1145/3313788
Burckhardt SCoppieters T(2018)Reactive caching for composed services: polling at the speed of pushProceedings of the ACM on Programming Languages10.1145/32765222:OOPSLA(1-28)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276522
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