Alternatives

There are number of alternative strategies for improving Python performance which we considered, but found unsatisfactory.

• Cython, Shedskin: Cython [103] and Shedskin [104] are both static compilers for Python. We view these as useful-but-limited workarounds for CPython's historically-poor performance. Shedskin does not support the full Python standard library [105], while Cython requires manual Cython-specific annotations for optimum performance.

  Static compilers like these are useful for writing extension modules without worrying about reference counting, but because they are static, ahead-of-time compilers, they cannot optimize the full range of code under consideration by a just-in-time compiler informed by runtime data.

• IronPython: IronPython [108] is Python on Microsoft's .Net platform. It is not actively tested on Mono [109], meaning that it is essentially Windows-only, making it unsuitable as a general CPython replacement.

• Jython: Jython [110] is a complete implementation of Python 2.5, but is significantly slower than Unladen Swallow (3-5x on measured benchmarks) and has no support for CPython extension modules [111], which would make migration of large applications prohibitively expensive.

• Psyco: Psyco [66] is a specializing JIT compiler for CPython, implemented as an extension module. It primarily improves performance for numerical code. Pros: exists; makes some code faster. Cons: 32-bit only, with no plans for 64-bit support; supports x86 only; very difficult to maintain; incompatible with SSE2 optimized code due to alignment issues.

• PyPy: PyPy [67] has good performance on numerical code, but is slower than Unladen Swallow on some workloads. Migration of large applications from CPython to PyPy would be prohibitively expensive: PyPy's JIT compiler supports only 32-bit x86 code generation; important modules, such as MySQLdb and pycrypto, do not build against PyPy; PyPy does not offer an embedding API, much less the same API as CPython.

• PyV8: PyV8 [112] is an alpha-stage experimental Python-to-JavaScript compiler that runs on top of V8. PyV8 does not implement the whole Python language, and has no support for CPython extension modules.

• WPython: WPython [106] is a wordcode-based reimplementation of CPython's interpreter loop. While it provides a modest improvement to interpreter performance [107], it is not an either-or substitute for a just-in-time compiler. An interpreter will never be as fast as optimized machine code. We view WPython and similar interpreter enhancements as complementary to our work, rather than as competitors.

Benchmarks

Unladen Swallow has developed a fairly large suite of benchmarks, ranging from synthetic microbenchmarks designed to test a single feature up through whole-application macrobenchmarks. The inspiration for these benchmarks has come variously from third-party contributors (in the case of the html5lib benchmark), Google's own internal workloads (slowspitfire, pickle, unpickle), as well as tools and libraries in heavy use throughout the wider Python community (django, 2to3, spambayes). These benchmarks are run through a single interface called perf.py that takes care of collecting memory usage information, graphing performance, and running statistics on the benchmark results to ensure significance.

The full list of available benchmarks is available on the Unladen Swallow wiki [44], including instructions on downloading and running the benchmarks for yourself. All our benchmarks are open-source; none are Google-proprietary. We believe this collection of benchmarks serves as a useful tool to benchmark any complete Python implementation, and indeed, PyPy is already using these benchmarks for their own performance testing [82], [97]. We welcome this, and we seek additional workloads for the benchmark suite from the Python community.

We have focused our efforts on collecting macrobenchmarks and benchmarks that simulate real applications as well as possible, when running a whole application is not feasible. Along a different axis, our benchmark collection originally focused on the kinds of workloads seen by Google's Python code (webapps, text processing), though we have since expanded the collection to include workloads Google cares nothing about. We have so far shied away from heavily-numerical workloads, since NumPy [81] already does an excellent job on such code and so improving numerical performance was not an initial high priority for the team; we have begun to incorporate such benchmarks into the collection [98] and have started work on optimizing numerical Python code.

Beyond these benchmarks, there are also a variety of workloads we are explicitly not interested in benchmarking. Unladen Swallow is focused on improving the performance of pure-Python code, so the performance of extension modules like NumPy is uninteresting since NumPy's core routines are implemented in C. Similarly, workloads that involve a lot of IO like GUIs, databases or socket-heavy applications would, we feel, fail to accurately measure interpreter or code generation optimizations. That said, there's certainly room to improve the performance of C-language extensions modules in the standard library, and as such, we have added benchmarks for the cPickle and re modules.

