9 ms·

How fast can we make interpreted Python?

167 points by iskander 13y ago

dchichkov 13y ago
Can we make function calls cheaper? 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.
- iskander 13y ago
  The ponderousness of these data structures isn't just about memory consumption or having to use boxed numbers. As far as performance goes, PyObjects infect everything in the interpreter. For example, when you're calling a Python function, after a long run-around in ceval, PyObject_Call, the function object's function_call method, you'll finally get back to ceval which creates a frame via a lengthy call to PyFrame_New. The whole process is a mess of allocating, deconstructing, increfing, decrefing, and tag-checking.
jaegerpicker 13y ago
While this is an undeniably cool project from the tech side, I think it's usually a better idea to rewrite bottlenecks of the kind that this helps with as a c extension. It's a fairly easy process (MUCH easier then in Java for example) and only a small amount of code needs to be in c itself but you can get huge performance increases without changing the Cython environment. I've always thought that was one of python/ruby's greatest strength's is the easy C integration.
- fernly 13y ago
  I think you mean the "CPython environment"? "Cython" is something else.
bsimpson 13y ago
As a web developer, I've often heard neckbeards bickering about Python's performance, but haven't had a real point-of-reference to understand how bad it can be until recently. 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.
- gregorsamza 13y ago
  A dataset with "many long lists of numbers" sounds like an ideal use case for NumPy, have you tried using that?
  - scardine 13y ago
    GAE allows only pure Python. No binary modules like NumPy.
    - kirubakaran 13y ago
      Numpy is supported https://developers.google.com/appengine/docs/python/tools/libraries27 https://developers.google.com/appengine/docs/python/tools/li...
    - corey 13y ago
      Python has an array class too: http://docs.python.org/2/library/array.html http://docs.python.org/2/library/array.html
  - bsimpson 13y ago
freework 13y ago
Python is typically used to build applications that are IO bound. Squeezing more performance out of the interpreter is not going to translate to any real gains for most Python users these days.
- dexterous 13y ago
  I'm curious, what leads you to the conclusion that 'Python is typically used to build applications that are IO bound'? Also, what exactly are you referring to when you say 'IO bound'?
  - bluedino 13y ago
    Python is commonly used in web services, where retrieving information from a database and transmitting the results via slow network connections are what takes up the most time, not processing the data in between with Python.
    - dexterous 13y ago
      I don't buy that. I've had enough people relate Python's roots in the sysad tool belt and it's application in processing large data sets to believe that it's intended use case could be that limited.
      - DrJosiah 13y ago
        And you shouldn't :) 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?
        dexterous 13y ago
cwzwarich 13y ago
There are a couple of things you want to do (some of which overlap with the article): 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/61830429.pdf 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.
- iskander 13y ago
  >Rearrange your instruction bodies based on execution / transition frequencies to improve instruction cache performance. 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?
  - mentat 13y ago
    Looks like he's contributed significantly to the Webkit javascript interpreter: https://www.webkit.org/blog/196/cameron-zwarich-is-a-webkit-reviewer/ https://www.webkit.org/blog/196/cameron-zwarich-is-a-webkit-...
jerf 13y ago
It seems to me over the past ten years I've heard this story so many times: "Python sucks. Let's do the obvious thing that makes it faster." Then, a month or two later, "I did the obvious thing and it's sometimes faster but often slower, net no gain or possible loss." to which the response is obviously "No sale." 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.)
- iskander 13y ago
  >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. 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.
  - enupten 13y ago
    There is some truth here; even the militantly dynamic Common lisp has a blisteringly fast implementation (SBCL).
dschiptsov 13y ago
The answer is very simple: 1) Know what ought to be done - do it and send the patches. 2) Need "speed" - write that part in C.)
- sherjilozair 13y ago
  2) Need "speed" - write that part in C.) That's not so easy. Interfacing Python and C code is also incredibly hard, and no one true way exists.
  - gizmo686 13y ago
    >That's not so easy. Interfacing Python and C code is also incredibly hard, and no one true way exists. 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.
    - lmm 13y ago
      If you use the CPython C API it's easy - but you also bind yourself closely to CPython. If you know performance is going to be important it's probably better to bite the bullet and use PyPy - which means you have to use the somewhat cruder cffi to interface with C code.
  - briancurtin 13y ago
    I've done it numerous times over the last several years and while it's probably not trivial, it's definitely not hard. If you're looking for a "one true way", it's Python's C API.
  - pekk 13y ago
    It might be incredibly hard if you do not know C.
