Python Global Attribute Cache

In my previous post we saw how Python optimizes bound method invokation, It's time to see other particularly important optimizations, the one(s) used for attribute lookup. Because of the dynamic nature of Python, looking up an attribute involves a complex algorithm (I've talked about it here and optimizing it is key, not just to make Python fast, but almost to make it usable. Notice that this optimization is also very important when invoking a method (obj.do_something()), as method invokation involves first that complex look up process to find the callable object, then the creation of a bound method (which optimization/omission we saw in our previous post), and then calling/invoking that callable. So in modern Python there are 2 complementary optimizations that are used for attribute lookup. We'll see in this post the first of them:

- Global Attribute cache / MRO cache
We know that looking up an attribute (either through the LOAD_ATTR bytecode instruction or the dynamic getattr() function), involves following the MRO for that object. Of course Python allows us to patch an existing class, replacing one method by another, adding methods, changing base classes, but this is not particularly common. Most times classes remain static, which means that normally looking up one method/attribute through the MRO will repeatidly come up with the same result. That should prompt an idea, "let's use a cache!", and yes, that's what CPython does:

CPython therefore maintains an internal cache for type-level attribute resolution, historically called the method cache, although it is useful for class attributes in general.

That's the Global Attribute cache / MRO cache. It's useful both when looking up an attribute in an instance or directly in the class. Simplifying things a bit, we could see this cache as a sort of dictionary of [type, attribute-name]: value (it's indeed a direct-mapped cache). As explained in the linked post above when accessing an attribute in an instance the lookup mechanism searches the MRO first (class and base classes) and depending on what it finds (or not finds there) it will then search the instance. Because of this, not finding an attribute in the MRO cache is also valuable information, so the cache contains also sort of "NOT_FOUND_IN_MRO" entries. The MRO cache definitively helps in all cases.

PyObject_GenericGetAttr must call _PyType_Lookup first, even for ob.x where x lives in the instance dict, because a data descriptor on the type (such as a property) takes priority over the instance dict. For plain instance attributes that type lookup almost always finds nothing, and caching that“nothing” keeps every ob.x from walking the whole MRO.

Given the dynamic operations allowed by Python, different actions (that I mentioned above: monkey-patching, changing class hierarhcy) will invalidate cache entries, actions things like:

• type.__setattr__ and type.__delattr__: any Cls.attr = ... or del Cls.attr, dunders included (which also refresh the matching C slots).
• Assigning to __bases__ (which recomputes the MRO).
• A few other type mutations.

For this to work there's a key detail. The C structure used to represent Python classes has a tp_version_tag field that changes (after being invalidated) if the class mutates.

Key properties:
0 means “no valid version”. New classes start at 0.
Tags are assigned lazily from one interpreter-wide counter (next_version_tag). A tag is only handed out when something needs one: the specializer, or the global type attribute cache. Classes that are never looked at never get one.
Tags are unique across all types, not per-class sequences, and never reused. So a cached version == N can only ever match one exact state of one exact class.

Invalidation:
Any change that could affect attribute lookup calls PyType_Modified(type), which:
Sets tp_version_tag = 0 on the type.
Walks tp_subclasses recursively and clears theirs too, because a subclass’s MRO lookup depends on its bases' dicts. The next time a tag is needed, a new one is taken from the global counter.

Another key detail, entries in the Global Attribute Cache contain this tp_version_tag. So if a class gets a new tp_version_tag, both tags will no longer match and the cache value won't be used. A normal MRO lookup will be done and the cache entry will be overwritten. Better explained by a GPT:

The lookup (attribute name in type)
Compute the slot in the cache and check entry->version == type->tp_version_tag && entry->name == name (two comparisons). If both match, return entry->value.
On a miss, do the real MRO walk (find_name_in_mro). Then, if the type has or can be given a version tag and the name can be cached, overwrite that slot.