Python Patterns - An Optimization Anecdote

http://www.python.org/doc/essays/list2str.html

by niyazpk • 16 years ago

74 42 16 years ago

rix0r• 16 years 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• 16 years 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• 16 years 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• 16 years 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• 16 years 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.

edanm5• 16 years 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.

riffraff2• 16 years 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.

derefr2• 16 years 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.

vilya• 16 years ago

This is the sort of thing that trace-based optimisation can help with. It's able to observe that the value bound to chr doesn't change between invocations and inline the lookup accordingly. I believe Mark Shannon's HotPy runtime (http://www.dcs.gla.ac.uk/~marks/) attempts to do this.

jpr2• 16 years ago

> Calling a function like "chr", which is looked up dynamically

Shouldn't that be just one or two pointer-dereferences? Or is Python putting globals in hash-table and looking them up each and every time?

edanm5• 16 years 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.

devinj2• 16 years ago

Point 3 is weakened by the fact that map can indeed be faster. 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 . The story is a bit different on 3.x, where list comps are implemented very differently: http://ideone.com/58FGZ

edanm5• 16 years 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.

codefisher• 16 years 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/

nene3• 16 years 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.

lysium3• 16 years 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.

nene3• 16 years 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• 16 years 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).

dish3• 16 years ago

That kind of should be the first train of thought in python too, why using "+" to add strings!? it maybe fixed in py3k but its still not worth it in py2.X

<pre> return ''.join(map(chr, list)) </pre>

Also the liberal use of the words list and string bothers me.

dish3• 16 years ago

Since Guido invented the words "list" and "string" in python at least, I guess him using them doesn't bother me.

nene3• 16 years ago

Found an answer.

The problem is that String.fromCharCode takes multiple arguments and Array.map also passes multiple arguments to the callback, therefore the equivalent of numbers.map(String.fromCharCode) is actually:

    numbers.map(function(x, y, z){return String.fromCharCode(x, y, z);})

Which of course is slower as the end result will actually be array with longer strings in it.

RyanMcGreal2• 16 years ago

Why not just:

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

Goladus• 16 years 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.

RyanMcGreal2• 16 years 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• 16 years 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

zephyrfalcon2• 16 years 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).

dish3• 16 years ago

WTF, Guido wrote that!? I will jump out of a window now.

teoruiz• 16 years ago

It is actually slower. Adding an f8 function using the ''.join() method:

  sikanda-13:30:02:/tmp$ python f.py 
  [...]
  f1 0.07
  f2 0.12
  f3 0.07
  f4 0.06
  f5 0.09
  f6 0.04
  f7 0.02
  f8 0.07

Original code linked in the article: http://www.python.org/doc/essays/f.py

scott_s• 16 years ago

My results agree with yours, in terms of who wins. Python 2.6 (2.4 is similar, and 3.0 is as well, for the techniques that were still valid) on OSX 10.5, Intel Core Duo at 2 GHz:

  [scotts@silver]$ /opt/local/bin/python2.6 f.py
  f1 0.107
  f2 0.19
  f3 0.106
  f4 0.097
  f5 0.139
  f6 0.073
  f7 0.025
  f8 0.103

edit: I added a ninth function,

  def f9(list):
    return ''.join(map(chr, list))

To test if the difference between f8 and f6 was the list comprehension or the joinfields method. A result of 0.072 tells me it's the list comprehension. The only difference between f8 and f9 is list comprehension versus map. That leads me to conclude that map is indeed a faster way to construct a list than a list comprehension. (Although this may change for a user-defined function. I could test this, but I've spent enough time already.)

rmc• 16 years 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• 16 years 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:

Python Patterns - An Optimization Anecdote

Related Stories