Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Re: Early binding as an option

Reply
Thread Tools

Re: Early binding as an option

 
 
Chris Angelico
Guest
Posts: n/a
 
      08-02-2011
On Tue, Aug 2, 2011 at 9:23 PM, Terry Reedy <(E-Mail Removed)> wrote:
> On 8/2/2011 12:55 PM, Chris Angelico wrote:
>>
>> As I understand it, Python exclusively late-binds names; when you
>> define a function, nothing is ever pre-bound.

>
> By 'pre-bound' you presumably mean bound at definition time rather than call
> time. Default arg objects *are* pre-computed and pre-bound to internal slots
> at definition time.


Of course; that's a different issue altogether. No, I'm talking about
the way a tight loop will involve repeated lookups for the same name.

Unfortunately, there is no way - by definition - to guarantee that a
binding won't change. Even in the example of getting the lengths of
lines in a file, it's entirely possible for __len__ to rebind the
global name "len" - so you can't rely on the repeated callings of
len() to be calling the same function.

But who WOULD do that? It's somewhat ridiculous to consider, and
there's a huge amount of code out there that does these repeated calls
and does not do stupid rebindings in the middle. So Python permits
crazy behaviour at the cost of the performance of normal behaviour.

With the local-variable-snapshot technique ("len = len"), can anything
be optimized, since the parser can guarantee that nothing ever
reassigns to it? If not, perhaps this would be a place where something
might be implemented:

@const(len,max) # maybe this
def maxline(f):
@const len,max # or this
n = 0
for line in somefile:
n = max(n,len(line))
return n

Some notation like this could tell the interpreter, "I don't expect
'len' or 'max' to be rebound during the execution of this function.
You're free to produce wrong results if either is."

So... Would this potentially produce wrong results? Would it be of any
use, or would its benefit be only valued in times when the whole
function needs to be redone in C?

Chris Angelico
 
Reply With Quote
 
 
 
 
Steven D'Aprano
Guest
Posts: n/a
 
      08-03-2011
Chris Angelico wrote:

> On Tue, Aug 2, 2011 at 9:23 PM, Terry Reedy <(E-Mail Removed)> wrote:
>> On 8/2/2011 12:55 PM, Chris Angelico wrote:
>>>
>>> As I understand it, Python exclusively late-binds names; when you
>>> define a function, nothing is ever pre-bound.

>>
>> By 'pre-bound' you presumably mean bound at definition time rather than
>> call time. Default arg objects *are* pre-computed and pre-bound to
>> internal slots at definition time.

>
> Of course; that's a different issue altogether. No, I'm talking about
> the way a tight loop will involve repeated lookups for the same name.


It's not really a different issue. The "standard" approach for performing
early binding in Python is by binding a global name to a local name at
function definition time. 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. Non-locals have to search multiple
namespaces (globals + built-ins), using a hash table. That's fast, but
locals are faster.

(Aside: this is why locals() is not generally writable: the dict is a copy
of that internal array. You can write to the dict, but the changes don't
propagate back to the actual local table of the function.)

So a good way to speed up name lookups is to turn a global into a local, and
one common way to do that is to do it when the function is defined. For
example, you will see this in the random module:

def randrange(self, start, stop=None, step=1, int=int, default=None,
maxwidth=1<<BPF):
"""Choose a random item from range(start, stop[, step]).

This fixes the problem with randint() which includes the
endpoint; in Python this is usually not what you want.
Do not supply the 'int', 'default', and 'maxwidth' arguments.
"""


Note the int=int parameter.


> Unfortunately, there is no way - by definition - to guarantee that a
> binding won't change. Even in the example of getting the lengths of
> lines in a file, it's entirely possible for __len__ to rebind the
> global name "len" - so you can't rely on the repeated callings of
> len() to be calling the same function.
>
> But who WOULD do that? It's somewhat ridiculous to consider, and
> there's a huge amount of code out there that does these repeated calls
> and does not do stupid rebindings in the middle. So Python permits
> crazy behaviour at the cost of the performance of normal behaviour.


This is a common criticism of Python, and the truth be told, it is right:
Python makes crazy monkey-patching that we're told not to do easy, at the
expense of allowing the compiler to optimise really common things.

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:

def func(x):
_len = len # bind at function call time
for i in x:
_len(i) # lookups of _len will be faster than len