catmanjan 13y ago
Haha oh my god Terry A. Davis commented on it! SQUAWK SQUAWK SQUAWK
fernly 13y ago
No mention of the somewhat confusingly named Cython [1]? It addresses the same issues in a different way. [1] http://en.wikipedia.org/wiki/Cython http://en.wikipedia.org/wiki/Cython
beagle3 13y ago
If you haven't already, LuaJIT's source code (and Mike Pall when asked) is a treasure trove of speedup ideas. 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.
- fijal 13y ago
  We have this optimization in PyPy (so yes, Python can do it). There is even a paper [0]. LuaJIT is a great source of inspiration but Python is just a huge language, which makes it much harder. http://www.maths.lth.se/matematiklth/vision/publdb/reports/pdf/ardo-bolz-etal-dls-12.pdf http://www.maths.lth.se/matematiklth/vision/publdb/reports/p...
mappu 13y ago
This is bikeshedding, but "The only hard problems in computer science are cache invalidation and naming things" - there's already a quite popular, multi-paradigm programming language named Falcon[1]. 1. http://www.falconpl.org/ http://www.falconpl.org/
- simonh 13y ago
  Sorry, but the two hard problems in programming are actually cache invalidation, naming things and off by one errors.
fijal 13y ago
The title is very misleading - it should be called "How fast can we make CPython", because it talks about compatibility with PyObject* and stuff. While I would argue that we can't make interpreted Python particularly fast, the actual topic in question is much harder than that.
xenonflash 13y ago
I don't think its correct to say the CPython is slow. What you can more accurately say about CPython is that the performance is highly variable. Some things are very fast, while others are comparatively slow. 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.
- toolslive 13y ago
  it really is a slow interpreter. Python comes with a pystone benchmark, and CPython is invariably the slowest of all interpreters. This being said, if you take a look at it's implementation, then it's immediately obvious why. The interpreter is a basically a simple C switch, with no optimization whatsoever. Simply threading the interpreter would make it about a factor 2 faster (at least that's what the experts claim you gain by threading)
  - xenonflash 13y ago
    Pystone isn't a performance benchmark, or at least it isn't a useful one. It's more of a regression test to see if anything has changed between versions. It's not useful as a performance benchmark because it doesn't weight the results according to how much the individual features matter in real life. There are three versions of Python besides CPython that are in commercial use. Two are much slower than CPython (up to three times slower), and Pypy is (currently) faster in some applications and slower in others. 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.
int3 13y ago
Interesting approach. One criticism: The paper mentions that compile times max out at 1.1ms "for the most complex function" in the benchmark (AES), and therefore it is sufficient to just compile everything. However, those benchmarks seem too small to justify that conclusion.

167 points by iskander 13y ago

Can we make function calls cheaper? 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.

iskander 13y ago
The ponderousness of these data structures isn't just about memory consumption or having to use boxed numbers. As far as performance goes, PyObjects infect everything in the interpreter. For example, when you're calling a Python function, after a long run-around in ceval, PyObject_Call, the function object's function_call method, you'll finally get back to ceval which creates a frame via a lengthy call to PyFrame_New. The whole process is a mess of allocating, deconstructing, increfing, decrefing, and tag-checking.

jaegerpicker 13y ago

While this is an undeniably cool project from the tech side, I think it's usually a better idea to rewrite bottlenecks of the kind that this helps with as a c extension. It's a fairly easy process (MUCH easier then in Java for example) and only a small amount of code needs to be in c itself but you can get huge performance increases without changing the Cython environment. I've always thought that was one of python/ruby's greatest strength's is the easy C integration.

fernly 13y ago
I think you mean the "CPython environment"? "Cython" is something else.

bsimpson 13y ago

As a web developer, I've often heard neckbeards bickering about Python's performance, but haven't had a real point-of-reference to understand how bad it can be until recently. 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.

gregorsamza 13y ago
A dataset with "many long lists of numbers" sounds like an ideal use case for NumPy, have you tried using that?
- scardine 13y ago
  GAE allows only pure Python. No binary modules like NumPy.
  - kirubakaran 13y ago
    Numpy is supported https://developers.google.com/appengine/docs/python/tools/libraries27 https://developers.google.com/appengine/docs/python/tools/li...
  - corey 13y ago
    Python has an array class too: http://docs.python.org/2/library/array.html http://docs.python.org/2/library/array.html
- bsimpson 13y ago

freework 13y ago

Python is typically used to build applications that are IO bound. Squeezing more performance out of the interpreter is not going to translate to any real gains for most Python users these days.

dexterous 13y ago
I'm curious, what leads you to the conclusion that 'Python is typically used to build applications that are IO bound'? Also, what exactly are you referring to when you say 'IO bound'?
- bluedino 13y ago
  Python is commonly used in web services, where retrieving information from a database and transmitting the results via slow network connections are what takes up the most time, not processing the data in between with Python.
  - dexterous 13y ago
    I don't buy that. I've had enough people relate Python's roots in the sysad tool belt and it's application in processing large data sets to believe that it's intended use case could be that limited.
    - DrJosiah 13y ago
      And you shouldn't :) 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?
      - dexterous 13y ago

cwzwarich 13y ago

There are a couple of things you want to do (some of which overlap with the article): 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/61830429.pdf 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.

iskander 13y ago
>Rearrange your instruction bodies based on execution / transition frequencies to improve instruction cache performance. 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?
- mentat 13y ago
  Looks like he's contributed significantly to the Webkit javascript interpreter: https://www.webkit.org/blog/196/cameron-zwarich-is-a-webkit-reviewer/ https://www.webkit.org/blog/196/cameron-zwarich-is-a-webkit-...

jerf 13y ago

It seems to me over the past ten years I've heard this story so many times: "Python sucks. Let's do the obvious thing that makes it faster." Then, a month or two later, "I did the obvious thing and it's sometimes faster but often slower, net no gain or possible loss." to which the response is obviously "No sale." 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.)

iskander 13y ago
>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. 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.
- enupten 13y ago
  There is some truth here; even the militantly dynamic Common lisp has a blisteringly fast implementation (SBCL).

dschiptsov 13y ago

The answer is very simple: 1) Know what ought to be done - do it and send the patches. 2) Need "speed" - write that part in C.)

