[Python-Dev] Idea: Dictionary references

[Andrew Barnert]

On Dec 17, 2015, at 15:41, Franklin? Lee <leewangzhong+python at gmail.com> wrote:
> 
> I already know that we can't use recursion, because it bypasses MRO.
> I'm also not yet sure whether it makes sense to use refs for classes
> in the first place.
> 
> As I understood it, an attribute will resolve in this order:
> - __getattribute__ up the MRO. (raises AttributeError)
> - __dict__ up the MRO. (raises KeyError)
> - __getattr__ up the MRO. (raises AttributeError)
> 
> 
> My new understanding:
> - __getattribute__. (raises AttributeError)
>    - (default implementation:) __dict__.__getitem__. (raises KeyError)
> - __getattr__ up the MRO. (raises AttributeError)

No, still completely wrong.

If __getattribute__ raises an AttributeError (or isn't found, but that only happens in special cases like somehow calling a method on a type that hasn't been constructed), that's the end of the line; there's no fallback, and everything else (IIRC: searching MRO dicts for data descriptors, searching the instance dict, searching MRO dicts for non-data descriptors or non-descriptors, special-method-lookup-and-call __getattr__, raise AttributeError... and then doing the appropriate descriptor call at the end if needed).

I was going to say that the only custom __getattribute__ you'll find in builtins or stdlib is on type, which does the exact same thing except when it calls a descriptor it does __get__(None, cls) instead of __get__(obj, type(obj)), and if you find any third-party __getattribute__ you should just assume it's going to do something crazy and don't bother trying to help it. But then I remembered that super must have a custom __getattribute__, so... you'd probably need to search the code for others.

> If this is the case, then (the default) __getattribute__ will be
> making the repeated lookups, and might be the one requesting the
> refcells (for the ones it wants).

Yes, the default and type __getattribute__ are what you'd want to optimize, if anything. And maybe special-method lookup.

> Descriptors seem to be implemented as:
>    Store a Descriptor object as an attribute. When a Descriptor is
> accessed, if it is being accessed from its owner, then unbox it and
> use its methods. Otherwise, it's a normal attribute.

Depending on what you mean by "owner", I think you have that backward. If the instance itself stores a descriptor, it's just used as itself; if the instance's _type_ (or a supertype) stores one, it's called to get the instance attribute.

> Then Descriptors are in the dict, so MIGHT benefit from refcells. The
> memory cost might be higher, though.

Same memory cost. They're just objects whose type's dicts happen to have a __get__ method (just like iterables are just objects whose type's dicts happen to have an __iter__ method). The point is that you can't cache the result of the descriptor call, you can cache the descriptor itself but it will rarely help, and the builtin method cache probably already takes care of 99% of the cases where it would help, so I don't see what you're going to get here.

>> On Thu, Dec 17, 2015 at 5:17 PM, Andrew Barnert <abarnert at yahoo.com> wrote:
>>> On Dec 17, 2015, at 13:37, Andrew Barnert via Python-Dev <python-dev at python.org> wrote:
>>> 
>>> On Thursday, December 17, 2015 11:19 AM, Franklin? Lee <leewangzhong+python at gmail.com> wrote:
>>> 
>>> 
>>>> ...
>>>> as soon as I figure out how descriptors actually work...
>>> 
>>> 
>>> I think you need to learn what LOAD_ATTR and the machinery around it actually does before I can explain why trying to optimize it like globals-vs.-builtins doesn't make sense. Maybe someone who's better at explaining than me can come up with something clearer than the existing documentation, but I can't.
>> 
>> I take that back. First, it was harsher than I intended. Second, I think I can explain things.
> 
> I appreciate it! Tracking function definitions in the source can make
> one want to do something else.

The documentation is pretty good for this stuff (and getting better every year). You mainly want the data model chapter of the reference and the descriptor howto guide; the dis and inspect docs in the library can also be helpful. Together they'll answer most of what you need.

If they don't, maybe I will try to write up an explanation as a blog post, but I don't think it needs to get sent to the list (except for the benefit of core devs calling me out of I screw up, but they have better things to do with their time).

>> First, for non-attribute lookups:
>> 
>> (Non-shared) locals just load and save from an array.
>> 
>> Free variables and shared locals load and save by going through an extra dereference on a cell object in an array.
> 
> In retrospect, of course they do.
> 
> It sounds like the idea is what's already used there, except the refs
> are synced to the locals array instead of a hash table.

Yes, which is already faster than what you want to do.

More importantly, trying to put globals into the locals dict as you've described isn't going to do any good--first, because the locals dict is ignored in favor of the fast array (which has to be structured at compile time), and second, because it wouldn't be any faster than the globals dict anyway; a dict lookup is a dict lookup.

In case you're wondering why globals don't just work the same way as nonlocals, as just one more nested scope: I'd guess it's to allow the global scope to be more dynamic than local scopes. You can create and pass around functions that reference globals that haven't been defined yet, exec up new types and functions, modify globals(), execute a module statement by statement instead of having to do it all at once (which would make the REPL more painful), use a partially-constructed module (so if a and b both import each other, that's only a problem if they access each others' globals at module scope), etc.

>> Globals do a single dict lookup.
> 
> A single dict lookup per function definition per name used? That's
> what I'm proposing.

Each LOAD_GLOBAL is a dict lookup at call time.

A major point of Victor's FAT Python, as I understand it, is to change that to a dict lookup at function build time (I think meaning MAKE_FUNCTION/MAKE_CLOSURE, not compile time) instead of call time, with guards to restore the original slow code if the results are out of date, by storing the result in the code object's constants table (which basically works like the fast-locals array, but even better, because it's a static part of the code object rather than copied into the end of the stack frame).

I don't see what other optimizations you can add on top of that that would help anything, except maybe in some weird edge case where FAT's guards keep getting tripped but somehow the references could be preserved. For normal code, you're just adding overhead for no benefit.

But builtins, FAT apparently has a problem that's not trivial to solve. So if you could make builtins appear like globals in a way that makes FAT's globals dict guard actually work correctly with them, that sounds like it would be a major contribution.

> For example, (and I only just remembered that comprehensions and gen
> expressions create scope)

Yes, because they define and call an anonymous function, and function definitions create scopes.

>    [f(x) for x in range(10000)]
> 
> would look up the name `f` at most twice (once in globals(), once in
> builtins() if needed), and will always have the latest version of `f`.
> 
> And if it's in a function, the refcell(s) would be saved by the function.

I don't know what this last sentence means.
> 
> 
>> Builtins do two dict lookups.
> 
> Two?

Actually, I guess three: first you fail to find the name in globals, then you find __builtins__ in globals, then you find the name in __builtins__ or __builtins__.__dict__.

>> Class attributes (including normal methods, @property, etc.) do two or more dict lookups--first the instance, then the class, then each class on the class's MRO. Then, if the result has a __get__ method, it's called with the instance and class to get the actual value. This is how bound methods get created, property lookup functions get called, etc. The result of the descriptor call can't get cached (that would mean, for example, that every time you access the same @property on an instance, you'd get the same value).
> 
> Yeah, I would only try to save in a dict lookup to get the descriptor,
> and I'm not sure it's worth it.
> 
> (Victor's response says that class attributes are already efficient, though.)
> 
> 
>> So, if the globals->builtins optimization is worth doing, don't tie it to another optimization that's much more complicated and less useful like this, or we'll never get your simple and useful idea.
> 
> Sure. I couldn't figure out where to even save the refcells for
> attributes, so I only really saw an opportunity for name lookups.
> Since locals and nonlocals don't require dict lookups, this means
> globals() and __builtin__.