[Tutor] A fun puzzle

[Kent Johnson]

Dick Moores wrote:
>> Two reasons. First, looking up a name that is local to a function is 
>> faster than looking up a global name. To find the value of 'str', 
>> the interpreter has to look at the module namespace, then the 
>> built-in namespace. These are each dictionary lookups. Local values 
>> are stored in an array and accessed by offset so it is much faster.
> 
> Wow, what DON'T you understand?

Lots, actually :-) There is a whole 'nother tier or two of Python expert 
above me that I can't touch. I just parrot back what I hear them saying. :-)

> Please explain "accessed by offset".

IIUC an array is allocated on the call stack to hold references to the 
local variables. (Anticipating you next question: 
http://en.wikipedia.org/wiki/Stack_frame) To get the value of the local 
variable the runtime just has to look up the correct entry in the array. 
The bytecode has the offset into the array. This is very quick - an 
indexed lookup.

Normal attribute access such as a module or builtin has to read the 
value out of a dict which is much more expensive, even with Python's 
optimized dicts.

> This time I added "xrange(10, end, 10)" and did the timing using the 
> template in the timeit module:
> 
> template = """
> def inner(_it, _timer):
>      _t0 = _timer()
>      from itertools import chain
>      end = 1000000
>      for _i in _it:
>          for x in chain(xrange(1, end, 10), xrange(2, end, 10),
>          xrange(3, end, 10), xrange(4, end, 10), xrange(5, end, 10),
>          xrange(6, end, 10), xrange(7, end, 10), xrange(8, end, 10),
>          xrange(9, end, 10), xrange(10, end, 10)):
>              pass
>      _t1 = _timer()
>      return _t1 - _t0
> """
> This gets always close to 71 msec per loop.
> 
> 
> template = """
> def inner(_it, _timer):
>      _t0 = _timer()
>      end = 1000000
>      for _i in _it:
>          for x in xrange(end):
>              pass
>      _t1 = _timer()
>      return _t1 - _t0
> """
> This gets always close to 84 msec per loop.
> 
> So they're not the same! And yours is the faster one! Because 
> itertools.chain() is written in C, I suppose.

That is very strange. I did a simple timer with time.time() and found 
that my original (1-9) version was consistently a little slower than the 
simple xrange(). And xrange is written in C too, and the chain version 
adds a layer over xrange. You should check your code carefully, that is 
a very surprising result.

> I just did a search on "itertools" in the comp.lang.python group at 
> Google Groups, and got 1,940 hits. <http://tinyurl.com/3a2abz>. That 
> should keep me busy!

Have fun!
Kent