Performance vs CPython 2.6.4

The charts below compare the arithmetic mean of multiple benchmark iterations for CPython 2.6.4 and Unladen Swallow. perf.py gathers more data than this, and indeed, arithmetic mean is not the whole story; we reproduce only the mean for the sake of conciseness. We include the t score from the Student's two-tailed T-test [45] at the 95% confidence interval to indicate the significance of the result. Most benchmarks are run for 100 iterations, though some longer-running whole-application benchmarks are run for fewer iterations.

A description of each of these benchmarks is available on the Unladen Swallow wiki [44].

Command:

./perf.py -r -b default,apps ../a/python ../b/python

32-bit; gcc 4.0.3; Ubuntu Dapper; Intel Core2 Duo 6600 @ 2.4GHz; 2 cores; 4MB L2 cache; 4GB RAM

64-bit; gcc 4.2.4; Ubuntu Hardy; AMD Opteron 8214 HE @ 2.2 GHz; 4 cores; 1MB L2 cache; 8GB RAM

Many of these benchmarks take a hit under Unladen Swallow because the current version blocks execution to compile Python functions down to machine code. This leads to the behaviour seen in the timeline graphs for the html5lib and rietveld benchmarks, for example, and slows down the overall performance of 2to3. We have an active development branch to fix this problem ([47], [48]), but working within the strictures of CPython's current threading system has complicated the process and required far more care and time than originally anticipated. We view this issue as critical to final merger into the py3k branch.

We have obviously not met our initial goal of a 5x performance improvement. A performance retrospective follows, which addresses why we failed to meet our initial performance goal. We maintain a list of yet-to-be-implemented performance work [51].

Memory Usage

The following table shows maximum memory usage (in kilobytes) for each of Unladen Swallow's default benchmarks for both CPython 2.6.4 and Unladen Swallow r988, as well as a timeline of memory usage across the lifetime of the benchmark. We include tables for both 32- and 64-bit binaries. Memory usage was measured on Linux 2.6 systems by summing the Private_ sections from the kernel's /proc/$pid/smaps pseudo-files [46].

Command:

./perf.py -r --track_memory -b default,apps ../a/python ../b/python

32-bit

64-bit

The increased memory usage comes from a) LLVM code generation, analysis and optimization libraries; b) native code; c) memory usage issues or leaks in LLVM; d) data structures needed to optimize and generate machine code; e) as-yet uncategorized other sources.

While we have made significant progress in reducing memory usage since the initial naive JIT implementation [43], there is obviously more to do. We believe that there are still memory savings to be made without sacrificing performance. We have tended to focus on raw performance, and we have not yet made a concerted push to reduce memory usage. We view reducing memory usage as a blocking issue for final merger into the py3k branch. We seek guidance from the community on an acceptable level of increased memory usage.

Start-up Time

Statically linking LLVM's code generation, analysis and optimization libraries increases the time needed to start the Python binary. C++ static initializers used by LLVM also increase start-up time, as does importing the collection of pre-compiled C runtime routines we want to inline to Python code.

Results from Unladen Swallow's startup benchmarks:

$ ./perf.py -r -b startup /tmp/cpy-26/bin/python /tmp/unladen/bin/python

### normal_startup ###
Min: 0.219186 -> 0.352075: 1.6063x slower
Avg: 0.227228 -> 0.364384: 1.6036x slower
Significant (t=-51.879098, a=0.95)
Stddev: 0.00762 -> 0.02532: 3.3227x larger
Timeline: http://tinyurl.com/yfe8z3r

### startup_nosite ###
Min: 0.105949 -> 0.264912: 2.5004x slower
Avg: 0.107574 -> 0.267505: 2.4867x slower
Significant (t=-703.557403, a=0.95)
Stddev: 0.00214 -> 0.00240: 1.1209x larger
Timeline: http://tinyurl.com/yajn8fa

