10

I'm a long-time Python user. A few years ago, I started learning C++ to see what it could offer in terms of speed. During this time, I would continue to use Python as a tool for prototyping. This, it seemed, was a good system: agile development with Python, fast execution in C++.

Recently, I've been using Python more and more again, and learning how to avoid all of the pitfalls and anti-patterns that I was quick to use in my earlier years with the language. It's my understanding that using certain features (list comprehensions, enumerations, etc.) can increase performance.

But are there technical limitations or language features that prevent my Python script from being as fast as an equivalent C++ program?

  • 2
    Yes, it can. See PyPy for the state of the art in Python compilers. – Greg Hewgill Jul 29 '14 at 20:12
  • 5
    All variables in python are polymorphic meaning the type of the variable is only known at runtime. If you see (assuming integers) x + y in C-like languages they do an integer addition. In python there will be a switch on the variable types on x and y and then the appropriate addition function is selected and then there will be an overflow check and then there is the addition. Unless python learns static typing this overhead will never go away. – nwp Jul 29 '14 at 22:03
  • 1
    @nwp No, that one's easy, see PyPy. Trickier, still open, problems include: How to overcome the start up latency of JIT compilers, how to avoid allocations for complicated long-lived object graphs, and how to make good use of the cache in general. – user7043 Jul 29 '14 at 22:46
11

I kind of hit this wall myself when I took a full-time Python programming job a couple years ago. I love Python, I really do, but when I started to do some performance tuning, I had some rude shocks.

The strict Pythonistas can correct me, but here are the things I found, painted in very broad strokes.

  • Python memory usage is kind of scary. Python represents everything as a dict -- which is extremely powerful, but has a result that even simple data types are gigantic. I remember the character "a" took 28 bytes of memory. If you're using big data structures in Python, make sure to rely on numpy or scipy, because they are backed by direct byte-array implementation.

That has a performance impact, because it means there are extra levels of indirection at run time, in addition to slogging around huge amounts of memory compared to other languages.

  • Python does have a global interpreter lock, which means that for the most part, processes are running single-threaded. There may be libraries that distribute tasks across processes, but we were spinning up 32 or so instances of our python script and running each single threaded.

Others can talk to the execution model, but Python is a compile-at-runtime and then interpreted, which means it doesn't go all the way to machine code. That also has a performance impact. You can easily link in C or C++ modules, or find them, but if you just run straight up Python, it's going to have a performance hit.

Now, in web service benchmarks, Python compares favorably to the other compile-at-runtime languages like Ruby or PHP. But it's pretty far behind most of the compiled languages. Even the languages that compile to intermediate language and run in a VM (like Java or C#) do much, much better.

Here is a really interesting set of benchmark tests that I refer to occasionally:

http://www.techempower.com/benchmarks/

