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

31–40 of 45 posts

Re: Python Patterns - An Optimization Anecdote

#31

Post by pornel »

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.

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

Re: Python Patterns - An Optimization Anecdote

#32

Post by edanm »

devinj wrote: post #29
edanm wrote: post #5

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

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…

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.

Re: Python Patterns - An Optimization Anecdote

#33

Post by edanm »

riffraff wrote: post #7
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 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 optimi…

Interesting. What are the best sources for learning what kind of optimizations are actually implemented in practice in Python?

Re: Python Patterns - An Optimization Anecdote

#34

Post by edanm »

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…

Good points.

What about multi-threading? Isn't it possible that another thread entirely reassigns "chr" to something different, while the for loop is running?

Obviously this would only happen in a pathological program written purely for perpetrating evil on unsuspecting programmers :) But seriously, it's possible, and it's the kind of thing optimizing compilers have to take into consideration.

Re: Python Patterns - An Optimization Anecdote

#35

Post by Nitramp »

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…

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?

Re: Python Patterns - An Optimization Anecdote

#36

Post by deathflute »

edanm wrote: post #32
devinj wrote: post #29

Earlier quoted context omitted.

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…

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

In my experience edanm is correct. map/reduce/filter are faster with built-in functions, but list comprehensions are faster with user-defined ones

For eg. using python 2.5.2

In [9]: l = ['10'] * 5000000

In [10]: timeit -n5 map(int, l)

5 loops, best of 3: 1.29 s per loop

In [11]: timeit -n5 [int(i) for i in l]

5 loops, best of 3: 1.64 s per loop

Re: Python Patterns - An Optimization Anecdote

#37

Post by nene »

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…

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.

Re: Python Patterns - An Optimization Anecdote

#38

Post by froydnj »

jpr wrote: post #26
zephyrfalcon wrote: post #25

Earlier quoted context omitted.

The latter; otherwise it wouldn't be dynamic. :-) I don't know the details, but I assume that some of the Python compiler projects do make assumptions like this, i.e. they can compile to faster code if you don't shadow or outright overwrite builtins, etc.

I still don't see why the variable names can't be interned somehow by the parser. This would mean that a global variable would be just a pointer in to the table, and "lookup" would be just dereferencing that pointer. AFAICT, this is how symbols and packages work in Common Lisp.

You are correct (you do have to check that the symbol is actually bound prior to dereferencing). But they don't (generally) work that way for symbols with a function binding. I think the rationale here is that it's much more common to have BOUNDP symbols than FBOUNDP symbols. So sticking an extra slot for the value in a symbol is worth it, space-wise, whereas an extra slot for the function is not, so function lookups go through some sort of global table.

Note too that Common Lisp forbids you from modifying the function binding of symbols in the COMMON-LISP package for precisely this reason: the compiler can do a better job reasoning about the effects of calls to those functions.

Re: Python Patterns - An Optimization Anecdote

#39

Post by rmc »

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

Re: Python Patterns - An Optimization Anecdote

#40

Post by devinj »

deathflute wrote: post #36
edanm wrote: post #32

Earlier quoted context omitted.

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

In my experience edanm is correct. map/reduce/filter are faster with built-in functions, but list comprehensions are faster with user-defined ones For eg. using python 2.5.2 In [9]: l = ['10'] * 5000000 In [10]: timeit -n5 map(int, l) 5 loops, best of 3: 1.29 s per loop In [11]: timeit -n5 [int(i) for i in l] 5 loops, best of 3: 1.64 s per loop

You mean "incorrect". Also, I did post detailed timing results above.
Post reply on HN