An Executable Semantics for Faster Development of Optimizing Python Compilers
Pages 15 - 28
Abstract
Python is a popular programming language whose performance is known to be uncompetitive in comparison to static languages such as C. Although significant efforts have already accelerated implementations of the language, more efficient ones are still required. The development of such optimized implementations is nevertheless hampered by its complex semantics and the lack of an official formal semantics. We address this issue by presenting an approach to define an executable semantics targeting the development of optimizing compilers. This executable semantics is written in a format that highlights type checks, primitive values boxing and unboxing, and function calls, which are all known sources of overhead. We also present semPy, a partial evaluator of our executable semantics that can be used to remove redundant operations when evaluating arithmetic operators. Finally, we present Zipi, a Python optimizing compiler prototype developed with the aid of semPy. On some tasks, Zipi displays performance competitive with that of state-of-the-art Python implementations.
References
[1]
Davide Ancona, Massimo Ancona, Antonio Cuni, and Nicholas D. Matsakis. 2007. RPython: A Step towards Reconciling Dynamically and Statically Typed OO Languages. In Proceedings of the 2007 Symposium on Dynamic Languages (DLS ’07). New York, NY, USA. 53–64. isbn:978-1-59593-868-8 https://doi.org/10.1145/1297081.1297091
[2]
Martin Bodin, Arthur Chargueraud, Daniele Filaretti, Philippa Gardner, Sergio Maffeis, Daiva Naudziuniene, Alan Schmitt, and Gareth Smith. 2014. A Trusted Mechanised JavaScript Specification. In Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’14). 87–100. isbn:9781450325448 https://doi.org/10.1145/2535838.2535876
[3]
Martin Bodin, Tomás Diaz, and Éric Tanter. 2020. A Trustworthy Mechanized Formalization of R. SIGPLAN Not., 53, 8 (2020), apr, 13–24. issn:0362-1340 https://doi.org/10.1145/3393673.3276946
[4]
Denis Bogdanas and Grigore Roşu. 2015. K-Java: A Complete Semantics of Java. SIGPLAN Not., 50, 1 (2015), jan, 445–456. issn:0362-1340 https://doi.org/10.1145/2775051.2676982
[5]
Carl Friedrich Bolz, Antonio Cuni, Maciej Fijalkowski, and Armin Rigo. 2009. Tracing the Meta-Level: PyPy’s Tracing JIT Compiler. In Proceedings of the 4th Workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems (ICOOOLPS ’09). 18–25. isbn:9781605585413 https://doi.org/10.1145/1565824.1565827
[6]
Dybvig, Kent. 2009. The Scheme Programming Language (fourth edition ed.). The MIT Press. isbn:978-0-262-51298-5 https://www.scheme.com/tspl4/
[7]
Chucky Ellison and Grigore Rosu. 2012. An Executable Formal Semantics of C with Applications. In Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’12). 533–544. isbn:9781450310833 https://doi.org/10.1145/2103656.2103719
[8]
Marc Feeley and Marc-André Bélanger. 2023. Forensics. https://github.com/udem-dlteam/forensics/
[9]
Marc Feeley and Marc-André Bélanger. 2023. Zipi Forensics. https://zipi-forensics.gambitscheme.org/
[10]
Feeley, Marc. 2023. Gambit. https://www.iro.umontreal.ca/ gambit/doc/gambit.pdf
[11]
Daniele Filaretti and Sergio Maffeis. 2014. An Executable Formal Semantics of PHP. In ECOOP 2014 – Object-Oriented Programming, Richard Jones (Ed.). 567–592. isbn:978-3-662-44202-9
[12]
Gouy, Isaac. 2023. The Computer Language Benchmarks Game. https://benchmarksgame-team.pages.debian.net/benchmarksgame/
[13]
Michael Greenberg and Austin J. Blatt. 2019. Executable Formal Semantics for the POSIX Shell. Proc. ACM Program. Lang., 4, POPL (2019), Article 43, dec, 30 pages. https://doi.org/10.1145/3371111
[14]
Mohamed Ismail and G. Suh. 2018. Quantitative Overhead Analysis for Python. In 2018 IEEE International Symposium on Workload Characterization (IISWC). Raleigh, NC, USA. 36–47. https://doi.org/10.1109/IISWC.2018.8573512
[15]
Olivier Melançon. 2022. Reusable Semantics for Implementation of Python Optimizing Compilers. https://papyrus.bib.umontreal.ca/xmlui/handle/1866/26538
[16]
Olivier Melançon. 2023. semPy. https://doi.org/10.1145/3580421
[17]
Raphaël Monat, Abdelraouf Ouadjaout, and Antoine Miné. 2020. Static Type Analysis by Abstract Interpretation of Python Programs. In 34th European Conference on Object-Oriented Programming (ECOOP 2020), Robert Hirschfeld and Tobias Pape (Eds.) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 166). Schloss Dagstuhl– Leibniz-Zentrum für Informatik, Dagstuhl, Germany. 17:1–17:29. isbn:978-3-95977-154-2 issn:1868-8969 https://doi.org/10.4230/LIPIcs.ECOOP.2020.17
[18]
Peter D. Mosses. 1975. Mathematical semantics and compiler generation. University of Oxford. https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.466424
[19]
Peter D. Mosses. 1996. Theory and Practice of Action Semantics. MFCS ’96, 1113, 37–61. isbn:978-3-540-61550-7 https://doi.org/10.1007/3-540-61550-4_139
[20]
Mozilla. 2023. Primitive. https://developer.mozilla.org/en-US/docs/Glossary/Primitive
[21]
Joe Gibbs Politz, Alejandro Martinez, Matthew Milano, Sumner Warren, Daniel Patterson, Junsong Li, Anand Chitipothu, and Shriram Krishnamurthi. 2013. Python: The Full Monty — A Tested Semantics for the Python Programming Language. In Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages & Applications (OOPSLA ’13). New York, NY, USA. 217–232. isbn:978-1-4503-2374-1 https://doi.org/10.1145/2509136.2509536
[22]
Serrano, Manuel. 2023. Bigloo. https://www-sop.inria.fr/mimosa/fp/Bigloo
[23]
Simionato, Michele. 2023. The Python 2.3 Method Resolution Order. https://www.python.org/download/releases/2.3/mro
[24]
Mallku Soldevila, Beta Ziliani, and Bruno Silvestre. 2022. From Specification to Testing: Semantics Engineering for Lua 5.2. J. Autom. Reason., 66, 4 (2022), nov, 905–952. issn:0168-7433 https://doi.org/10.1007/s10817-022-09638-y
[25]
Stinner, Victor. 2023. Benchmarks — Python Performance Benchmark Suite. https://pyperformance.readthedocs.io/benchmarks.html
[26]
Stinner, Victor. 2023. The Python Performance Benchmark Suite. https://pyperformance.readthedocs.io
[27]
The PyPy Team. 2023. PyPy. https://www.pypy.org
[28]
The Python Software Foundation. 2023. cPython 3.9. https://www.python.org
[29]
The Python Software Foundation. 2023. Performance Options. https://docs.python.org/3/using/configure.html#performance-options
[30]
The Python Software Foundation. 2023. PyPerformance. https://github.com/python/pyperformance
[31]
The Python Software Foundation. 2023. The Python Language Reference. https://docs.python.org/3/reference/index.html
[32]
TIOBE Software BV. 2023. TIOBE Index for August 2023. https://www.tiobe.com/tiobe-index/
[33]
Yannick Zakowski, Calvin Beck, Irene Yoon, Ilia Zaichuk, Vadim Zaliva, and Steve Zdancewic. 2021. Modular, Compositional, and Executable Formal Semantics for LLVM IR. Proc. ACM Program. Lang., 5, ICFP (2021), Article 67, aug, 30 pages. https://doi.org/10.1145/3473572
[34]
Qiang Zhang, Lei Xu, Xiangyu Zhang, and Baowen Xu. 2022. Quantifying the Interpretation Overhead of Python. Science of Computer Programming, 215, C (2022), March, issn:0167-6423 https://doi.org/10.1016/j.scico.2021.102759
Index Terms
- An Executable Semantics for Faster Development of Optimizing Python Compilers
Recommendations
Generic Executable Semantics for D-Clean
D-Clean primitives are first class citizens which allows the coordination of a dynamical work distributions over a cluster. The computations are distributed automatically over the Grid by the middleware system. The programmer controls the computation ...
A Typed C11 Semantics for Interactive Theorem Proving
CPP '15: Proceedings of the 2015 Conference on Certified Programs and ProofsWe present a semantics of a significant fragment of the C programming language as described by the C11 standard. It consists of a small step semantics of a core language, which uses a structured memory model to capture subtleties of C11, such as strict-...
Numba: a LLVM-based Python JIT compiler
LLVM '15: Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPCDynamic, interpreted languages, like Python, are attractive for domain-experts and scientists experimenting with new ideas. However, the performance of the interpreter is often a barrier when scaling to larger data sets. This paper presents a just-in-...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2023
231 pages
ISBN:9798400703966
DOI:10.1145/3623476
- General Chair:
- João Saraiva,
- Program Chairs:
- Thomas Degueule,
- Elizabeth Scott
Copyright © 2023 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
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 23 October 2023
Check for updates
Badges
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
SLE '23
Sponsor:
SLE '23: 16th ACM SIGPLAN International Conference on Software Language Engineering
October 23 - 24, 2023
Cascais, Portugal
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 111Total Downloads
- Downloads (Last 12 months)87
- Downloads (Last 6 weeks)13
Reflects downloads up to 01 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in