Python Patterns - An Optimization Anecdote
1–10 of 45 posts
Re: Python Patterns - An Optimization Anecdote
#2The 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.
Re: Python Patterns - An Optimization Anecdote
#3I 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.
Re: Python Patterns - An Optimization Anecdote
#4I 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.
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.
Re: Python Patterns - An Optimization Anecdote
#5I 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.
Re: Python Patterns - An Optimization Anecdote
#6The 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…
> 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.
Re: Python Patterns - An Optimization Anecdote
#7I 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.
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 perfo…
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.
Re: Python Patterns - An Optimization Anecdote
#8I 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.
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 perfo…
> 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.
Re: Python Patterns - An Optimization Anecdote
#9I 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.
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 perfo…
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.
Re: Python Patterns - An Optimization Anecdote
#10For 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/