Hidden classes

[gvanrossum]

See my hick branch

My idea:

• For a "hot" class (instantiated >N times for some N) create a hidden class based on contents of __dict__ after __init__ returns.
• (Could also use the shared keys that are stored in ht_cached_keys.)
• Next time when creating a new instance, instantiate the hidden class instead.
• Hidden class uses __slots__ machinery: for each attribute there's a reserved slot in the instance.
• For a class C, the hidden class C_ inherits directly from C.
• There's a pointer in the type object for C pointing to C_.
• The speed benefit comes from the inline cache for LOAD_ATTR.
  • In master: ceval.c#L3172
  • Or in my disassembler branch from LOAD_ATTR_SLOT and STORE_ATTR_SLOT.

Stuff to do:

• How do we handle the reference cycle between C and C_
• How to handle a subclass D of C, which gets its own hidden class D_. (Need to ensure slots line up.)
• Hide the existence of the hidden class from a lots of places:
  • self.__class__ should point to C, not C_
  • self.__dict__ should somehow deoptimize the object (but not the class)
  • Should C_ be allowed to appear in C.__subclasses__()?

Critique:

• Shared-keys dictionaries provide some of the same benefits: the size of such a dict is an object header plus a gap-free array of values, so the extra space cost is just the dict header. And there won't be any effort hiding anything from the user in this case. However, even with the LOAD_ATTR inline cache (which caches the index in the array of values) there is a fair amount of pointer chasing needed to get to the value.
• We should benchmark whether we see enough of a speedup for a class that's manually been given __slots__ compared to the same class without __slots__ to assess whether to pursue this further.

[markshannon]

Using __slots__ will definitely be faster, because there is much less overhead. You'd need to emulate managing the hidden classes as well to get a fairer benchmark.

[markshannon]

My biggest reservation about this is the complexity of handling dictionaries that are explicitly accessed and modified.
That's going to be complex.

[markshannon]

Another option to consider, is to lay out the dictionary's values directly after the object header and add a flag to the dictionary to indicate that layout was used.
That way, the logical structure remains the same, requiring no change to most code.
Deallocation of the object and dict would need to be aware of the flag to avoid leaks and incorrect frees, but the code changes would tiny in comparison.

[gvanrossum]

That's very clever. I suppose when the dict gets extended beyond the original set of keys the values get copied to a new array, and the original object just has a bunch of dead space. That seems reasonable.

But we'd need a flag in the object (not its type) indicating that this arrangement is valid, if we wanted something like a LOAD_ATTR_SLOT specialized opcode (or special handling for slots in the LOAD_ATTR inline cache, as in current master). That flag would probably end up costing 8 bytes, but without that flag we'd always have to go through the dict object header (which might be fine).

[benjamingr]

My biggest reservation about this is the complexity of handling dictionaries that are explicitly accessed and modified.
That's going to be complex.

Typically the workaround for that is to not use hidden classes for those classes and instead fallback on dictionaries.

[gvanrossum]

See also #72.

[markshannon]

This is now obsolete.
#72 provides all the advantages of hidden classes, but none of the problems discussed above when the __dict__ is directly accessed or modified.