### bzr_startup ###
Min: 0.067990 -> 0.097985: 1.4412x slower
Avg: 0.084322 -> 0.111348: 1.3205x slower
Significant (t=-37.432534, a=0.95)
Stddev: 0.00793 -> 0.00643: 1.2330x smaller
Timeline: http://tinyurl.com/ybdm537

### hg_startup ###
Min: 0.016997 -> 0.024997: 1.4707x slower
Avg: 0.026990 -> 0.036772: 1.3625x slower
Significant (t=-53.104502, a=0.95)
Stddev: 0.00406 -> 0.00417: 1.0273x larger
Timeline: http://tinyurl.com/ycout8m

bzr_startup and hg_startup measure how long it takes Bazaar and Mercurial, respectively, to display their help screens. startup_nosite runs python -S many times; usage of the -S option is rare, but we feel this gives a good indication of where increased startup time is coming from.

Unladen Swallow has made headway toward optimizing startup time, but there is still more work to do and further optimizations to implement. Improving start-up time is a high-priority item [34] in Unladen Swallow's merger punchlist.

Binary Size

Statically linking LLVM's code generation, analysis and optimization libraries significantly increases the size of the python binary. The tables below report stripped on-disk binary sizes; the binaries are stripped to better correspond with the configurations used by system package managers. We feel this is the most realistic measure of any change in binary size.

The increased binary size is caused by statically linking LLVM's code generation, analysis and optimization libraries into the python binary. This can be straightforwardly addressed by modifying LLVM to better support shared linking and then using that, instead of the current static linking. For the moment, though, static linking provides an accurate look at the cost of linking against LLVM.

Even when statically linking, we believe there is still headroom to improve on-disk binary size by narrowing Unladen Swallow's dependencies on LLVM. This issue is actively being addressed [33].

Performance Retrospective

Our initial goal for Unladen Swallow was a 5x performance improvement over CPython 2.6. We did not hit that, nor to put it bluntly, even come close. Why did the project not hit that goal, and can an LLVM-based JIT ever hit that goal?

Why did Unladen Swallow not achieve its 5x goal? The primary reason was that LLVM required more work than we had initially anticipated. Based on the fact that Apple was shipping products based on LLVM [83], and other high-level languages had successfully implemented LLVM-based JITs ([62], [64], [84]), we had assumed that LLVM's JIT was relatively free of show-stopper bugs.

That turned out to be incorrect. We had to turn our attention away from performance to fix a number of critical bugs in LLVM's JIT infrastructure (for example, [85], [86]) as well as a number of nice-to-have enhancements that would enable further optimizations along various axes (for example, [88], [87], [89]). LLVM's static code generation facilities, tools and optimization passes are stable and stress-tested, but the just-in-time infrastructure was relatively untested and buggy. We have fixed this.