(All that said, I still love Python dearly, and if I get the chance to choose the language I'm working in, it's my first choice. Most of the time, I'm not constrained by crazy throughput requirements anyway.)

  • 2
    The string "a" is not a good example for the first bullet point. A Java string also has considerable overhead for single character strings, and but it's constant overhead that amortizes quite well as the string grows in length (one to four bytes oer characters depending on version, build options, and string contents). You're right about user-defined objects though, at least those that don't use __slots__. PyPy should do much better in this regard but I don't know enough to judge. – user7043 Jul 29 '14 at 22:53
  • 1
    The second problem you're pointing out is related only to specific implementation and not inherent to language. The first problem requires explanation: what "weighs" 28 bytes is not the character itself but the fact that it's been packed in a string class, coming with it's own methods and properties. Representing single character as bytes array (literal b'a') "only" weighs 18 bytes on Python 3.3 and I'm sure there are more ways to optimize character storage in memory if your application really needs it. – Red Jul 30 '14 at 8:52
  • C# can compile natively (e.g. upcoming MS tech, Xamarin for iOS). – Den Aug 18 '14 at 8:03
13

The Python reference implementation is the “CPython” interpreter. It tries to be reasonably fast, but it does not currently employ advanced optimizations. And for many usage scenarios, this is a good thing: The compilation to some intermediary code happens immediately before runtime, and each time the program is executed the code is compiled anew. So the time needed for optimization has to be weighed against the time gained by optimizations – if there isn't a net gain, the optimization is worthless. For a very long-running program, or a program with very tight loops, employing advanced optimizations would be useful. However, CPython is used for some jobs that preclude aggressive optimization:

  • Short-running scripts, used e.g. for sysadmin tasks. Many operating systems like Ubuntu build a good part of their infrastructure on top of Python: CPython is fast enough for the job, but has virtually no start-up time. As long as it's faster than bash, it's good.

  • CPython must have clear semantics, as it is a reference implementation. This allows simple optimizations such as “optimize the implementation of the foo operator” or “compile list comprehensions to faster bytecode”, but will generally preclude optimizations that destroy information, such as inlining functions.

Of course, there are more Python implementations than just CPython:

  • Jython is built on top of the JVM. The JVM can interpret or JIT-compile the provided bytecode, and has profile-guided optimizations. It suffers from high start-up time, and it takes a while until the JIT kicks in.

  • PyPy is a state of the art, JITting Python VM. PyPy is written in RPython, a restricted subset of Python. This subset removes some expressiveness from Python, but allows the type of any variable to be statically inferred. The VM written in RPython can then be transpiled to C, which gives RPython C-like performance. However, RPython is still more expressive than C, which allows faster development of new optimizations. PyPy is an example of compiler bootstrapping. PyPy (not RPython!) is mostly compatible to the CPython reference implementation.

  • Cython is (like RPython) an incompatible Python dialect with static typing. It also transpiles to C code, and is able to easily generate C extensions for the CPython interpreter.

If you are willing to translate your Python code to Cython or RPython, then you'll get C-like performance. However, they shouldn't be understood as “a subset of Python”, but rather as “C with Pythonic syntax”. If you switch to PyPy, your vanilla Python code will get a considerable speed boost, but will also be unable to interface with extensions written in C or C++.

But what properties or features prevent vanilla Python from reaching C-like levels of performance, aside from long start-up times?

  • Contributors and funding. Unlike Java or C#, there is no single driving company behind the language with an interest to make this language the best of its class. This restricts development to mainly to volunteers, and occasional grants.

  • Late binding and the lack of any static typing. Python allows us to write crap like this:

    import random
    
    # foo is a function that returns an empty list
    def foo(): return []
    
    # foo is a function, right?
    # this ought to be equivalent to "bar = foo"
    def bar(): return foo()
    
    # ooh, we can reassign variables to a different type – randomly
    if random.randint(0, 1):
       foo = 42
    
    print bar()
    # why does this blow up (in 50% of cases)?
    # "foo" was a function while "bar" was defined!
    # ah, the joys of late binding
    

    In Python, any variable can be reassigned at any time. This prevents caching or inlining; any access has to go through the variable. This indirection weighs down performance. Of course: if your code doesn't do such insane things so that each variable can be given a definitive type before compilation and each variable is assigned only once, then – in theory – a more efficient execution model could be chosen. A language with this in mind would provide some way to mark identifiers as constants, and at least allow optional type annotations (“gradual typing”).

  • A questionable object model. Unless slots are used, it's hard to figure out which fields an object has (a Python object is essentially a hash table of fields). And even once we're there, we still have no idea what types these fields have. This prevents representing objects as tightly packed structs, as is the case in C++. (Of course, C++'s representation of objects isn't ideal either: due to the struct-like nature, even private fields belong to the public interface of an object.)

  • Garbage collection. In many cases, GC could be avoided completely. C++ allows us to statically allocate objects which are destroyed automatically when the current scope is left: Type instance(args);. Until then, the object is alive and can be lent to other functions. This is usually done via “pass-by-reference”. Languages like Rust allow the compiler to statically check that no pointer to such an object exceeds the lifetime of the object. This memory management scheme is totally predictable, highly efficient, and suits most cases without complicated object graphs. Unfortunately, Python was not designed with memory management in mind. In theory, escape analysis can be used to find cases where GC can be avoided. In practice, simple method chains such as foo().bar().baz() will have to allocate a large number of short-lived objects on the heap (generational GC is one way to keep this problem small).

    In other cases, the programmer may already know the final size of some object such as a list. Unfortunately, Python does not offer a way to communicate this when creating a new list. Instead, new items will be pushed onto the end, which might require multiple reallocations. A few notes:

    • Lists of a specific size can be created like fixed_size = [None] * size. However, the memory for the objects inside that list will have to be allocated seperately. Contrast C++, where we can do std::array<Type, size> fixed_size.

    • Packed arrays of a specific native type can be created in Python via the array builtin module. Also, numpy offers efficient representations of data buffers with specific shapes for native numeric types.

Summary

Python was designed for ease of use, not for performance. Its design makes creating highly efficient implementation rather difficult. If the programmer abstains from problematic features, then a compiler understanding the remaining idioms will be able to emit efficient code that can rival C in performance.

8

Yes. The primary problem is that the language is defined to be dynamic- that is, you never know what you're doing until you're about to do it. That makes it very hard to produce efficient machine code, because you don't know what to produce machine code for. JIT compilers can do some work in this area but it's never comparable to C++ because the JIT compiler simply can't spend time and memory running, since that's time and memory you're not spending running your program, and there are hard limits on what they can achieve without breaking the dynamic language semantics.

I'm not going to claim that this is an unacceptable tradeoff. But it is fundamental to the nature of Python that real implementations will never be as fast as C++ implementations.

8

There are three main factors that affect the performance of all dynamic languages, some more than others.

  1. Interpretive overhead. At runtime there is some kind of byte code rather than machine instructions and there is a fixed overhead to executing this code.
  2. Dispatch overhead. The target for a function call is not known until runtime, and finding out which method to call carries a cost.
  3. Memory management overhead. Dynamic languages store stuff in objects that have to be allocated and deallocated, and that carries performance overhead.

For C/C++ the relative costs of these 3 factors are almost zero. Instructions are executed directly by the processor, dispatch takes at most an indirection or two, heap memory is never allocated unless you say so. Well-written code may approach assembly language.

For C#/Java with JIT compilation the first two are low but garbage collected memory has a cost. Well written code may approach 2x C/C++.

For Python/Ruby/Perl the cost of all three of these factors is relatively high. Think 5x compared to C/C++ or worse. (*)

Remember that runtime library code may well be written in the same language as your programs and have the same performance limitations.


(*) As Just-In_Time (JIT) compilation is extended to these languages they too will approach (typically 2x) the speed of well-written C/C++ code.

It should also be noted that once the gap is narrow (between competing languages), then differences are dominated by algorithms and implementation details. JIT code may beat C/C++ and C/C++ may beat assembly language because it's just easier to write good code.

  • "Remember that runtime library code may well be written in the same language as your programs and have the same performance limitations." and "For Python/Ruby/Perl the cost of all three of these factors is relatively high. Think 5x compared to C/C++ or worse." Actually, that is not true. For example, the Rubinius Hash class (one of the core datastructures in Ruby) is written in Ruby, and it performs comparably, sometimes even faster, than YARV's Hash class which is written in C. And one of the reasons is that large parts of Rubinius's runtime system are written in Ruby, so that they can … – Jörg W Mittag Aug 18 '14 at 0:57
  • … for example be inlined by the Rubinius compiler. Extreme examples are the Klein VM (a metacircular VM for Self) and the Maxine VM (a metacircular VM for Java), where everything, even the method dispatch code, garbage collector, memory allocator, primitive types, core datastructures and algorithms are written in Self or Java. That way, even parts of the core VM can be inlined into usercode, and the VM can re-compile and re-optimize itself using runtime feedback from the userprogram. – Jörg W Mittag Aug 18 '14 at 1:01
  • @JörgWMittag: Still true. Rubinius has JIT, and JIT code often beats C/C++ on individual benchmarks. I can't find any evidence that this metacircular stuff does much for speed in the absence of JIT. [See edit for clarity about JIT.] – david.pfx Aug 18 '14 at 1:56
1

But are there technical limitations or language features that prevent my Python script from being as fast as an equivalent C++ program?

No. It's just a question of money and resources poured into making C++ run fast vs. money and resources poured into making Python run fast.

For example, when the Self VM came out, it was not only the fastest dynamic OO language, it was the fastest OO language period. Despite being an incredibly dynamic language (much more so than Python, Ruby, PHP or JavaScript, for example), it was faster than most of the C++ implementations that were available.

But then Sun canceled the Self project (a mature general purpose OO language for developing large systems) to focus on a small scripting language for animated menus in TV set top boxes (you might have heard about it, it's called Java), there was no more funding. At the same time, Intel, IBM, Microsoft, Sun, Metrowerks, HP et al. spent vast amounts of money and resources making C++ fast. CPU manufacturers added features to their chips to make C++ fast. Operating Systems were written or modified to make C++ fast. So, C++ is fast.

I am not terribly familiar with Python, I'm more a Ruby person, so I will give an example from Ruby: the Hash class (equivalent in function and importance to dict in Python) in the Rubinius Ruby implementation is written in 100% pure Ruby; yet it competes favorably and sometimes even outperforms the Hash class in YARV which is written in hand-optimized C. And compared to some of the commercial Lisp or Smalltalk systems (or the afore-mentioned Self VM), Rubinius's compiler isn't even that clever.

There is nothing inherent in Python that makes it slow. There are features in today's processors and operating systems that hurt Python (e.g. virtual memory is known to be terrible for garbage collection performance). There are features that help C++ but don't help Python (modern CPUs try to avoid cache misses, because they are so expensive. Unfortunately, avoiding cache misses is hard when you have OO and polymorphism. Rather, you should reduce the cost of cache misses. The Azul Vega CPU, which was designed for Java, does this.)

If you spend as much money, research and resources on making Python fast, as was done for C++, and you spend as much money, research and resources on making operating systems that make Python programs run fast as was done for C++ and you spend as much money, research and resources on making CPUs that make Python programs run fast as was done for C++, then there is no doubt in my mind that Python could reach comparable performance to C++.

We have seen with ECMAScript what can happen if just one player gets serious about performance. Within a year, we had basically a 10x performance increase across the board for all major vendors.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.