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