Early binding as an option

[Steven D'Aprano]

Chris Angelico wrote:

>> In CPython at least, local lookups are faster
>> than globals: locals are stored in a fixed array, and the function knows
>> the numeric offset of each variable.
> 
> Ah! I was not aware of this, and thought that locals were a dictionary
> too. Of course, it makes a lot of sense. In that case, the classic
> "grab it as a local" isn't just loading down the locals dictionary
> with more names and thus slower lookups.

Er, not quite. Hash tables don't get slower as you add more items in them.

The difference is between:

(1) Search for "name" in globals dict;
(2) If not found, search for "name" in builtins dict;

(both searches being O(1) constant time to a first approximation) 

versus:

(1) Look in slot 5 in the function table of local variables


Name lookups involve hashing the string, then jumping to that position in a
hash table, then checking the name equals the key actually found. On
average, that requires constant time regardless of how many keys are in the
hash table (although the hash calculation and the equality tests might
depend on the length of the name). So the whole thing is predictably fast.
But not quite as fast as a simple jump to an offset to a table.

In theory, if you can arrange matters so that the dict is full of keys which
all hash the same, then performance will fall to O(N) instead of O(1), but
that would be *very* hard to do by accident. (A malicious coder might find
a way to fill your globals with a whole lot of three-letter variables that
happen to hash equal to that of "len", but then a malicious coder has
better ways of making your life miserable than slowing down name lookups.)


>> But, are you *sure* that name lookups are *really* the bottleneck? Name
>> lookups are pretty fast. If you want them faster, turn them into a local
>> variable. It's not clear to me that syntax, or a pragma directive, or
>> some other form of magic, is better than an explicit assignment:
> 
> No, I'm not sure. Unfortunately I have no convenient way to compare;

Have you tried using the profiler?


> all I can do is compare with a completely different language, which is
> of course NEVER going to be fair. The only actual data I have on the
> subject is the perfect-numbers search the other day; Pike managed the
> same task in a fraction of the time that Python spent on it. Pike has
> a single integer type that quietly switches from small to large at
> 2**32, with a noticeable performance change. This is the same as
> Python 2, but could explain some of the Python 3 penalty. There's only
> two obvious possibilities (there may be others, of course): firstly,
> that the actual name lookup is expensive; 

I wouldn't imagine that's a big factor, but I could be wrong.

> and secondly, that Pike is 
> able to optimize integer arithmetic by knowing that the value in
> question is an int, and it will never be anything else.

Much more likely.

Or that Pike's programming model is simpler and therefore code is faster, or
it has a smarter compiler... there could be many, many different reasons.

Or you cheated and used a slightly different algorithm in Pike :)


[...]
> So which is the better idiom?
> 
> def func(x):
>    _len = len  # bind at function call time
>    for i in x:
>        _len(i)  # lookups of _len will be faster than len

That's the standard way of doing, er, early binding as late as possible :)

To do early binding as early as possible:

def func(x, len=len):  # binds at function definition time
    for i in x:
        len(i)


> or:
> 
> def func(x):
>    len = len  # localize len
>    for i in x:
>        len(i)  # use it exactly as you otherwise would

That can't work. The problem is that because len is assigned to in the body
of the function, the Python compiler treats it as a local variable. So the
line len=len is interpreted as <local>len = <local>len, which doesn't yet
exist. There's no way of saying <local>len = <global>len in the body of the
function.

So you must either:

(1) use a different name: length = len

(2) use a fully-qualified name: import builtins; len = builtins.len

(3) do the assignment as a default parameter, which has slightly different
binding rules: def func(x, <local>len=<global>len)

(4) manual lookup: len = builtins.__dict__['len']  # untested


I don't recommend that last one, unless you're deliberately trying to write
obfuscated code :)



-- 
Steven