The argument that Python would be faster if it did early binding is not a
given. For trivial code that doesn't do much, I dare say it might shave off
a significant percentage, but trivial code is already pretty fast. Who
cares if you speed up a trivial operation? In non-trivial code that does
real work, it's not obvious that early binding will result in meaningful
time savings. ("Yay, my code now runs in 17.1 milliseconds instead of
17.2!") The onus is on the person proposing this change to prove that the
benefit is worth the extra complexity.

Knowing what we know now, I'm not sure whether Guido would have kept the
late binding semantics for Python, or privileged builtins in some fashion.
I suspect that he wouldn't have changed a thing, but if he did, I suspect
he'd be more concerned about accidental shadowing of builtins than about
optimizations.

E.g. people say list = [1,2,3], and then later try to call list(something).

Or maybe that's just me

Guido is generally very, very suspicious about proposed optimisations. They
tend to increase the code's complexity by far more than they increase its
speed. (E.g. an order of magnitude more complex to get 10% speed increase.)
And they often subtly break the semantics of the code. E.g. if you do
floating point maths, optimizing compilers that assume that x + y - x
equals y are BROKEN.


> With the local-variable-snapshot technique ("len = len"), can anything
> be optimized, since the parser can guarantee that nothing ever
> reassigns to it?


Very likely. But the optimization happens at runtime, not at compile time.

Default values for parameters are stored as an attribute of the function at
definition time. So if you have this:

def f(x, len=len):
return len(x)

then f gets a publicly accessible attribute func_defaults:

>>> f.func_defaults

(<built-in function len>,)

Even if you re-bind len, that doesn't change the binding here, and the
*local* variable len will be assigned that value when f is called. Here's a
practical example:


>>> def test(len=len):

.... while True:
.... yield len
....
>>>
>>> it = test()
>>> next(it)

<built-in function len>
>>> len = None # rebind the global len
>>> next(it)

<built-in function len>
>>> test.func_defaults = (None, )
>>> next(it)

<built-in function len>

But note that now as I've replaced the default value, the next time I call
test() I'll get len=None.


[...]
> So... Would this potentially produce wrong results? Would it be of any
> use, or would its benefit be only valued in times when the whole
> function needs to be redone in C?


You really would need to demonstrate that the bottleneck in useful code (as
opposed to toy examples) was the name lookups.



--
Steven

 
Reply With Quote
 
 
 
 
Chris Angelico
Guest
Posts: n/a
 
      08-03-2011
On Wed, Aug 3, 2011 at 11:16 AM, Steven D'Aprano
<(E-Mail Removed)> wrote:
> Chris Angelico wrote:
>> Of course; that's a different issue altogether. No, I'm talking about
>> the way a tight loop will involve repeated lookups for the same name.

>
> It's not really a different issue. The "standard" approach for performing
> early binding in Python is by binding a global name to a local name at
> function definition time.


Thanks for the detailed response!

My concept was that this wouldn't affect the dynamism significantly,
and that if the function's caller wanted to change the definition of
'len', s/he could still do so; the "snapshotting" would occur as the
function begins executing. This would make things rather safer, as
there's a limited window during which this could affect things.

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

> * * * *Do not supply the 'int', 'default', and 'maxwidth' arguments.
> * * * *"""


I love the way Python doesn't stop you from doing stupid things. This
is an invitation to do something... hmm.
>>> random.randrange(5,10,1,int=lambda x: (print(x),int(x))[1])


> 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;
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; 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. Since I was
under the impression that local variables were stored in a hash table,
I concluded that the first option was reasonably likely, and tried to
get more data.

>> So... Would this potentially produce wrong results? Would it be of any
>> use, or would its benefit be only valued in times when the whole
>> function needs to be redone in C?

>
> You really would need to demonstrate that the bottleneck in useful code (as
> opposed to toy examples) was the name lookups.


And especially, prove that the same can't be done with local variables.

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

or:

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

In other words, is it "Explicit is better than implicit" or "Simple is
better than complex"? Since this does absolutely exactly the same
thing as the original, I'd be inclined to go with the second form; a
single line at the top of the function, with an explanatory comment
perhaps, and the rest of the code is unaware of the optimization. But
this has the potential to be insanely confusing if anything goes
wrong, because down in the body of the function there's no clue that
anything was changed.

Unfortunately I can't offer any real-world use cases or examples. This
is purely a thought experiment at the moment.

Chris Angelico
 
Reply With Quote
 
Steven D'Aprano
Guest
Posts: n/a
 
      08-03-2011
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

 
Reply With Quote
 
Alain Ketterlin
Guest
Posts: n/a
 
      08-03-2011
Chris Angelico <(E-Mail Removed)> writes:

[...]
> 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; 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.


Pike is (at least partly) statically typed. Most of the lookups are
solved at compile time, and have therefore zero overhead at run-time. So
your second possibility is the good one, but probably not because of
arithmetic optims, rather because of all the lookups Pike doesn't
perform dynamically.

-- Alain.
 
Reply With Quote
 
Chris Angelico
Guest
Posts: n/a
 
      08-03-2011
On Wed, Aug 3, 2011 at 8:51 PM, Steven D'Aprano
<(E-Mail Removed)> wrote:
> Chris Angelico wrote:
>
>> 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..


Whoops, sloppy English there. The locals dictionary isn't slower
because it gets more stuffed in it (well, maybe a dict will slow down
if you stuff a few million things in it vs having five, but not with
this scale), but that it's slower than alternatives.

>> No, I'm not sure. Unfortunately I have no convenient way to compare;

>
> Have you tried using the profiler?


I can profile the code the way it is. I can't profile the code the way
it isn't, with static lookups. I could compare global vs local, but
not global/local vs no lookup at all.

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


Pike separates variables from their values, just as Python does. I've
actually stuffed strings into variables that are supposed to be int
only, and things work fine (a bit confusing for the human though!).
But you're right that it's probably simplifying other lookups, not the
actual variable name. I think the same consideration applies; if you
know exactly what you're working with, if you assume that x.__add__ is
not going to change, then you can optimize.

> Or you cheated and used a slightly different algorithm in Pike


Heh. No, I kept the algorithm exactly the same. I'll post the code if
you like

>> 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'tyet
> exist. There's no way of saying <local>len = <global>len in the body ofthe
> function.


Duh. Forgot that. Without convenient syntax like "len = ::len" to do
this, it's not advisable.

> (4) manual lookup: len = builtins.__dict__['len'] *# untested
>
> I don't recommend that last one, unless you're deliberately trying to write
> obfuscated code


For that reason! Although using builtins in this way isn't a good idea
- there's no reason to do early binding late if you just bind to the
same thing that early binding early would have done. And
globals()["len"] doesn't work either, because builtins aren't
globals... blargh, there's really no simple way to do this. It's a
good thing I don't *need* to do anything like this, because it's not
the syntactically simple optimization that I thought it would be!

ChrisA
 
Reply With Quote
 
Chris Torek
Guest
Posts: n/a
 
      08-04-2011
>Chris Angelico wrote:
[snippage]
>> def func(x):
>> len = len # localize len
>> for i in x:
>> len(i) # use it exactly as you otherwise would


In article <4e39a6b5$0$29973$c3e8da3$(E-Mail Removed) om>
Steven D'Aprano <(E-Mail Removed)> wrote:
>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


(This is my preferred form, given what one has now, if one is going
to do this in the function body. Of course in 2.x it is spelled
__builtin__.len instead...)

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


If Python *were* to have some kind of "tie this symbol down now"
operation / keyword / whatever, one could write:

def func(x):
snap len # here the new keyword is "snap"
for i in x:
... len(i) ... # use it exactly as you otherwise would

Of course there is no *need* for any new syntax with the other
construction:

def func(x, len=len) # snapshots "len" at def() time
for i in x:
... len(i) ...

but if one were to add it, it might look like:

def func(x, snap len):

The advantage (?) of something like a snap or snapshot or whatever
keyword / magic-function / whatever is that you can apply it to
more than just function names, e.g.:

def func(arg):
# for this example, assume that arg needs to have the
# following attributes:
snap arg.kloniblatt, arg.frinkle, arg.tippy
...

Here, in the "..." section, a compiler (whether byte-code, or JIT,
or whatever -- JIT makes the most sense in this case) could grab
the attributes, looking up their types and any associated stuff it
wants to, and then assume that for the rest of that function's
execution, those are not allowed to change. (But other arg.whatever
items are, here. If you want to bind *everything*, perhaps "snap
arg" or "snap arg.*" -- see below.)

Even a traditional (CPython) byte-code compiler could do something
sort of clever here, by making those attributes "read-only" to
whatever extent the snapshot operation is defined as fixing the
binding (e.g., does it recurse into sub-attributes? does it bind
only the name-and-type, or does it bind name-and-type-and-value,
or name-and-type-and-function-address-if-function, or ... -- all
of which has to be pinned down before any such suggestion is taken
too seriously ).
--
In-Real-Life: Chris Torek, Wind River Systems
Intel require I note that my opinions are not those of WRS or Intel
Salt Lake City, UT, USA (4039.22'N, 11150.29'W) +1 801 277 2603
email: gmail (figure it out) http://web.torek.net/torek/index.html
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Early binding as an option Chris Angelico Python 1 08-02-2011 07:02 PM
pywin32 COM sort in Excel (late binding fails, early binding works) (+py2exe) kogrover@gmail.com Python 2 10-20-2006 04:08 PM
COM Objects, Early Binding, and Server-Side ASPX Compilation =?Utf-8?B?UGxhdA==?= ASP .Net 5 03-16-2005 04:27 PM
dynamically change table with early binding? Max ASP .Net 1 01-04-2004 07:49 AM
how to do early-binding on repeater Shawn ASP .Net 0 12-08-2003 02:19 PM



Advertisments