6 ms·

Python Patterns - An Optimization Anecdote

74 points by niyazpk 16y ago

rix0r 16y ago
The first thing that stuck out to me like a sore thumb was the string-concatenation-in-a-loop. Though the author was aware of its consequences he only addressed it late in the article, optimizing relatively trivial stuff like variable lookups first. And then he did so in a rather strange way, instead of adding string fragments to a list and then join()ing them. Not sure how fast that loop would be in Python compared to the implied loop&join but I sure would have liked to see them compared.
- RiderOfGiraffes 16y ago
  > Not sure how fast that loop would be in Python > compared to the implied loop&join but I sure > would have liked to see them compared. Why don't you try it and tell us the results?
- StavrosK 16y ago
  Yeah, seriously. "".join((chr(x) for x in chars)) would be the first thing I did (I'm not sure if comprehensions are faster than generators, they probably are, so I'd test for that as well.
- Nitramp 16y ago
  Indeed seems strange to micro optimize all that stuff without first fixing the obvious quadratic runtime part. By the way, is there no mutable string object (à la Java's StringBuilder/Buffer) in Python?
Devilboy 16y ago
I hope that one day soon our compilers will be smart enough to optimize simple things like this automatically, so we can focus more on writing for clarity. This seems like exactly the kind of thing a next-gen compiler should be able to optimize.
- edanm 16y ago
  I'm not sure it's so possible, considering the dynamic nature of Python. Consider one of the biggest problems - dynamic lookups. Calling a function like "chr", which is looked up dynamically and found in the global scope each time, takes a lot of time. Just adding a local variable which has the same value (i.e. lchr = chr) already gives a speedup. How can an optimizer fix this? Technically, a new lookup must be performed each time, since you never know if "chr" has been mapped to something new during the iterations.
  - riffraff 16y ago
    you can lookup once and inline the method, and only keep a flag to check if you need to invalidate that. Pypy & other jits al do this kind of things all the time :) But you don't need a jit: you can partially execute the code and determine that no changes were happening in the referenced globals, thus the inlining becomes possible. There is quite a bit of literature on the issue of using partial evaluation for optimizing dynamic/reflective languages.
    - edanm 16y ago
      Interesting. What are the best sources for learning what kind of optimizations are actually implemented in practice in Python?
      - riffraff 16y ago
        well neither of the above, in standard python, but the pypy project has _a lot_ of interesting stuff http://codespeak.net/pypy/dist/pypy/doc/extradoc.html http://codespeak.net/pypy/dist/pypy/doc/extradoc.html
  - derefr 16y ago
    > you never know if "chr" has been mapped to something new during the iterations. Why must this be true? Scan the loop body, find nothing that redefines chr, create a local variable holding it at the beginning of the loop. The same goes for all identifiers mentioned in the loop.
edanm 16y ago
I once found myself writing a python program to calculate Poker hands. It was pretty fun to write - it generated, for any given hand you hold, every possible way the game can go forward, and generated statistics about how many times you win (against 1 opponent only, who could be holding anything.) The program initially ran for 20 minutes on each hand. I worked a day on optimizing it, and got it down to around 1-2 minutes per hand, so I learned a few tricks to make things quicker. Lessons learned: 1. Local lookups are much faster. 2. Anything that you can somehow offload to a c-loop, makes things much faster. 3. Surprisingly, the fastest construct for building a new list was always list comprehension (e.g. [x for x in calc(l) or whatever.) This was far faster than a regular ol' for-loop, of course, but was also faster than using map's and reduce's.
- devinj 16y ago
  Point 3 is weakened by the fact that map can indeed be faster. http://codepad.org/SzXcubXy http://codepad.org/SzXcubXy -- in fact, point 2 and point 3 are in conflict, because map() does use a C-loop, whereas list comprehensions do not. As it turns out, point 2 was the correct one. Also, and this is just on a more minor, pedantic note, list comprehensions basically are regular for loops, except with the use of the list-append opcode instead of a getattr-call pair. This produces a minor speedup, but it's nothing to write home about, honest. (using a different pastebin because it has a feature I needed): http://ideone.com/dT1LG http://ideone.com/dT1LG . The story is a bit different on 3.x, where list comps are implemented very differently: http://ideone.com/58FGZ http://ideone.com/58FGZ
  - edanm 16y ago
    First off, I'm really no expert in Python or optimizations - I'm only reporting on observations. Having said that, I was pretty surprised that the list comprehensions ran faster than map, exactly because of point 2 - I had assumed that map used a c-loop, whereas list comprehensions did not. Unfortunately, I don't have that code sitting around anywhere so I can't redo the tests - I just remember being very surprised by those results.
    - 16y ago
codefisher 16y ago
For those interested, the author of this was actually Guido himself. I would have used "".join(map(chr, list)) myself. But I am not sure that was support in the version of python available at the time. It is equivalent to f6. To some of those talking about the dynamic nature of python means you have to look up chr every time, there is a way to stop that, see this project http://github.com/rfk/promise/ http://github.com/rfk/promise/
nene 16y ago
I decided to try writing the same thing in JavaScript and discovered something really strange. My first idea was: numbers.map(function(x){return String.fromCharCode(x);}).join(""); This was pretty fast already, but why not eliminate the anonymous function completely and pass String.fromCharCode directly to map(): numbers.map(String.fromCharCode).join(""); I timed it and... ...this was ~100 times slower than the previous version. WTF! Somehow passing this native function directly to Array.map() is way slower than wrapping it inside another function and passing that to Array.map(). I have tested it so far in Chrome, Firefox and Opera - the results are the same. I also tried forEach(), which behaves similarly. Does anybody have an idea why this is so? Update: I tried the same with Math.round and Math.sin, and with these the results were as one would expect: passing the function to Array.map() directly was a little bit faster than using intermediate anonymous function. So it seems the problem is with String.fromCharCode specifically.
- lysium 16y ago
  Just a guess: your anonymous function cannot be redefined (because there is no name), but String.fromCharCode could potentially be. Thus, a similar reason as mentioned in the article for global vs. local variables. One would think that String.fromCharCode is looked up only once, though.
  - nene 16y ago
    That's exactly what I was thinking: * In the first version each time the anonymous function is executed interpreter has to lookup String and from it the fromCharCode method => 2n lookups. * In the second version the String and fromCharCode have to be lookud up only once => 2 lookups. Therefore according to slow-lookups-theory the first version should be slower. Except when I measure it, the opposite turns out to be true.
  - pornel 16y ago
    Actually it's the opposite. When you pass String.fromCharCode directly, then you're passing reference (not name) to that particular implementation, and it can't change. When you pass anonymous function, then every execution of that function needs to look up `String.fromCharCode` (anonymous functions save scope, not references). I'm surprised by the benchmark as well. I suspect it may be because calls to native functions are handled differently from calls to JS functions, and JS engine is able to optimize call inside anonymous function (create trace/JIT and inline it), but not when calling by reference (and perhaps keeps calling it by some expensive proxy object).
RyanMcGreal 16y ago
Why not just: def f(list): return ''.join([chr(l) for l in list])
- Goladus 16y ago
  This would be my default approach as well. I'd be interested to see how it compares-- my guess is that it would be equivalent to or slightly faster than f6(), and slower than the version that uses the array library.
  - RyanMcGreal 16y ago
    From the article, I'm guessing the author was using a version <2.x. Incidentally, I ran my function and f6 from the article on a list of 9600 integers using Python 2.6.3. f6 ran in 0.00303250832159 seconds and my function ran in 0.00421450212248 seconds.
  - petdog 16y ago
    Actually, map is still faster: In [24]: timeit ''.join(map(chr, ll)) 100000 loops, best of 3: 3.91 us per loop In [25]: timeit ''.join([chr(i) for i in ll]) 100000 loops, best of 3: 5.85 us per loop In [26]: timeit ''.join(chr(i) for i in ll) 100000 loops, best of 3: 7.79 us per loop
- zephyrfalcon 16y ago
  Because it's an old article. Admittedly, there's no easy way to know this, because it has no date, but believe me, it's been around for ages. At the very least, it predates the silly str.join method (and new-style classes and string methods altogether). However, before that, there was the string module, which had the join() function. This article probably relates to it in some way; I think that either it predates string.join (I'm not sure when that was added to Python, but it's been around since at least 1.4), or it clarifies how it was implemented. The author is Guido van Rossum, by the way (another thing that isn't mentioned in the article).
  - dish 16y ago
rmc 16y ago
Incidentally, are there any programmes that can scan your python functions and suggest improvements that are in this article? e.g. any programme that'll suggest referencing global names to the local namespace, using map etc.?
danielh 16y ago
It's a whole different story if the input gets longer and the quadratic complexity kicks in. Just change the testdata like this: testdata = range(256)*100 Result: f1 5.539 f2 40.747 f3 5.072 f4 5.311 f5 0.068 f6 3.304 f7 1.431

74 points by niyazpk 16y ago

rix0r 16y ago

The first thing that stuck out to me like a sore thumb was the string-concatenation-in-a-loop. Though the author was aware of its consequences he only addressed it late in the article, optimizing relatively trivial stuff like variable lookups first. And then he did so in a rather strange way, instead of adding string fragments to a list and then join()ing them. Not sure how fast that loop would be in Python compared to the implied loop&join but I sure would have liked to see them compared.

RiderOfGiraffes 16y ago
> Not sure how fast that loop would be in Python > compared to the implied loop&join but I sure > would have liked to see them compared. Why don't you try it and tell us the results?
StavrosK 16y ago
Yeah, seriously. "".join((chr(x) for x in chars)) would be the first thing I did (I'm not sure if comprehensions are faster than generators, they probably are, so I'd test for that as well.
Nitramp 16y ago
Indeed seems strange to micro optimize all that stuff without first fixing the obvious quadratic runtime part. By the way, is there no mutable string object (à la Java's StringBuilder/Buffer) in Python?

Devilboy 16y ago

I hope that one day soon our compilers will be smart enough to optimize simple things like this automatically, so we can focus more on writing for clarity. This seems like exactly the kind of thing a next-gen compiler should be able to optimize.

edanm 16y ago
I'm not sure it's so possible, considering the dynamic nature of Python. Consider one of the biggest problems - dynamic lookups. Calling a function like "chr", which is looked up dynamically and found in the global scope each time, takes a lot of time. Just adding a local variable which has the same value (i.e. lchr = chr) already gives a speedup. How can an optimizer fix this? Technically, a new lookup must be performed each time, since you never know if "chr" has been mapped to something new during the iterations.
- riffraff 16y ago
  you can lookup once and inline the method, and only keep a flag to check if you need to invalidate that. Pypy & other jits al do this kind of things all the time :) But you don't need a jit: you can partially execute the code and determine that no changes were happening in the referenced globals, thus the inlining becomes possible. There is quite a bit of literature on the issue of using partial evaluation for optimizing dynamic/reflective languages.
  - edanm 16y ago
    Interesting. What are the best sources for learning what kind of optimizations are actually implemented in practice in Python?
    - riffraff 16y ago
      well neither of the above, in standard python, but the pypy project has _a lot_ of interesting stuff http://codespeak.net/pypy/dist/pypy/doc/extradoc.html http://codespeak.net/pypy/dist/pypy/doc/extradoc.html
- derefr 16y ago
  > you never know if "chr" has been mapped to something new during the iterations. Why must this be true? Scan the loop body, find nothing that redefines chr, create a local variable holding it at the beginning of the loop. The same goes for all identifiers mentioned in the loop.

edanm 16y ago

I once found myself writing a python program to calculate Poker hands. It was pretty fun to write - it generated, for any given hand you hold, every possible way the game can go forward, and generated statistics about how many times you win (against 1 opponent only, who could be holding anything.) The program initially ran for 20 minutes on each hand. I worked a day on optimizing it, and got it down to around 1-2 minutes per hand, so I learned a few tricks to make things quicker. Lessons learned: 1. Local lookups are much faster. 2. Anything that you can somehow offload to a c-loop, makes things much faster. 3. Surprisingly, the fastest construct for building a new list was always list comprehension (e.g. [x for x in calc(l) or whatever.) This was far faster than a regular ol' for-loop, of course, but was also faster than using map's and reduce's.

devinj 16y ago
Point 3 is weakened by the fact that map can indeed be faster. http://codepad.org/SzXcubXy http://codepad.org/SzXcubXy -- in fact, point 2 and point 3 are in conflict, because map() does use a C-loop, whereas list comprehensions do not. As it turns out, point 2 was the correct one. Also, and this is just on a more minor, pedantic note, list comprehensions basically are regular for loops, except with the use of the list-append opcode instead of a getattr-call pair. This produces a minor speedup, but it's nothing to write home about, honest. (using a different pastebin because it has a feature I needed): http://ideone.com/dT1LG http://ideone.com/dT1LG . The story is a bit different on 3.x, where list comps are implemented very differently: http://ideone.com/58FGZ http://ideone.com/58FGZ
- edanm 16y ago
  First off, I'm really no expert in Python or optimizations - I'm only reporting on observations. Having said that, I was pretty surprised that the list comprehensions ran faster than map, exactly because of point 2 - I had assumed that map used a c-loop, whereas list comprehensions did not. Unfortunately, I don't have that code sitting around anywhere so I can't redo the tests - I just remember being very surprised by those results.
  - 16y ago

codefisher 16y ago

For those interested, the author of this was actually Guido himself. I would have used "".join(map(chr, list)) myself. But I am not sure that was support in the version of python available at the time. It is equivalent to f6. To some of those talking about the dynamic nature of python means you have to look up chr every time, there is a way to stop that, see this project http://github.com/rfk/promise/ http://github.com/rfk/promise/

nene 16y ago

I decided to try writing the same thing in JavaScript and discovered something really strange. My first idea was: numbers.map(function(x){return String.fromCharCode(x);}).join(""); This was pretty fast already, but why not eliminate the anonymous function completely and pass String.fromCharCode directly to map(): numbers.map(String.fromCharCode).join(""); I timed it and... ...this was ~100 times slower than the previous version. WTF! Somehow passing this native function directly to Array.map() is way slower than wrapping it inside another function and passing that to Array.map(). I have tested it so far in Chrome, Firefox and Opera - the results are the same. I also tried forEach(), which behaves similarly. Does anybody have an idea why this is so? Update: I tried the same with Math.round and Math.sin, and with these the results were as one would expect: passing the function to Array.map() directly was a little bit faster than using intermediate anonymous function. So it seems the problem is with String.fromCharCode specifically.

lysium 16y ago
Just a guess: your anonymous function cannot be redefined (because there is no name), but String.fromCharCode could potentially be. Thus, a similar reason as mentioned in the article for global vs. local variables. One would think that String.fromCharCode is looked up only once, though.
- nene 16y ago
  That's exactly what I was thinking: * In the first version each time the anonymous function is executed interpreter has to lookup String and from it the fromCharCode method => 2n lookups. * In the second version the String and fromCharCode have to be lookud up only once => 2 lookups. Therefore according to slow-lookups-theory the first version should be slower. Except when I measure it, the opposite turns out to be true.
- pornel 16y ago
  Actually it's the opposite. When you pass String.fromCharCode directly, then you're passing reference (not name) to that particular implementation, and it can't change. When you pass anonymous function, then every execution of that function needs to look up `String.fromCharCode` (anonymous functions save scope, not references). I'm surprised by the benchmark as well. I suspect it may be because calls to native functions are handled differently from calls to JS functions, and JS engine is able to optimize call inside anonymous function (create trace/JIT and inline it), but not when calling by reference (and perhaps keeps calling it by some expensive proxy object).

RyanMcGreal 16y ago

Why not just: def f(list): return ''.join([chr(l) for l in list])

Goladus 16y ago
This would be my default approach as well. I'd be interested to see how it compares-- my guess is that it would be equivalent to or slightly faster than f6(), and slower than the version that uses the array library.
- RyanMcGreal 16y ago
  From the article, I'm guessing the author was using a version <2.x. Incidentally, I ran my function and f6 from the article on a list of 9600 integers using Python 2.6.3. f6 ran in 0.00303250832159 seconds and my function ran in 0.00421450212248 seconds.
- petdog 16y ago
  Actually, map is still faster: In [24]: timeit ''.join(map(chr, ll)) 100000 loops, best of 3: 3.91 us per loop In [25]: timeit ''.join([chr(i) for i in ll]) 100000 loops, best of 3: 5.85 us per loop In [26]: timeit ''.join(chr(i) for i in ll) 100000 loops, best of 3: 7.79 us per loop
zephyrfalcon 16y ago
Because it's an old article. Admittedly, there's no easy way to know this, because it has no date, but believe me, it's been around for ages. At the very least, it predates the silly str.join method (and new-style classes and string methods altogether). However, before that, there was the string module, which had the join() function. This article probably relates to it in some way; I think that either it predates string.join (I'm not sure when that was added to Python, but it's been around since at least 1.4), or it clarifies how it was implemented. The author is Guido van Rossum, by the way (another thing that isn't mentioned in the article).
- dish 16y ago

rmc 16y ago

Incidentally, are there any programmes that can scan your python functions and suggest improvements that are in this article? e.g. any programme that'll suggest referencing global names to the local namespace, using map etc.?

danielh 16y ago

It's a whole different story if the input gets longer and the quadratic complexity kicks in. Just change the testdata like this: testdata = range(256)*100 Result: f1 5.539 f2 40.747 f3 5.072 f4 5.311 f5 0.068 f6 3.304 f7 1.431