(Our hypothesis is that we hit these problems -- problems other projects had avoided -- because of the complexity and thoroughness of CPython's standard library test suite.)

We also diverted engineering effort away from performance and into support tools such as gdb and oProfile. gdb did not work well with JIT compilers at all, and LLVM previously had no integration with oProfile. Having JIT-aware debuggers and profilers has been very valuable to the project, and we do not regret channeling our time in these directions. See the Debugging and Profiling sections for more information.

Can an LLVM-based CPython JIT ever hit the 5x performance target? The benchmark results for JIT-based JavaScript implementations suggest that 5x is indeed possible, as do the results PyPy's JIT has delivered for numeric workloads. The experience of Self-92 [53] is also instructive.

Can LLVM deliver this? We believe that we have only begun to scratch the surface of what our LLVM-based JIT can deliver. The optimizations we have incorporated into this system thus far have borne significant fruit (for example, [90], [91], [92]). Our experience to date is that the limiting factor on Unladen Swallow's performance is the engineering cycles needed to implement the literature. We have found LLVM easy to work with and to modify, and its built-in optimizations have greatly simplified the task of implementing Python-level optimizations.

An overview of further performance opportunities is discussed in the Future Work section.

Known Incompatibilities

The only application or library we know to not work with Unladen Swallow that does work with CPython 2.6.4 is Psyco [66]. We are aware of some libraries such as PyGame [80] that work well with CPython 2.6.4, but suffer some degradation due to changes made in Unladen Swallow. We are tracking this issue [48] and are working to resolve these instances of degradation.

While Unladen Swallow is source-compatible with CPython 2.6.4, it is not binary compatible. C extension modules compiled against one will need to be recompiled to work with the other.

The merger of Unladen Swallow should have minimal impact on long-lived CPython optimization branches like WPython. WPython [106] and Unladen Swallow are largely orthogonal, and there is no technical reason why both could not be merged into CPython. The changes needed to make WPython compatible with a JIT-enhanced version of CPython should be minimal [115]. The same should be true for other CPython optimization projects (for example, [116]).

Invasive forks of CPython such as Stackless Python [117] are more challenging to support. Since Stackless is highly unlikely to be merged into CPython [118] and an increased maintenance burden is part and parcel of any fork, we consider compatibility with Stackless to be relatively low-priority. JIT-compiled stack frames use the C stack, so Stackless should be able to treat them the same as it treats calls through extension modules. If that turns out to be unacceptable, Stackless could either remove the JIT compiler or improve JIT code generation to better support heap-based stack frames [119], [120].

Experimenting with Changes to Python or CPython Bytecode

Unladen Swallow's JIT compiler operates on CPython bytecode, and as such, it is immune to Python language changes that affect only the parser.

We recommend that changes to the CPython bytecode compiler or the semantics of individual bytecodes be prototyped in the interpreter loop first, then be ported to the JIT compiler once the semantics are clear. To make this easier, Unladen Swallow includes a --without-llvm configure-time option that strips out the JIT compiler and all associated infrastructure. This leaves the current burden of experimentation unchanged so that developers can prototype in the current low-barrier-to-entry interpreter loop.

Unladen Swallow began implementing its JIT compiler by doing straightforward, naive translations from bytecode implementations into LLVM API calls. We found this process to be easily understood, and we recommend the same approach for CPython. We include several sample changes from the Unladen Swallow repository here as examples of this style of development: [26], [27], [28], [29].

Debugging

The Unladen Swallow team implemented changes to gdb to make it easier to use gdb to debug JIT-compiled Python code. These changes were released in gdb 7.0 [17]. They make it possible for gdb to identify and unwind past JIT-generated call stack frames. This allows gdb to continue to function as before for CPython development if one is changing, for example, the list type or builtin functions.

Example backtrace after our changes, where baz, bar and foo are JIT-compiled:

Program received signal SIGSEGV, Segmentation fault.
0x00002aaaabe7d1a8 in baz ()
(gdb) bt
#0 0x00002aaaabe7d1a8 in baz ()
#1 0x00002aaaabe7d12c in bar ()
#2 0x00002aaaabe7d0aa in foo ()
#3 0x00002aaaabe7d02c in main ()
#4 0x0000000000b870a2 in llvm::JIT::runFunction (this=0x1405b70, F=0x14024e0, ArgValues=...)
at /home/rnk/llvm-gdb/lib/ExecutionEngine/JIT/JIT.cpp:395
#5 0x0000000000baa4c5 in llvm::ExecutionEngine::runFunctionAsMain
(this=0x1405b70, Fn=0x14024e0, argv=..., envp=0x7fffffffe3c0)
at /home/rnk/llvm-gdb/lib/ExecutionEngine/ExecutionEngine.cpp:377
#6 0x00000000007ebd52 in main (argc=2, argv=0x7fffffffe3a8,
envp=0x7fffffffe3c0) at /home/rnk/llvm-gdb/tools/lli/lli.cpp:208

Previously, the JIT-compiled frames would have caused gdb to unwind incorrectly, generating lots of obviously-incorrect #6 0x00002aaaabe7d0aa in ?? ()-style stack frames.

Highlights:

• gdb 7.0 is able to correctly parse JIT-compiled stack frames, allowing full use of gdb on non-JIT-compiled functions, that is, the vast majority of the CPython codebase.
• Disassembling inside a JIT-compiled stack frame automatically prints the full list of instructions making up that function. This is an advance over the state of gdb before our work: developers needed to guess the starting address of the function and manually disassemble the assembly code.
• Flexible underlying mechanism allows CPython to add more and more information, and eventually reach parity with C/C++ support in gdb for JIT-compiled machine code.

