Re: Early binding as an option

Discussion in 'Python' started by Chris Angelico, Aug 2, 2011.

  1. On Tue, Aug 2, 2011 at 9:23 PM, Terry Reedy <> 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
    Chris Angelico, Aug 2, 2011
    #1
    1. Advertising

  2. Chris Angelico wrote:

    > On Tue, Aug 2, 2011 at 9:23 PM, Terry Reedy <> 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
    Steven D'Aprano, Aug 3, 2011
    #2
    1. Advertising

  3. On Wed, Aug 3, 2011 at 11:16 AM, Steven D'Aprano
    <> 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
    Chris Angelico, Aug 3, 2011
    #3
  4. 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
    Steven D'Aprano, Aug 3, 2011
    #4
  5. Chris Angelico <> 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.
    Alain Ketterlin, Aug 3, 2011
    #5
  6. On Wed, Aug 3, 2011 at 8:51 PM, Steven D'Aprano
    <> 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
    Chris Angelico, Aug 3, 2011
    #6
  7. Chris Angelico

    Chris Torek Guest

    >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$>
    Steven D'Aprano <> 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 (40°39.22'N, 111°50.29'W) +1 801 277 2603
    email: gmail (figure it out) http://web.torek.net/torek/index.html
    Chris Torek, Aug 4, 2011
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Shawn
    Replies:
    0
    Views:
    447
    Shawn
    Dec 8, 2003
  2. Max
    Replies:
    1
    Views:
    419
    Natty Gur
    Jan 4, 2004
  3. =?Utf-8?B?UGxhdA==?=
    Replies:
    5
    Views:
    1,899
    =?Utf-8?B?UGxhdA==?=
    Mar 16, 2005
  4. Replies:
    2
    Views:
    853
    Kevin Grover
    Oct 20, 2006
  5. Chris Angelico

    Early binding as an option

    Chris Angelico, Aug 2, 2011, in forum: Python
    Replies:
    1
    Views:
    165
    Alain Ketterlin
    Aug 2, 2011
Loading...

Share This Page