Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Python Patterns - An Optimization Anecdote

python.org

Post reply on HN
Print view View original

11–20 of 45 posts

Re: Python Patterns - An Optimization Anecdote

#11

Post by lysium »

derefr wrote: post #8
edanm wrote: post #4

Earlier quoted context omitted.

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.

Generally, you cannot scan the loop body to find redefinitions of `chr`. This is known as the halting problem.

Consider, for example, a redefinition of `chr` in an `if`-clause: you would have to actually run the program to know if the `if`-clause is taken or not.

Further, in Python, the redefinition of `chr` does not even have to be in the form of `chr = ...`, but could be an assignment into a global hash, maybe even using a variable as an index.

Re: Python Patterns - An Optimization Anecdote

#12

Post by StavrosK »

rix0r wrote: post #2

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…

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.

Re: Python Patterns - An Optimization Anecdote

#13

Post by [deleted] »

derefr wrote: post #8
edanm wrote: post #4

Earlier quoted context omitted.

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.

[deleted]

Re: Python Patterns - An Optimization Anecdote

#14

Post by derefr »

lysium wrote: post #11
derefr wrote: post #8

Earlier quoted context omitted.

> 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.

Generally, you cannot scan the loop body to find redefinitions of `chr`. This is known as the halting problem. Consider, for example, a redefinition of `chr` in an `if`-clause: you would have to actually run the program to know if the `if`-clause is taken or not. Further, in Python, the redefinition of `chr` does not even have to be in the form of `chr = ...`, but could be an assignment into a global hash, maybe even…

I'm not suggesting that you have to know specifically that chr is being redefined; to cancel the optimization, you simply have to know that "this loop body is not limited to the subset of operations which are known to not redefine chr" (i.e. basically the same sort of analysis Google NaCl does.) This leaves a large number of optimizations on the table (i.e. any loop body that modifies a global hash will cancel the optimization), but is better than no optimization at all.

Re: Python Patterns - An Optimization Anecdote

#15

Post by [deleted] »

lysium wrote: post #11
derefr wrote: post #8

Earlier quoted context omitted.

> 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.

Generally, you cannot scan the loop body to find redefinitions of `chr`. This is known as the halting problem. Consider, for example, a redefinition of `chr` in an `if`-clause: you would have to actually run the program to know if the `if`-clause is taken or not. Further, in Python, the redefinition of `chr` does not even have to be in the form of `chr = ...`, but could be an assignment into a global hash, maybe even…

[deleted]

Re: Python Patterns - An Optimization Anecdote

#16

Post by nene »

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.

Re: Python Patterns - An Optimization Anecdote

#17

Post by lysium »

derefr wrote: post #14
lysium wrote: post #11

Earlier quoted context omitted.

Generally, you cannot scan the loop body to find redefinitions of `chr`. This is known as the halting problem. Consider, for example, a redefinition of `chr` in an `if`-clause: you would have to actually run the program to know if the `if`-clause is taken or not. Further, in Python, the redefinition of `chr` does not even have to be in the form of `chr = ...`, but could be an assignment into a global hash, maybe even…

I'm not suggesting that you have to know specifically that chr is being redefined; to cancel the optimization, you simply have to know that "this loop body is not limited to the subset of operations which are known to not redefine chr" (i.e. basically the same sort of analysis Google NaCl does.) This leaves a large number of optimizations on the table (i.e. any loop body that modifies a global hash will cancel the op…

I wonder how large (or small) that restricted subset is and how easily it is 'violated', turning off the optimization although it would have been possible (For example, the global hash could be referred to via a local variable which might carry the result of a function call). Do you have any insights on that?

Until then, using a 'dirty flag' on the `chr` definition that turns off the optimization at run time as mentioned elsewhere in this thread, seems to be the appropriate approach for me.

Re: Python Patterns - An Optimization Anecdote

#18

Post by lysium »

nene wrote: post #16

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 previ…

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.

Re: Python Patterns - An Optimization Anecdote

#19

Post by nene »

lysium wrote: post #18
nene wrote: post #16

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 previ…

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.

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.

Re: Python Patterns - An Optimization Anecdote

#20

Post by dish »

nene wrote: post #16

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 previ…

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

return ''.join(map(chr, list))

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

Post reply on HN