sherjilozair 13y ago
2) Need "speed" - write that part in C.) That's not so easy. Interfacing Python and C code is also incredibly hard, and no one true way exists.
- gizmo686 13y ago
  >That's not so easy. Interfacing Python and C code is also incredibly hard, and no one true way exists. 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.
  - lmm 13y ago
    If you use the CPython C API it's easy - but you also bind yourself closely to CPython. If you know performance is going to be important it's probably better to bite the bullet and use PyPy - which means you have to use the somewhat cruder cffi to interface with C code.
- briancurtin 13y ago
  I've done it numerous times over the last several years and while it's probably not trivial, it's definitely not hard. If you're looking for a "one true way", it's Python's C API.
- pekk 13y ago
  It might be incredibly hard if you do not know C.

catmanjan 13y ago

Haha oh my god Terry A. Davis commented on it! SQUAWK SQUAWK SQUAWK

fernly 13y ago

No mention of the somewhat confusingly named Cython [1]? It addresses the same issues in a different way. [1] http://en.wikipedia.org/wiki/Cython http://en.wikipedia.org/wiki/Cython

beagle3 13y ago

If you haven't already, LuaJIT's source code (and Mike Pall when asked) is a treasure trove of speedup ideas. 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.

fijal 13y ago
We have this optimization in PyPy (so yes, Python can do it). There is even a paper [0]. LuaJIT is a great source of inspiration but Python is just a huge language, which makes it much harder. http://www.maths.lth.se/matematiklth/vision/publdb/reports/pdf/ardo-bolz-etal-dls-12.pdf http://www.maths.lth.se/matematiklth/vision/publdb/reports/p...

mappu 13y ago

This is bikeshedding, but "The only hard problems in computer science are cache invalidation and naming things" - there's already a quite popular, multi-paradigm programming language named Falcon[1]. 1. http://www.falconpl.org/ http://www.falconpl.org/

simonh 13y ago
Sorry, but the two hard problems in programming are actually cache invalidation, naming things and off by one errors.

fijal 13y ago

The title is very misleading - it should be called "How fast can we make CPython", because it talks about compatibility with PyObject* and stuff. While I would argue that we can't make interpreted Python particularly fast, the actual topic in question is much harder than that.

xenonflash 13y ago

I don't think its correct to say the CPython is slow. What you can more accurately say about CPython is that the performance is highly variable. Some things are very fast, while others are comparatively slow. 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.

toolslive 13y ago
it really is a slow interpreter. Python comes with a pystone benchmark, and CPython is invariably the slowest of all interpreters. This being said, if you take a look at it's implementation, then it's immediately obvious why. The interpreter is a basically a simple C switch, with no optimization whatsoever. Simply threading the interpreter would make it about a factor 2 faster (at least that's what the experts claim you gain by threading)
- xenonflash 13y ago
  Pystone isn't a performance benchmark, or at least it isn't a useful one. It's more of a regression test to see if anything has changed between versions. It's not useful as a performance benchmark because it doesn't weight the results according to how much the individual features matter in real life. There are three versions of Python besides CPython that are in commercial use. Two are much slower than CPython (up to three times slower), and Pypy is (currently) faster in some applications and slower in others. 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.

int3 13y ago

Interesting approach. One criticism: The paper mentions that compile times max out at 1.1ms "for the most complex function" in the benchmark (AES), and therefore it is sufficient to just compile everything. However, those benchmarks seem too small to justify that conclusion.