Lowlights:

• gdb cannot print local variables or tell you what line you're currently executing inside a JIT-compiled function. Nor can it step through JIT-compiled code, except for one instruction at a time.
• Not yet integrated with Apple's gdb or Microsoft's Visual Studio debuggers.

The Unladen Swallow team is working with Apple to get these changes incorporated into their future gdb releases.

Profiling

Unladen Swallow integrates with oProfile 0.9.4 and newer [18] to support assembly-level profiling on Linux systems. This means that oProfile will correctly symbolize JIT-compiled functions in its reports.

Example report, where the #u#-prefixed symbol names are JIT-compiled Python functions:

$ opreport -l ./python | less
CPU: Core 2, speed 1600 MHz (estimated)
Counted CPU_CLK_UNHALTED events (Clock cycles when not halted) with a unit mask of 0x00 (Unhalted core cycles) count 100000
samples % image name symbol name
79589 4.2329 python PyString_FromFormatV
62971 3.3491 python PyEval_EvalCodeEx
62713 3.3354 python tupledealloc
57071 3.0353 python _PyEval_CallFunction
50009 2.6597 24532.jo #u#force_unicode
47468 2.5246 python PyUnicodeUCS2_Decode
45829 2.4374 python PyFrame_New
45173 2.4025 python lookdict_string
43082 2.2913 python PyType_IsSubtype
39763 2.1148 24532.jo #u#render5
38145 2.0287 python _PyType_Lookup
37643 2.0020 python PyObject_GC_UnTrack
37105 1.9734 python frame_dealloc
36849 1.9598 python PyEval_EvalFrame
35630 1.8950 24532.jo #u#resolve
33313 1.7717 python PyObject_IsInstance
33208 1.7662 python PyDict_GetItem
33168 1.7640 python PyTuple_New
30458 1.6199 python PyCFunction_NewEx

This support is functional, but as-yet unpolished. Unladen Swallow maintains a punchlist of items we feel are important to improve in our oProfile integration to make it more useful to core CPython developers [19].

Highlights:

• Symbolization of JITted frames working in oProfile on Linux.

Lowlights:

• No work yet invested in improving symbolization of JIT-compiled frames for Apple's Shark [20] or Microsoft's Visual Studio profiling tools.
• Some polishing still desired for oProfile output.

We recommend using oProfile 0.9.5 (and newer) to work around a now-fixed bug on x86-64 platforms in oProfile. oProfile 0.9.4 will work fine on 32-bit platforms, however.

Given the ease of integrating oProfile with LLVM [21] and Unladen Swallow [22], other profiling tools should be easy as well, provided they support a similar JIT interface [23].

We have documented the process for using oProfile to profile Unladen Swallow [24]. This document will be merged into CPython's Doc/ tree in the merge.

Addition of C++ to CPython

In order to use LLVM, Unladen Swallow has introduced C++ into the core CPython tree and build process. This is an unavoidable part of depending on LLVM; though LLVM offers a C API [8], it is limited and does not expose the functionality needed by CPython. Because of this, we have implemented the internal details of the Unladen Swallow JIT and its supporting infrastructure in C++. We do not propose converting the entire CPython codebase to C++.

Highlights:

• Easy use of LLVM's full, powerful code generation and related APIs.
• Convenient, abstract data structures simplify code.
• C++ is limited to relatively small corners of the CPython codebase.
• C++ can be disabled via ./configure --without-llvm, which even omits the dependency on libstdc++.

Lowlights:

• Developers must know two related languages, C and C++ to work on the full range of CPython's internals.
• A C++ style guide will need to be developed and enforced. PEP 7 will be extended [121] to encompass C++ by taking the relevant parts of the C++ style guides from Unladen Swallow [71], LLVM [72] and Google [73].
• Different C++ compilers emit different ABIs; this can cause problems if CPython is compiled with one C++ compiler and extensions modules are compiled with a different C++ compiler.

