PyPy -- How can it possibly beat CPython?

Question

From the Google Open Source Blog:

PyPy is a reimplementation of Python in Python, using advanced techniques to try to attain better performance than CPython. Many years of hard work have finally paid off. Our speed results often beat CPython, ranging from being slightly slower, to speedups of up to 2x on real application code, to speedups of up to 10x on small benchmarks.

How is this possible? Which Python implementation was used to implement PyPy? CPython? And what are the chances of a PyPyPy or PyPyPyPy beating their score?

(On a related note... why would anyone try something like this?)

Solution 1

Q1. How is this possible?

Manual memory management (which is what CPython does with its counting) can be slower than automatic management in some cases.

Limitations in the implementation of the CPython interpreter preclude certain optimisations that PyPy can do (eg. fine grained locks).

As Marcelo mentioned, the JIT. Being able to on the fly confirm the type of an object can save you the need to do multiple pointer dereferences to finally arrive at the method you want to call.

Q2. Which Python implementation was used to implement PyPy?

The PyPy interpreter is implemented in RPython which is a statically typed subset of Python (the language and not the CPython interpreter). - Refer https://pypy.readthedocs.org/en/latest/architecture.html for details.

Q3. And what are the chances of a PyPyPy or PyPyPyPy beating their score?

That would depend on the implementation of these hypothetical interpreters. If one of them for example took the source, did some kind of analysis on it and converted it directly into tight target specific assembly code after running for a while, I imagine it would be quite faster than CPython.

Update: Recently, on a carefully crafted example, PyPy outperformed a similar C program compiled with gcc -O3. It's a contrived case but does exhibit some ideas.

Q4. Why would anyone try something like this?

From the official site. https://pypy.readthedocs.org/en/latest/architecture.html#mission-statement

We aim to provide:

• a common translation and support framework for producing
  implementations of dynamic languages, emphasizing a clean
  separation between language specification and implementation
  aspects. We call this the RPython toolchain_.

• a compliant, flexible and fast implementation of the Python_ Language which uses the above toolchain to enable new advanced high-level features without having to encode the low-level details.

By separating concerns in this way, our implementation of Python - and other dynamic languages - is able to automatically generate a Just-in-Time compiler for any dynamic language. It also allows a mix-and-match approach to implementation decisions, including many that have historically been outside of a user's control, such as target platform, memory and threading models, garbage collection strategies, and optimizations applied, including whether or not to have a JIT in the first place.

The C compiler gcc is implemented in C, The Haskell compiler GHC is written in Haskell. Do you have any reason for the Python interpreter/compiler to not be written in Python?

Solution 2

"PyPy is a reimplementation of Python in Python" is a rather misleading way to describe PyPy, IMHO, although it's technically true.

There are two major parts of PyPy.

1. The translation framework
2. The interpreter

The translation framework is a compiler. It compiles RPython code down to C (or other targets), automatically adding in aspects such as garbage collection and a JIT compiler. It cannot handle arbitrary Python code, only RPython.

RPython is a subset of normal Python; all RPython code is Python code, but not the other way around. There is no formal definition of RPython, because RPython is basically just "the subset of Python that can be translated by PyPy's translation framework". But in order to be translated, RPython code has to be statically typed (the types are inferred, you don't declare them, but it's still strictly one type per variable), and you can't do things like declaring/modifying functions/classes at runtime either.

The interpreter then is a normal Python interpreter written in RPython.

Because RPython code is normal Python code, you can run it on any Python interpreter. But none of PyPy's speed claims come from running it that way; this is just for a rapid test cycle, because translating the interpreter takes a long time.

With that understood, it should be immediately obvious that speculations about PyPyPy or PyPyPyPy don't actually make any sense. You have an interpreter written in RPython. You translate it to C code that executes Python quickly. There the process stops; there's no more RPython to speed up by processing it again.

