PEP 3146 – Merging Unladen Swallow into CPython | peps.python.org
PEP 3146 – Merging Unladen Swallow into CPython PEP 3146 – Merging Unladen Swallow into CPython Author : Collin Winter <collinwinter at google.com>, Jeffrey Yasskin <jyasskin at google.com>, Reid Kleckner <rnk at mit.edu> Status : Withdrawn Type : Standards Track Created : 01-Jan-2010 Python-Version : 3.3 Post-History : Table of Contents PEP Withdrawal Abstract Rationale, Implementation Alternatives Performance Benchmarks Performance vs CPython 2.6.4 Memory Usage Start-up Time Binary Size Performance Retrospective Correctness and Compatibility Known Incompatibilities Platform Support Impact on CPython Development Experimenting with Changes to Python or CPython Bytecode Debugging Profiling Addition of C++ to CPython Managing LLVM Releases, C++ API Changes Building CPython Proposed Merge Plan Contingency Plans Future Work Unladen Swallow Community Licensing References Copyright PEP Withdrawal With Unladen Swallow going the way of the Norwegian Blue [1] [2] , this PEP has been deemed to have been withdrawn.
Abstract This PEP proposes the merger of the Unladen Swallow project [3] into CPython’s source tree. Unladen Swallow is an open-source branch of CPython focused on performance. Unladen Swallow is source-compatible with valid Python 2.6.4 applications and C extension modules. Unladen Swallow adds a just-in-time (JIT) compiler to CPython, allowing for the compilation of selected Python code to optimized machine code. Beyond classical static compiler optimizations, Unladen Swallow’s JIT compiler takes advantage of data collected at runtime to make checked assumptions about code behaviour, allowing the production of faster machine code.
This PEP proposes to integrate Unladen Swallow into CPython’s development tree in a separate py3k-jit branch, targeted for eventual merger with the main py3k branch. While Unladen Swallow is by no means finished or perfect, we feel that Unladen Swallow has reached sufficient maturity to warrant incorporation into CPython’s roadmap. We have sought to create a stable platform that the wider CPython development team can build upon, a platform that will yield increasing performance for years to come.
This PEP will detail Unladen Swallow’s implementation and how it differs from CPython 2.6.4; the benchmarks used to measure performance; the tools used to ensure correctness and compatibility; the impact on CPython’s current platform support; and the impact on the CPython core development process. The PEP concludes with a proposed merger plan and brief notes on possible directions for future work. We seek the following from the BDFL: Approval for the overall concept of adding a just-in-time compiler to CPython, following the design laid out below.
Permission to continue working on the just-in-time compiler in the CPython source tree. Permission to eventually merge the just-in-time compiler into the py3k branch once all blocking issues [31] have been addressed. A pony. Rationale, Implementation Many companies and individuals would like Python to be faster, to enable its use in more projects. Google is one such company. Unladen Swallow is a Google-sponsored branch of CPython, initiated to improve the performance of Google’s numerous Python libraries, tools and applications.
To make the adoption of Unladen Swallow as easy as possible, the project initially aimed at four goals: A performance improvement of 5x over the baseline of CPython 2.6.4 for single-threaded code. 100% source compatibility with valid CPython 2.6 applications. 100% source compatibility with valid CPython 2.6 C extension modules. Design for eventual merger back into CPython. We chose 2.6.4 as our baseline because Google uses CPython 2.4 internally, and jumping directly from CPython 2.4 to CPython 3.x was considered infeasible.
To achieve the desired performance, Unladen Swallow has implemented a just-in-time (JIT) compiler [51] in the tradition of Urs Hoelzle’s work on Self [52] , gathering feedback at runtime and using that to inform compile-time optimizations. This is similar to the approach taken by the current breed of JavaScript engines [59] , [60] ; most Java virtual machines [63] ; Rubinius [61] , MacRuby [62] , and other Ruby implementations; Psyco [64] ; and others.
We explicitly reject any suggestion that our ideas are original. We have sought to reuse the published work of other researchers wherever possible. If we have done any original work, it is by accident. We have tried, as much as possible, to take good ideas from all corners of the academic and industrial community. A partial list of the research papers that have informed Unladen Swallow is available on the Unladen Swallow wiki [54] .
The key observation about optimizing dynamic languages is that they are only dynamic in theory; in practice, each individual function or snippet of code is relatively static, using a stable set of types and child functions. The current CPython bytecode interpreter assumes the worst about the code it is running, that at any moment the user might override the len() function or pass a never-before-seen type into a function.
In practice this never happens, but user code pays for that support. Unladen Swallow takes advantage of the relatively static nature of user code to improve performance. At a high level, the Unladen Swallow JIT compiler works by translating a function’s CPython bytecode to platform-specific machine code, using data collected at runtime, as well as classical compiler optimizations, to improve the quality of the generated machine code.
Because we only want to spend resources compiling Python code that will actually benefit the runtime of the program, an online heuristic is used to assess how hot a given function is. Once the hotness value for a function crosses a given threshold, it is selected for compilation and optimization. Until a function is judged hot, however, it runs in the standard CPython eval loop, which in Unladen Swallow has been instrumented to record interesting data about each bytecode executed.
This runtime data is used to reduce the flexibility of the generated machine code, allowing us to optimize for the common case. For example, we collect data on Whether a branch was taken/not taken. If a branch is never taken, we will not compile it to machine code. Types used by operators. If we find that a + b is only ever adding integers, the generated machine code for that snippet will not support adding floats. Functions called at each callsite.
If we find that a particular foo() callsite is always calling the same foo function, we can optimize the call or inline it away Refer to [55] for a complete list of data points gathered and how they are used. However, if by chance the historically-untaken branch is now taken, or some integer-optimized a + b snippet receives two strings, we must support this. We cannot change Python semantics. Each of these sections of optimized machine code is preceded by a guard , which checks whether the simplifying assumptions we made when optimizing still hold.
If the assumptions are still valid, we run the optimized machine code; if they are not, we revert back to the interpreter and pick up where we left off. We have chosen to reuse a set of existing compiler libraries called LLVM [4] for code generation and code optimization. This has saved our small team from needing to understand and debug code generation on multiple machine instruction sets and from needing to implement a large set of classical compiler optimizations.
The project would not have been possible without such code reuse. We have found LLVM easy to modify and its community receptive to our suggestions and modifications. In somewhat more depth, Unladen Swallow’s JIT works by compiling CPython bytecode to LLVM’s own intermediate representation (IR) [94] , taking into account any runtime data from the CPython eval loop. We then run a set of LLVM’s built-in optimization passes, producing a smaller, optimized version o
The rest of this page is on the live site.