Managing LLVM Releases, C++ API Changes

LLVM is released regularly every six months. This means that LLVM may be released two or three times during the course of development of a CPython 3.x release. Each LLVM release brings newer and more powerful optimizations, improved platform support and more sophisticated code generation.

LLVM releases usually include incompatible changes to the LLVM C++ API; the release notes for LLVM 2.6 [9] include a list of intentionally-introduced incompatibilities. Unladen Swallow has tracked LLVM trunk closely over the course of development. Our experience has been that LLVM API changes are obvious and easily or mechanically remedied. We include two such changes from the Unladen Swallow tree as references here: [10], [11].

Due to API incompatibilities, we recommend that an LLVM-based CPython target compatibility with a single version of LLVM at a time. This will lower the overhead on the core development team. Pegging to an LLVM version should not be a problem from a packaging perspective, because pre-built LLVM packages generally become available via standard system package managers fairly quickly following an LLVM release, and failing that, llvm.org itself includes binary releases.

Unladen Swallow has historically included a copy of the LLVM and Clang source trees in the Unladen Swallow tree; this was done to allow us to closely track LLVM trunk as we made patches to it. We do not recommend this model of development for CPython. CPython releases should be based on official LLVM releases. Pre-built LLVM packages are available from MacPorts [12] for Darwin, and from most major Linux distributions ([13], [14], [16]). LLVM itself provides additional binaries, such as for MinGW [25].

LLVM is currently intended to be statically linked; this means that binary releases of CPython will include the relevant parts (not all!) of LLVM. This will increase the binary size, as noted above. To simplify downstream package management, we will modify LLVM to better support shared linking. This issue will block final merger [99].

Unladen Swallow has tasked a full-time engineer with fixing any remaining critical issues in LLVM before LLVM's 2.7 release. We consider it essential that CPython 3.x be able to depend on a released version of LLVM, rather than closely tracking LLVM trunk as Unladen Swallow has done. We believe we will finish this work [100] before the release of LLVM 2.7, expected in May 2010.

Building CPython

In addition to a runtime dependency on LLVM, Unladen Swallow includes a build-time dependency on Clang [5], an LLVM-based C/C++ compiler. We use this to compile parts of the C-language Python runtime to LLVM's intermediate representation; this allows us to perform cross-language inlining, yielding increased performance. Clang is not required to run Unladen Swallow. Clang binary packages are available from most major Linux distributions (for example, [15]).

We examined the impact of Unladen Swallow on the time needed to build Python, including configure, full builds and incremental builds after touching a single C source file.

Full builds take a hit due to a) additional .cc files needed for LLVM interaction, b) statically linking LLVM into libpython, c) compiling parts of the Python runtime to LLVM IR to enable cross-language inlining.

Incremental builds are also somewhat slower than mainline CPython. The table below shows incremental rebuild times after touching Objects/listobject.c.

As with full builds, this extra time comes from statically linking LLVM into libpython. If libpython were linked shared against LLVM, this overhead would go down.

Contingency Plans

There is a chance that we will not be able to reduce memory usage or startup time to a level satisfactory to the CPython community. Our primary contingency plan for this situation is to shift from an online just-in-time compilation strategy to an offline ahead-of-time strategy using an instrumented CPython interpreter loop to obtain feedback. This is the same model used by gcc's feedback-directed optimizations (-fprofile-generate) [113] and Microsoft Visual Studio's profile-guided optimizations [114]; we will refer to this as "feedback-directed optimization" here, or FDO.

We believe that an FDO compiler for Python would be inferior to a JIT compiler. FDO requires a high-quality, representative benchmark suite, which is a relative rarity in both open- and closed-source development. A JIT compiler can dynamically find and optimize the hot spots in any application -- benchmark suite or no -- allowing it to adapt to changes in application bottlenecks without human intervention.

If an ahead-of-time FDO compiler is required, it should be able to leverage a large percentage of the code and infrastructure already developed for Unladen Swallow's JIT compiler. Indeed, these two compilation strategies could exist side-by-side.