So "How is it possible for PyPy to be faster than CPython" also becomes fairly obvious. PyPy has a better implementation, including a JIT compiler (it's generally not quite as fast without the JIT compiler, I believe, which means PyPy is only faster for programs susceptible to JIT-compilation). CPython was never designed to be a highly optimising implementation of the Python language (though they do try to make it a highly optimised implementation, if you follow the difference).

---

The really innovative bit of the PyPy project is that they don't write sophisticated GC schemes or JIT compilers by hand. They write the interpreter relatively straightforwardly in RPython, and for all RPython is lower level than Python it's still an object-oriented garbage collected language, much more high level than C. Then the translation framework automatically adds things like GC and JIT. So the translation framework is a huge effort, but it applies equally well to the PyPy python interpreter however they change their implementation, allowing for much more freedom in experimentation to improve performance (without worrying about introducing GC bugs or updating the JIT compiler to cope with the changes). It also means when they get around to implementing a Python3 interpreter, it will automatically get the same benefits. And any other interpreters written with the PyPy framework (of which there are a number at varying stages of polish). And all interpreters using the PyPy framework automatically support all platforms supported by the framework.

So the true benefit of the PyPy project is to separate out (as much as possible) all the parts of implementing an efficient platform-independent interpreter for a dynamic language. And then come up with one good implementation of them in one place, that can be re-used across many interpreters. That's not an immediate win like "my Python program runs faster now", but it's a great prospect for the future.

And it can run your Python program faster (maybe).

Solution 3

PyPy is implemented in Python, but it implements a JIT compiler to generate native code on the fly.

The reason to implement PyPy on top of Python is probably that it is simply a very productive language, especially since the JIT compiler makes the host language's performance somewhat irrelevant.

Solution 4

PyPy is written in Restricted Python. It does not run on top of the CPython interpreter, as far as I know. Restricted Python is a subset of the Python language. AFAIK, the PyPy interpreter is compiled to machine code, so when installed it does not utilize a python interpreter at runtime.

Your question seems to expect the PyPy interpreter is running on top of CPython while executing code. Edit: Yes, to use PyPy you first translate the PyPy python code, either to C and build with gcc, to jvm byte code, or to .Net CLI code. See Getting Started

View more solutions

Comments

[u0b34a0f6ae]

Nitpick: PyPy is PyPyPy. Think of the Py-* prefix as a projection operator.

[balki]

Ok. so PyPy should be preferred than to CPython? does it have any drawbacks?

[Cees Timmerman]

PyPy is excellent at runtime optimization, but its different innards make it incompatible with several popular C extensions.

[Sergey Orshanskiy]

Almost everyone is missing the question, as to how a speed gain is THEORETICALLY possible. But think about it: Python can do anything, just like a Turing machine. It can call gcc, after all. So you can also write some python code that runs on CPython, that interprets some other python code, translates it to C, and executes gcc, and then executes the compiled program. And it could be faster, if the code is called often enough.

[Alexander H]

Does the JIT generate Python code running at the same level as PyPy, or does it generate real native code running at the level of whichever Python implementation PyPy is running on?

[Alex S]

Real native code (see here); 32-bit x86 code to be precise.

[Frank V]

PyPy will run on top of CPython but in this mode it doesn't provide the speed gains one might desire. :-) codespeak.net/pypy/dist/pypy/doc/…

[Ben]

This answer is completely missing the main explanation for how PyPy is fast; while it mentions that PyPy is not really implemented in Python, but in RPython, it doesn't point out that RPython code is statically compiled and optimised to produce the PyPy interpreter (it just happens to also be valid Python code that can run on top of CPython much more slowly). What they have implemented in "normal Python" is the RPython "compiler" (the translation framework referred to in the block quote).

[Tobu]

This is burying the lede. Most of the performance comes from translation to C (which makes the interpreter not that much slower than CPython), and JIT, which makes hot paths much faster.

[polvoazul]

I couldnt follow the difference :(

[Ben]

@polvoazul The difference between an optimized language implementation and an optimizing one? Well, when I say the CPython is a well optimized implementation, I mean that the developers try to make the internal algorithms of the interpreter itself and the builtin data structures run efficiently. An optimizing implementation, OTOH, would analyze the end users code and try to figure out ways to transform it to execute more efficiently.

[Ali]

"Update: Recently, on a carefully crafted example, PyPy outperformed a similar C program compiled with gcc -O3." And if you read the first comment under that post, you will see that the writer of that post doesn't know link-time optimization. With link-time optimization enabled, the C code runs faster.

[Noufal Ibrahim]

Well, the blog post was in 2011 and this answer in 2014. Also, the comment does mention shared libraries. I don't know how much of this (answer and blog post) is valid. All the involved technologies have changed a lot in the past few years.

[amcgregor]

On the two carefully crafted examples of Pypy being faster than equivalent C, each is faster in benchmark for a very specific set of reasons. The first because Pypy is smart enough to realize the tight loop counting things never has that count used, so it can be deleted entirely (JIT pass) the second for a combination of: because the Pypy JIT can "inline across library boundaries", given the example of the "printf" function being specialized to literally only be able to emit an integer, and eliminates repeated malloc (memory allocation overhead).