Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #90713

Re: Building CPython

Show key headers only | View raw

On 16/05/2015 02:55, Steven D'Aprano wrote:
> On Sat, 16 May 2015 09:27 am, Mark Lawrence wrote:
>
>> On 15/05/2015 23:44, Marko Rauhamaa wrote:
>>> BartC <bc@freeuk.com>:
>>>
>>>> What /is/ a method lookup? Is it when you have this:
>>>>
>>>>    A.B()
>>>>
>>>> and need to find whether the expression A (or its class or type) has a
>>>> name B associated with it? (And it then needs to check whether B is
>>>> something that can be called.)
>>>>
>>>> If so, does that have to be done using Python's Dict mechanism? (Ie.
>>>> searching for a key 'B' by name and seeing if the object associated
>>>> with it is a method. That does not sound efficient.)
>
> It's not as inefficient as you may think. Dicts are hash tables, and hash
> tables are a standard computer science data structure for performing very
> fast searches at constant (or near constant) time.
>
> The dict is basically an array of pointers to (key, value). To look a name
> up in the dict, you hash the string which gives you an index into the
> array, then look at that position. If it is blank, you know there is no
> match. If it points to a string, you compare that string to your string. If
> they are equal, then you have a match. If they aren't equal, you have a
> collision, and you have to look elsewhere (details differ) but typically
> you don't end up looking in more than one or two positions. So all pretty
> fast, and close enough to constant time.
>
> To speed things up even further, I think that the hash value is cached with
> the string, so it only needs to be calculated the first time.
>
>
>
>>> That is a general feature among high-level programming languages. In
>>> Python, it is even more complicated:
>>>
>>>    * first the object's dict is looked up for the method name
>>>
>>>    * if the method is not found (it usually isn't), the dict of the
>>>      object's class is consulted
>>>
>>>    * if the method is found (it usually is), a function object is
>>>      instantiated that delegates to the class's method and embeds a "self"
>>>      reference to the object to the call
>
> It's the other way around. The function object already exists: you created
> it by writing `def method(self, *args): ... ` inside the class body. def
> always makes a function. It's the *method* object which is created on the
> fly, delegating to the function.
>
>
>
>>> IOW, two dict lookups plus an object construction for each method call.
>>>
>>>
>>> Marko
>>>
>>
>> As a picture paints a thousand words is anybody aware of a site or sites
>> that show this diagramatically, as I think I and possibly others would
>> find it far easier to grasp.
>
> No I'm not aware of any such site, but I can try to make it more obvious
> with an example.
>
> Suppose we have a hierarchy of classes, starting from the root of the
> hierarchy (object) to a specific instance:
>
> class Animal(object):
>      pass
>
> class Mammal(Animal):
>      pass
>
> class Dog(Mammal):
>      def bark(self): ...
>
> laddy = Dog()
>
>
> We then look up a method:
>
> laddy.bark()
>
> In a non-dynamic language like Java, the compiler knows exactly where bark
> is defined ("in the Dog class") and can call it directly. In dynamic
> languages like Python, the compiler can't be sure that bark hasn't been
> shadowed or overridden at runtime, so it has to search for the first match
> found. Simplified:
>
> * Does laddy.__dict__ contain the key "bark"? If so, we have a match.
>
> * For each class in the MRO (Method Resolution Order), namely
>    [Dog, Mammal, Animal, object], does the class __dict__ contain the
>    key "bark"? If so, we have a match.
>
> * Do any of those classes in the MRO have a __getattr__ method? If
>    so, then try calling __getattr__("bark") and see if it returns
>    a match.
>
> * Give up and raise AttributeError.
>
> [Aside: some of the things I haven't covered: __slots__, __getattribute__,
> how metaclasses can affect this.]
>
> In the case of laddy.bark, the matching attribute is found as
> Dog.__dict__['bark']:
>
>      temp = Dog.__bark__['bark']  # laddy.bark, is a function
>
> At this point, the descriptor protocol applies. You can ignore this part if
> you like, and just pretend that laddy.bark returns a method instead of a
> function, but if you want to know what actually happens in all it's gory
> details, it is something like this (again, simplified):
>
> * Does the attribute have a __get__ method? If not, then we just
>    use the object as-is, with no changes.
>
> * But if it does have a __get__ method, then it is a descriptor and
>    we call the __get__ method to get the object we actually use.
>
>
> Since functions are descriptors, we get this:
>
>      temp = temp.__get__(laddy, Dog)  # returns a method object
>
> and finally we can call the method:
>
>      temp()  # laddy.bark()
>
>
> None of these individual operations are particularly expensive, nor are
> there a lot of them. For a typical instance, the MRO usually contains only
> two or three classes, and __dict__ lookups are fast. Nevertheless, even
> though each method lookup is individually *almost* as fast as the sort of
> pre-compiled all-but-instantaneous access which Java can do, it all adds
> up. So in Java, a long chain of dots:
>
>      foo.bar.baz.foobar.spam.eggs.cheese
>
> can be resolved at compile-time, and takes no more time than
>
>      foo.cheese
>
> but in Python's case it has to be resolved at run-time, so if you care about
> speed, you should try to avoid long chains of dots in performance critical
> loops. E.g. instead of:
>
>      for x in sequence:
>          foo.bar.baz.foobar.spam.eggs.cheese(x)
>
> you can write:
>
>      cheese = foo.bar.baz.foobar.spam.eggs.cheese
>      for x in sequence:
>          cheese(x)
>

Thanks for taking the time over this, I'll study it later today after 
hopefully a good night's sleep :)

-- 
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Building CPython BartC <bc@freeuk.com> - 2015-05-13 20:36 +0100
  Re: Building CPython Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-05-13 20:58 +0100
  Re: Building CPython Terry Reedy <tjreedy@udel.edu> - 2015-05-13 18:34 -0400
    Re: Building CPython BartC <bc@freeuk.com> - 2015-05-14 16:51 +0100
      Re: Building CPython Chris Angelico <rosuav@gmail.com> - 2015-05-15 02:09 +1000
        Re: Building CPython BartC <bc@freeuk.com> - 2015-05-14 18:02 +0100
          Re: Building CPython Dave Angel <davea@davea.name> - 2015-05-14 13:10 -0400
          Re: Building CPython Chris Angelico <rosuav@gmail.com> - 2015-05-15 03:11 +1000
            Re: Building CPython BartC <bc@freeuk.com> - 2015-05-14 18:32 +0100
              Re: Building CPython Chris Angelico <rosuav@gmail.com> - 2015-05-15 03:45 +1000
          Re: Building CPython Terry Reedy <tjreedy@udel.edu> - 2015-05-14 14:50 -0400
            Re: Building CPython Christian Gollwitzer <auriocus@gmx.de> - 2015-05-15 12:51 +0200
              Re: Building CPython Terry Reedy <tjreedy@udel.edu> - 2015-05-15 17:19 -0400
      Re: Building CPython Marko Rauhamaa <marko@pacujo.net> - 2015-05-14 19:29 +0300
        Re: Building CPython BartC <bc@freeuk.com> - 2015-05-14 22:55 +0100
          Re: Building CPython MRAB <python@mrabarnett.plus.com> - 2015-05-14 23:19 +0100
          Re: Building CPython BartC <bc@freeuk.com> - 2015-05-15 01:50 +0100
            Re: Building CPython Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-05-15 18:05 +1200
              Re: Building CPython Marko Rauhamaa <marko@pacujo.net> - 2015-05-15 11:59 +0300
                Re: Building CPython wxjmfauth@gmail.com - 2015-05-15 02:07 -0700
                Re: Building CPython Marko Rauhamaa <marko@pacujo.net> - 2015-05-15 12:20 +0300
                Re: Building CPython wxjmfauth@gmail.com - 2015-05-15 02:51 -0700
                Re: Building CPython Marko Rauhamaa <marko@pacujo.net> - 2015-05-15 13:52 +0300
                Re: Building CPython Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-15 22:10 +1000
                Re: Building CPython Chris Angelico <rosuav@gmail.com> - 2015-05-15 22:34 +1000
                Re: Building CPython wxjmfauth@gmail.com - 2015-05-15 07:11 -0700
                Re: Building CPython Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-05-15 13:41 +0100
                Re: Building CPython Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-05-15 13:38 +0100
                Re: Building CPython Chris Angelico <rosuav@gmail.com> - 2015-05-15 19:43 +1000
                Re: Building CPython Marko Rauhamaa <marko@pacujo.net> - 2015-05-15 13:50 +0300
                Re: Building CPython Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-15 22:43 +1000
                Re: Building CPython Ian Kelly <ian.g.kelly@gmail.com> - 2015-05-15 09:00 -0600
                Re: Building CPython Ian Kelly <ian.g.kelly@gmail.com> - 2015-05-15 09:04 -0600
                Re: Building CPython Chris Angelico <rosuav@gmail.com> - 2015-05-16 01:06 +1000
                Re: Building CPython Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-15 20:14 +1000
                Re: Building CPython Chris Angelico <rosuav@gmail.com> - 2015-05-15 20:25 +1000
                Re: Building CPython Terry Reedy <tjreedy@udel.edu> - 2015-05-15 17:05 -0400
                Re: Building CPython BartC <bc@freeuk.com> - 2015-05-15 22:54 +0100
                Re: Building CPython Marko Rauhamaa <marko@pacujo.net> - 2015-05-16 01:44 +0300
                Re: Building CPython Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-05-16 00:27 +0100
                Re: Building CPython Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-16 11:55 +1000
                Re: Building CPython Chris Angelico <rosuav@gmail.com> - 2015-05-16 12:15 +1000
                Re: Building CPython Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-05-16 03:17 +0100
                Re: Building CPython BartC <bc@freeuk.com> - 2015-05-16 01:43 +0100
                Re: Building CPython MRAB <python@mrabarnett.plus.com> - 2015-05-16 02:16 +0100
                Re: Building CPython Marko Rauhamaa <marko@pacujo.net> - 2015-05-16 11:08 +0300
                Re: Building CPython Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-16 19:40 +1000
                Re: Building CPython Marko Rauhamaa <marko@pacujo.net> - 2015-05-16 16:59 +0300
                Re: Building CPython Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-17 04:18 +1000
                Re: Building CPython Marko Rauhamaa <marko@pacujo.net> - 2015-05-16 21:55 +0300
                Re: Building CPython Marko Rauhamaa <marko@pacujo.net> - 2015-05-17 01:51 +0300
                Re: Building CPython Marko Rauhamaa <marko@pacujo.net> - 2015-05-17 23:49 +0300
                Re: Building CPython Terry Reedy <tjreedy@udel.edu> - 2015-05-15 19:54 -0400
              Re: Building CPython BartC <bc@freeuk.com> - 2015-05-15 10:32 +0100
                Re: Building CPython Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-05-16 12:55 +1200
                Re: Building CPython Jonas Wielicki <jonas@wielicki.name> - 2015-05-17 14:25 +0200
                Re: Building CPython BartC <bc@freeuk.com> - 2015-05-17 14:41 +0100

csiph-web