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.

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.

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

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

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

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.

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.

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.

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.

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

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.