How fast can we make interpreted Python?
phi-node.com
phi-node.com
1) Use a register-based VM (with a sliding and growing register file) instead of a stack-based VM. In theory you can make a stack-based VM fast with lots of macroinstructions that fuse smaller operations together, but it isn't worth it.
2) Use inline caching for method calls, property accesses, and primitive operations that do type checks. In an interpreter you can modify the instruction stream even on platforms that disallow modification of executable code. I know this isn't the origin of the technique in bytecode interpreters, but here's a paper describing it in case it's not obvious:
http://www.lirmm.fr/~ducour/Doc-objets/ECOOP10/papers/6183/6...
3) Pick your value encoding carefully. You almost always want fast immediate integers. On 64-bit platforms it is quite common these days to repurpose some of the NaN range in IEEE doubles for type tags to enable storing doubles in immediate values.
4) Write your interpreter in assembly. Compilers generate terrible code for interpreters, even (especially?) with the use of computed goto / labels-as-values extensions. The register allocators of traditional compilers are designed to optimize loops by moving spill code outside of them and to reduce the impact of function calls. They will not be able to realistically allocate registers across different instruction bodies, and they won't be able to make the correct tradeoff about how much work to push into the slow path of instruction bodies.
5) Rearrange your instruction bodies based on execution / transition frequencies to improve instruction cache performance.
6) Pay close attention to the boundaries between your interpreter and the runtime libraries / the FFI. You don't want to take a bigger hit than you need to every time you call out to native code.
That technique applies more to JavaScript, which uses doubles as the standard number type, than in Python, which has both integers and floats. Still a good idea to make sure that both native integers and native floats end up as unboxed native types in registers, though.
Do you mean...group all the frequent operations together so they overlap on cache lines? It's hard to tell how much this would help, have you tried it?
You can do it automatically by gathering statistics on frequent instruction pairs. In practice greedy algorithms for code scheduling work fairly well, assuming you have meaningful statistics.
I think after the low-hanging fruit above, there's lot of weird interpreter/compiler folklore on old usenet posts, Forth VM designs, random papers (like the Register vs. Stack machine showdown).
There are also some enlightening books like "Lisp in Small Pieces".
I'm at SciPy right now and I was just talking to the Julia developers yesterday about the need for a textbook, website, or wiki to gather all this disparate info in one place.
Want to help us get it started?
I'd enjoy being on a project like that. Can I send you an email?
I say this merely as an interesting observation. I've come to consider this a de facto counterargument to the claim that languages aren't slow, only implementations are. It may be theoretically true, but in practice, as nice as Python may be to use, it has proved a very difficult language to speed up. (PyPy has taken a very good run at it, but it sure wasn't a case of "I'll just do this easy, obvious thing." PyPy seems to have hit Python's performance with multiple PhD-thesis level attacks, and it's still certainly not C in the general case.)
I disagree with you. Python isn't much harder to speed up than Lua and in some ways it's better behaved than JavaScript. Still, both of those languages enjoy implementations significantly faster than CPython. Really, it's not the semantics of the language which hold back Python's performance but rather the fact that extension modules are extremely tightly coupled with a particular interpreter implementation. Lua has a clean interface with C, JavaScript implementations generally force the outside world to use doubly indirect handles on objects. CPython, on the other hand, is shameless in flaunting its internals for the whole world to see.
The only reason that PyPy has taken "multiple PhD-thesis level attacks" to near completion is because their approach is insanely ambitious. They didn't write a JIT. Instead they wrote a toolkit for partially evaluating interpreters on source files and generate native code by tracing an interpreter while it itself runs a program. It's nuts! It's amazing that PyPy works and the amount of effort is totally unsurprising.
Had they gone a more traditional route, the whole thing could have been done in a year or two. They would, however, still face resistance from a Python community that wants to neither give up nor rewrite their PyObject-laced libraries.
Note that PyPy is not the only project that did that - remember psyco? There are reasons why after 3 years Armin said "I give up, let's do PyPy". It's not the "well behaved" part, this can be worked around, Python is simply more complex than Javascript or Lua and by complex I mean just bigger. All the extension modules that everyone naturally expects to be fast (even just the stdlib), descriptor protocol, crazy frame access semantics. That does make it very labour intensive to do the right thing. Look what happened to Unladen Swallow - they did not get anywhere really within a year. Several of PyPy optimizations that took forever to do are really new stuff, whether you do JIT by hand or generate it automatically.
Alas, it's doubtful that a Python implementation that sacrifices C extensions would get all that far with mainstream adopters, as so many useful libraries are done as C extensions.
Python's object model is incredibly rich in ways that JavaScript and Lua don't even come close to touching. Let me list some things that you'll see in Python code that you're not gonna see in JS or Lua:
* Objects that don't extend the object hierarchy (you don't have to extend from `object`)
* Types that don't extend the type hierarchy (Python has full metaclassing)
* Any object can elect to become callable; calls are almost message passes
* Two different levels of message-passing method/attribute rewriting (__getattr__ and __getattribute__)
* Descriptors, such as properties (no, real properties) are baked into the object model
* The table of globals can be altered at any time, frustrating static analysis
* The table of locals can be altered too!
* The table of builtins can be altered!! (Is nothing sacred?)
In addition, PyPy did not start out as a partial evaluator and meta-tracing JIT generator. What you're seeing is the result of about a decade of work and a half-dozen iterations. They started out with something much like the thing that you would expect to see, but just like every other Python JIT project, they learned that Python is complex and difficult to optimize.
So, uh, you're wrong. Sorry.
Cache misses are incredibly expensive, and any "obvious optimization" of Python's core will inevitably introduce more of them because the code gets longer. So most of the optimizations wins big in the area in which they are targeted, but loses in general performance.
For the same reason gcc -Os (optimizing for small binary) is often faster than gcc -O3.
On top of that, there is significant resistance from the devs to complicate the core. They prefer a slower, but easier to understand, easier to analyze interpreter over a complex one with harder to predict runtime performance. It's the same with reference counting and theoretically superior garbage collection.
One idea that stood out to me (and which I first saw in LuaJIT, and as far as I know originated with Pall) is: when rewriting loop code, unroll at least 2 iterations of the loop. (The first executes and conditionally continues into the second; the second loops onto itself). So far, just extra work.
However, any kind of constant folding algorithm is now immediately elevated into a "code hoisting out of loop" algorithm at no extra cost - e.g., SSA form gets that kind of code motion.
I'm not sure Python can make much use of that, because it is nearly impossible to guarantee idempotence of operations - but in case you can somehow make that guarantee, that can be very significant for e.g. function name lookups.
A possible way to use that is to have the loop opcode have two branch targets: "namespaces modified" (which goes to the first iteration, which reloads values) and "namespaces unmodified" (which loops at the 2nd iteration, relying on the constant folding and not looking up in dicts again). This could make calls like "a.b.c.d.e.f" require 0 lookups in most iterations of most loops -- but would also require a global "namespace modified" flag.
http://www.maths.lth.se/matematiklth/vision/publdb/reports/p...
The slow things tend to be the sort of numerical loops that you see in micro-benchmarks. It's no coincidence that the version of Python in the linked article saw its greatest speed up in a numerical loop, but only modest improvement elsewhere. It's exactly this sort of simple repetitive operation where interpreter overhead matters the most.
Language features that encapsulate complex functionality tend to be harder to speed up in CPython because the VM operates at a fairly high level. In effect you're just kicking off a large subroutine that is written in C, and you're really executing native code until that operation is complete. You're not going to improve very much on that no matter how much you try.
What this means is that speed will depend heavily on the type of application program being written, and also on how much the programmer takes advantage of the unique language features. It also makes realistic cross language benchmarks difficult because the right way to do something in Python may not have a direct equivalent in another language. The result tends to be "lowest common denominator" benchmarks, which are exactly the sort of algorithms which CPython does worst at.
The CPython interpreter is not a simple switch. It uses computed gotos if you compile it with gcc. Microsoft VC doesn't have language support needed for writing fast interpreters, so the Python source is written in a way that will default to using a switch if you compile it with MS VC. So, on every platform except for one, it's a computed goto.
Modern CPU performance is very negatively affected by branch prediction failure and cache effects. A lot of the existing literature that you may see on interpreter performance is obsolete because it doesn't take those factors into account, but rather assumes that all code paths are equal. Threading worked well with older CPUs, not so well with newer ones.
I am current working on an interpreter that recognises a subset of Python for use as a library in complex mathematical algorithms. As part of this I have bench marked multiple different interpreter designs for it and also compared it to native ('C') code. It is possible to get a much faster interpreter, provided you limit it to doing very simple things repetitively. These simple things also happen to be the sorts of things which are popular with benchmark writers (because they're easy to write cross language benchmarks for), but which CPython does not do well in.
A sub-interpreter which targets these types of problems should give improved performance in this area. Rewriting the entire Python interpreter though would probably have little value, as the characteristics of opening a file or doing set operations, or handling exceptions are entirely different from adding two numbers together.
There is no such thing as a single speed "knob" which you can crank up or down to improve performance. There are many, many, features in modern programming languages, all of which have their own characteristics. Picking out a benchmark which happens to exercise one or a few of them will tell you nothing about how a real world application will perform unless it corresponds to the actual bottlenecks in your application. For that, you need to know the application domain and the language inside and out.
One thing about Python developers is that they tend to be very pragmatic. When someone comes to them with an idea, they say "show me the numbers in a real life situation". More often than not, the theoretical advantage of the approach being espoused evaporates when subjected to that type of analysis.
looks like a switch to me.
Anyway, I've let them tell me the CPython interpreter is very simple on purpose to allow it to function as a standard 'definition' of the language behaviour. A simple jit does wonders, as does a less brain dead gc. Superinstructions, threading, ... are all possible. But you're absolutely right: It's really difficult to predict how much each improvement would contribute.
"Computed GOTOs, or the-optimization-commonly-but-improperly-known-as-"threaded code" using gcc's labels-as-values extension (...) At the time of this writing, the "threaded code" version is up to 15-20% faster than the normal "switch" version, depending on the compiler and the CPU architecture."
They also have an explanation of the branch prediction effect which I mentioned earlier.
They have both methods (switch and computed goto) since some compilers don't support computed gotos, and some people want to use alternative compilers (e.g. Microsoft VC).
In my own interpreter, I tried both switch and computed gotos, as well as another method called "replicated switch". I auto-generate the interpreter source code (using a simple script) so that I could change methods easily for comparison. In my own testing, computed gotos were about 50% faster than a simple switch, but keep in mind that is strictly doing numerical type code. More complex operations would water that down somewhat, as less of the execution time would be due to dispatch overhead.
Computed gotos aren't really any more complex than a switch once you understand the format, and as I said above you can convert between the two with a simple script. What does get complex is doing Python level static or run time code optimization to try to predict types or remove redundant operations from loops. CPython doesn't do that, while Pypy does this extensively. It's these types of compiler and run-time re-compile optimizations which make the big difference.
Overall, my interpreter is currently about 5.5 times faster than CPython with the specific simple benchmark program I tested. However, keep in mind it only does (and only ever will do) a narrow subset of the full Python language. Performance is never the result of a single technique. It's the result of many small improvements each of which address a specific problem.
I once looked at it, and it does a fairly literal translation. The only problem is that it changes semantics of the primitive types. For example a python integer becomes a C++ int. (and overflow semantics change)
I've started working on a side project that processes geo data in AppEngine. My dataset includes many long lists of numbers (lats, longs, altitudes, timestamps, etc.). A 700 route dataset is about 25MB in a sqlite database, but trying to access any significant portion of it quickly maxes out the 4GB of RAM available on either of my dev machines (which is more than I could reasonably expect to be provisioned in the cloud). I mentioned this as a potential bug to the relevant Googler at I/O this year and he basically said "that's not us, that's Python."
It's mindboggling how quickly you can burn through your RAM in CPython. Hopefully you can prove something that will eventually make its way back into CPython and lift everyone's boats. Unfortunately, even if Falcon helped on my dev machine, I can't imagine it being taken up on cloud platforms like AppEngine.
Where a lot of people who are new to Python run into problems is that the language is deceptively easy. They try writing Python code that's simply a direct analogue of how they would write Java or C#. The resulting code will run, but it often be slow and a lot more verbose than necessary. Very often the way you would do something in Java or C# is the worst possible way to do it in Python. Conversely, the best way to do it in Python often has no direct analogue in Java or C#. With Python, the learning curve is shallow, but it's very long, and there's lots to learn if you want to reap all the benefits.
Without knowing what your data or algorithms are, it's pretty difficult to give any sensible detailed advice. However, if you are dealing with long "lists" of numbers, perhaps what you really want is long "arrays" of numbers. Lists and arrays are not the same thing in Python.
Something seems very wrong if every 1 MB of data read from your SQLite database ends up consuming 150+ MB of memory in some way.
Are you able to provide any sample code and a SQLite database that exhibit this problem, so attempts can be made to fix it?
I still have plenty more work to do on the project. I think I'll end up fanning out each list iteration into a series of smaller chunks to keep me from blowing through all the RAM on any one request.
(Which you may well realize...)
For example, I had a 100MB JSON file that I tried to use the stdlib json library to load. It quickly used >8GB (my machine's RAM) and started paging, dragging everything to a halt. This is partly because the stdlib JSON parser is written in python.
Now, if you switch to a small, clever implementation called cjson[1], it can load the whole thing without bumping 3-400MB in RAM, and the high watermark is the data at the end. Much better!
So, in summary, be careful that the important part of your code is the one that uses all the RAM - and that it's not some "hello world" quality stdlib code that's killing you. If it is, and there isn't a cjson for the job, I've found wrapping C/C++ libraries with Cython[2] a simple way to solve the problem without too much hassle (generally only a couple of days work at a time if you're tight, and only wrap the functions you actually need to use yourself.)
[1] https://pypi.python.org/pypi/python-cjson - although there's a 1.5.1 out there somewhere with a fix for a bug that loses precision on floats...which is the only one I use personally. It's so hard to find that I keep a copy of the source in my Dropbox for when I need it!
[2] http://cython.org/ - although of course actually using cython means you can't take advantage of pypy, IronPython, and other "faster" implementations because you're tied to the cpython C interface forever.
From my observations in pretty much any unoptimized Python (CPython interpreted) code function calls is nearly always a bottleneck. And speed is directly bound by the number of function calls being performed, not by ponderous data structures.
While I would argue that we can't make interpreted Python particularly fast, the actual topic in question is much harder than that.
Because Python is slow, Python is not used in scenarios where speed is crucial. That much is true.
However, if Python was faster, it would be used in those scenarios, so more people would be using it for speed critical code so it would provide real gains for a great many Python programmers.
This is exactly what happened with JavaScript: before V8 JavaScript was in exactly the same position as Python. Not many people were writing large programs in JavaScript because JavaScript was too slow. V8 sped up JavaScript 10x+ and people started writing much larger apps that do require that speed. If JavaScript speed suddenly dropped to pre-V8 speeds, we would all find the most popular web apps unusably slow.
Python is used just about everywhere for just about everything (sometimes properly, sometimes poorly). While there are a lot of web sites that run Python, there are also countless other applications that use it that are unrelated to the web. See Scipy as an example.
That said, the earlier poster mentioning that many people are using Python for IO bound processes is not too far a stretch. Why else would Twisted Python exist, and why would the new Tulip async IO stuff be developed?
(And don't get me wrong, it's an effective approach that plays to the strengths of both languages. But it's not doing "heavy lifting" in python)
1) Know what ought to be done - do it and send the patches.
2) Need "speed" - write that part in C.)
2) Need "speed" - write that part in C.)Can you elaborate on this. I've worked on python C extensions (just minor updates and fixes, I've never been the one to write significant chunks of it), and it seems like interfacing python with C is pretty straight forward.
SQUAWK SQUAWK SQUAWK