I was recently trying to optimize some C code using cachegrind, and discovered that branch misprediction in an inner loop was the culprit. I began wondering how much anything similar could affect Python code. After all, especially in CPython, every opcode is going through hundreds of lines of ceval code, with a giant switch and multiple branches, and so on, so, how much difference could a branch at the Python level make?

To find out, I turned to the famous Stack Overflow question Why is processing a sorted array faster than an unsorted array? That question has a simple C++ test case where the code runs ~6x as fast on x86 and x86_64 platforms with most compilers, and it's been verified to be similar in other compiled languages like Java, C#, and go.

So, what about Python?

The code

The original question takes a 32K array of bytes, and sums the bytes that are >= 128:
    long long sum = 0;
    /* ... */
    for (unsigned c = 0; c < arraySize; ++c)
    {
        if (data[c] >= 128)
            sum += data[c];
    }
 
In Python terms:
    total = 0
    for i in data:
        if i >= 128:
            total += i
When run with a random array of bytes, this usually takes about 6x as long as when run with the same array pre-sorted. (Your mileage may vary, because there's a way the compiler can optimize away the loop for you, at least on x86 and x86_64, and some compilers will, depending on your optimization settings, figure that out for you. If you want to know more, read the linked question.)

So, here's a simple test driver:
    import functools
    import random
    import timeit

    def sumbig(data):
        total = 0
        for i in data:
            if i >= 128:
                total += i
        return total

    def test(asize, reps):
        data = bytearray(random.randrange(256) for _ in range(asize)
        t0 = timeit.timeit(functools.partial(sumbig, data), number=reps)
        t1 = timeit.timeit(functools.partial(sumbig, bytearray(sorted(data))), number=reps)
        print(t0, t1)

    if __name__ == '__main__':
        import sys
        asize = int(sys.argv[1]) if len(sys.argv) > 1 else 32768
        reps = int(sys.argv[2]) if len(sys.argv) > 2 else 1000
        test(asize, reps)
I tested this on a few different computers, using Apple pre-installed CPython 2.7.6, Python.org CPython 2.7.8 and 3.4.1, Homebrew CPython 3.4.0, and a custom build off trunk, and it pretty consistently saves about 12% to pre-sort the array. Nothing like the 84% savings in C++, but still, a lot more than you'd expect. After all, we're doing roughly 65x as much work in the CPython ceval loop than we were doing in the C++ loop, so you'd think the difference would be lost in the noise, and we're also doing much larger loops, so you'd think branch prediction wouldn't be helping as much in the first place. But if you watch the BR_MISP counters in Instruments, or do the equivalent with cachegrind, you'll see that it's mispredicting a lot more branches for the unsorted case than the sorted case—as in 1.9% of the total conditional branches in the ceval loop instead of 0.1%. Presumably, even though this is still pretty small, and nothing like what you see in C, the cost of the misprediction is also higher? It's hard to be sure…

You'd expect a much bigger benefit in the other Python implementations. Jython and IronPython compile to JVM and ILR code, which then gets the same kind of JIT recompilation as Java and C#, so if those JITs aren't smart enough to optimize away the branch with a conditional move instruction for Java and C#, they won't be for Python code either. PyPy is JIT-compiling directly from Python—plus, its JIT is itself driven by tracing, which can be hurt by the equivalent of branch misprediction at a higher level. And in fact I found a difference of 54% in Jython 2.5.1, 68% in PyPy 2.3.1 (both the 2.7 and 3.2 versions), and 72% in PyPy 2.4.0 (2.7 only).

C++ optimizations


There are a number of ways to optimize this in C, but they all amount to the same thing: find some way to do a bit of extra work to avoid the conditional branch—bit-twiddling arithmetic, a lookup table, etc. The lookup table seems like the most likely version to help in Python, so here it is:
    table = bytearray(i if i >= 128 else 0 for i in range(256))
    total = 0
    for i in a:
        total + table[i]
To put this inside a function, you'd want to build the table globally instead of once per call, then copy it to a local inside the function to avoid the slow name lookup inside the inner loop:
    _table = bytearray(i if i >= 128 else 0 for i in range(256))
    def sumbig_t(data):
        table = _table
        total = 0
        for i in a:
            total + table[i]
The sorted and unsorted arrays are now about the same speed. And for PyPy, that's about 13% faster than with the sorted data in the original version. For CPython, on the other hand, it's 33% slower. I also tried the various bit-twiddling optimizations; they're slightly slower than the lookup table in PyPy, and at least 250% slower in CPython.

So, what have we learned? Python, even CPython, can be affected by the same kinds of low-level performance problems as compiled languages. The alternative implementations can also handle those problems the same way. CPython can't… but then if this code were a bottleneck in your problem, you'd almost certainly be switching to PyPy or writing a C extension anyway, right?

Python optimizations

There's an obvious Python-specific optimization here—which I wouldn't even really call an optimization, since it's also a more Pythonic way of writing the code:
    total = sum(i for i in data if i >= 128)
This does in fact speed things up by about 13% in CPython, although it slows things down by 217% in PyPy. It leaves us with the same original difference between random and sorted arrays, and the same basic effects for applying the table or bit twiddling.

You'd think that taking two passes, applying the table to the data and then summing the result, would obviously be slower, right? And normally you'd be right; a quick test shows a 31% slowdown. But if you think about it, when we're dealing with bytes, applying the table can be done with bytes.translate. And of course the sum is now just summing a builtin sequence, not a generator. So we effectively have two C loops instead of one Python loop, which may be a win:
    def sumbig_s(data):
        return sum(data.translate(bytearray(_table)))
For CPython, this saves about 83% of the time vs. the original sumbig's speed on unsorted data. And the difference between sorted and unsorted data is very small, so it's still an 81% savings on sorted data. However, for PyPy, it's 4% slower for unsorted data, and you lose the gain for sorted data.

If you think about it, while we're doing that pass, we might as well just remove the small values instead of mapping them to 0:
    def sumbig_s2(data):
        return sum(data.translate(bytearray(_table), bytearray(range(128))))
That ought to make the first loop a little slower, and affected by branch misprediction, while making the second loop twice as fast, right? And that's exactly what we see, in CPython. For unsorted data, it cuts 90% off the original code, and now sorting it gives us another 36% improvement. That's near PyPy speeds. On the other hand, in PyPy, it's just as slow for sorted data as the previous fix, and twice as slow for unsorted data, so it's even more of a pessimization.

What about using numpy? The obvious implementation is:
    def sumbig_n(data):
        data = np.array(data)
        return data[data>=128].sum()
In CPython, this cuts 90% of the speed off the original code for unsorted data, and for sorted data it cuts off another 48%. Either way, it's the fastest solution so far, even faster than using PyPy. But we can do the equivalent of translating the if to arithmetic or bit-twiddling too. I tried tricks like ~((data-128)>>31)&data, but the fastest turned out to be the simplest:
    def sumbig_n2(data):
        data = np.array(data)
        return (data&(data>=128)).sum()
Now just as fast for unsorted data as for sorted, cutting 94% of the time off the original.

Conclusions

So, what does this mean for you?

Well, most of the time, nothing. If your code is too slow, and it's doing arithmetic inside a loop, and the algorithm itself can't be improved, the first step should almost always be converting to numpy, PyPy, or C, and often that'll be the last step as well.

But it's good to know that the same issues that apply to low-level code still affect Python, and in some cases (especially if you're already using numpy or PyPy) the same solutions may help.
3

View comments

  1. This comment has been removed by the author.

    ReplyDelete
  2. It is very nice blog. The content of this blog is helpful for us with the informative and valuable information. Share your information and keep going on. Click Here: Python Online Training || Python Online Course

    ReplyDelete
  3. Thank you for sharing such a useful information for us and it is very nice blog. Click here: Python Online Training

    ReplyDelete
Hybrid Programming
Hybrid Programming
5
Greenlets vs. explicit coroutines
Greenlets vs. explicit coroutines
6
ABCs: What are they good for?
ABCs: What are they good for?
1
A standard assembly format for Python bytecode
A standard assembly format for Python bytecode
6
Unified call syntax
Unified call syntax
8
Why heapq isn't a type
Why heapq isn't a type
1
Unpacked Bytecode
Unpacked Bytecode
3
Everything is dynamic
Everything is dynamic
1
Wordcode
Wordcode
1
For-each loops should define a new variable
For-each loops should define a new variable
4
Views instead of iterators
Views instead of iterators
2
How lookup _could_ work
How lookup _could_ work
2
How lookup works
How lookup works
7
How functions work
How functions work
2
Why you can't have exact decimal math
Why you can't have exact decimal math
2
Can you customize method resolution order?
Can you customize method resolution order?
1
Prototype inheritance is inheritance
Prototype inheritance is inheritance
1
Pattern matching again
Pattern matching again
The best collections library design?
The best collections library design?
1
Leaks into the Enclosing Scope
Leaks into the Enclosing Scope
2
Iterable Terminology
Iterable Terminology
8
Creating a new sequence type is easy
Creating a new sequence type is easy
2
Going faster with NumPy
Going faster with NumPy
2
Why isn't asyncio too slow?
Why isn't asyncio too slow?
Hacking Python without hacking Python
Hacking Python without hacking Python
1
How to detect a valid integer literal
How to detect a valid integer literal
2
Operator sectioning for Python
Operator sectioning for Python
1
If you don't like exceptions, you don't like Python
If you don't like exceptions, you don't like Python
2
Spam, spam, spam, gouda, spam, and tulips
Spam, spam, spam, gouda, spam, and tulips
And now for something completely stupid…
And now for something completely stupid…
How not to overuse lambda
How not to overuse lambda
1
Why following idioms matters
Why following idioms matters
1
Cloning generators
Cloning generators
5
What belongs in the stdlib?
What belongs in the stdlib?
3
Augmented Assignments (a += b)
Augmented Assignments (a += b)
11
Statements and Expressions
Statements and Expressions
3
An Abbreviated Table of binary64 Values
An Abbreviated Table of binary64 Values
1
IEEE Floats and Python
IEEE Floats and Python
Subtyping and Ducks
Subtyping and Ducks
1
Greenlets, threads, and processes
Greenlets, threads, and processes
6
Why don't you want getters and setters?
Why don't you want getters and setters?
8
The (Updated) Truth About Unicode in Python
The (Updated) Truth About Unicode in Python
1
How do I make a recursive function iterative?
How do I make a recursive function iterative?
1
Sockets and multiprocessing
Sockets and multiprocessing
Micro-optimization and Python
Micro-optimization and Python
3
Why does my 100MB file take 1GB of memory?
Why does my 100MB file take 1GB of memory?
1
How to edit a file in-place
How to edit a file in-place
ADTs for Python
ADTs for Python
5
A pattern-matching case statement for Python
A pattern-matching case statement for Python
2
How strongly typed is Python?
How strongly typed is Python?
How do comprehensions work?
How do comprehensions work?
1
Reverse dictionary lookup and more, on beyond z
Reverse dictionary lookup and more, on beyond z
2
How to handle exceptions
How to handle exceptions
2
Three ways to read files
Three ways to read files
2
Lazy Python lists
Lazy Python lists
2
Lazy cons lists
Lazy cons lists
1
Lazy tuple unpacking
Lazy tuple unpacking
3
Getting atomic writes right
Getting atomic writes right
Suites, scopes, and lifetimes
Suites, scopes, and lifetimes
1
Swift-style map and filter views
Swift-style map and filter views
1
Inline (bytecode) assembly
Inline (bytecode) assembly
Why Python (or any decent language) doesn't need blocks
Why Python (or any decent language) doesn't need blocks
18
SortedContainers
SortedContainers
1
Fixing lambda
Fixing lambda
2
Arguments and parameters, under the covers
Arguments and parameters, under the covers
pip, extension modules, and distro packages
pip, extension modules, and distro packages
Python doesn't have encapsulation?
Python doesn't have encapsulation?
3
Grouping into runs of adjacent values
Grouping into runs of adjacent values
dbm: not just for Unix
dbm: not just for Unix
How to use your self
How to use your self
1
Tkinter validation
Tkinter validation
7
What's the deal with ttk.Frame.__init__(self, parent)
What's the deal with ttk.Frame.__init__(self, parent)
1
Does Python pass by value, or by reference?
Does Python pass by value, or by reference?
9
"if not exists" definitions
"if not exists" definitions
repr + eval = bad idea
repr + eval = bad idea
1
Solving callbacks for Python GUIs
Solving callbacks for Python GUIs
Why your GUI app freezes
Why your GUI app freezes
21
Using python.org binary installations with Xcode 5
Using python.org binary installations with Xcode 5
defaultdict vs. setdefault
defaultdict vs. setdefault
1
Lazy restartable iteration
Lazy restartable iteration
2
Arguments and parameters
Arguments and parameters
3
How grouper works
How grouper works
1
Comprehensions vs. map
Comprehensions vs. map
2
Basic thread pools
Basic thread pools
Sorted collections in the stdlib
Sorted collections in the stdlib
4
Mac environment variables
Mac environment variables
Syntactic takewhile?
Syntactic takewhile?
4
Can you optimize list(genexp)
Can you optimize list(genexp)
MISRA-C and Python
MISRA-C and Python
1
How to split your program in two
How to split your program in two
How methods work
How methods work
3
readlines considered silly
readlines considered silly
6
Comprehensions for dummies
Comprehensions for dummies
Sockets are byte streams, not message streams
Sockets are byte streams, not message streams
9
Why you don't want to dynamically create variables
Why you don't want to dynamically create variables
7
Why eval/exec is bad
Why eval/exec is bad
Iterator Pipelines
Iterator Pipelines
2
Why are non-mutating algorithms simpler to write in Python?
Why are non-mutating algorithms simpler to write in Python?
2
Sticking with Apple's Python 2.7
Sticking with Apple's Python 2.7
Blog Archive
About Me
About Me
Loading
Dynamic Views theme. Powered by Blogger. Report Abuse.