Repository navigation
Compact layout of Plain Python Objects #72
Description
Plain Python Objects are, at the Python level, just a thin wrapper around a dictionary.
However, they are generally used as objects with common behavior across all objects of a class.
Consider the much overused example of Color:
class Color:
def __init__(self, r, g, b):
self.red = r
self.green = g
self.blue = bThis object has 3 words of data, but for a header size of H takes a huge (H+1)+(H+4)+5 == 2H+10 words assuming shared keys. Without shared keys it takes an even worse (H+1)+(H+4)+13+5 == 2H+23 words.
We can make two simple observations.
- The overhead of maintaining the dictionary, even if it is never used directly, is large.
- If we cannot share keys, things get even worse.
Which suggests two broad strategies:
- Avoid creating the dictionary, if we don't have to.
- Design the key sharing mechanism to reduce the number of cases where we lose sharing. It might be worth over-allocating the shared keys and values array a bit to achieve this. The compiler should be able to help us here. All
self.attraccesses in a class's methods are visible to the compiler.
Ideally we would like to use H+3 words of memory, but even H+5 (allowing 2 slots for internal use or over allocation) would halve memory use.
Activity
gvanrossum commentedon Jul 21, 2021
I sense a connection to the idea of Hidden Classes (from the JavaScript world, esp. v8).
markshannon commentedon Jul 26, 2021
Hidden classes (originally known as "maps" Chambers, 92 sect 6.1.1) have a couple of important disadvantages.
[1] Suppose we want to specialize for attribute lookup on an instance. Suppose our prototype object belongs to set
Scontaining all object with the same map (hidden class) and the setCcontaining all objects with the same actual class.We will have to specialize for the set
S ∩ Cwhich may well be considerably smaller than eitherSorC.markshannon commentedon Jul 26, 2021
There are two things we need to do to get close to the ideal layout.
S ∩ C, ideally makingS ∩ C ≈ C.S ∩ Cand that degrades gracefully for other objects.Where
Sin the set of all objects with the same dictionary keys, andCis the set of all objects with the same class.Note that an object's dictionary keys is not the same as the set of keys present in the dictionary. E.g. the dict
{a:1, b:1}can be represented asor as
The later form may be more efficient if it allows the keys
{'a', 'b', 'c'}to be shared across many dictionaries.markshannon commentedon Jul 26, 2021
Current object layouts.
With shared keys
Without shared keys
The above diagram is slightly misleading, in that the keys and values are interleaved in the non-shared case. However this does not impact the amount of memory allocated.
Key
markshannon commentedon Jul 26, 2021
By putting the values directly after the
__dict__slot, we can get close to the minimum memory (just one extra field for the__dict__pointer).Compact layout
After accessing the
__dict__If code explicitly accesses the
__dict__of the object, we must create a dictionary. In which case the object would now look like this:which is similar to the current object layout with shared keys, except that the values are allocated directly after the rest of the object.
After adding a new attribute
If a new attribute is added that isn't in the shared keys, then a new keys and values array must be created, much like it is in the current implementation. After adding the new attribute, the object would look like this:
This wastes even more memory than the current approach. Hopefully it will be infrequent enough that we can save a substantial amount of memory overall.
markshannon commentedon Sep 15, 2021
Instead of using some
wild guessesheuristics in the compiler to pre-compute the likely set of attributes of an object, we should do it at runtime.First of all, a couple of observations:
The idea is to pre-allocate the shared dict keys in the class with capacity of 20 (or whatever is the capacity for an allocation of 32) and set an initial size to that same value.
cls->values_size = 20For each new object, after the first, shrink the size of the values until it reaches
capacity(shared_dict_keys) + 1.Even if the ultimate size is 1, we will only waste 171 slots (1.4kb).
We expect that by the time any object creation call is specialized,
values_sizewill have reached its fixed point.If not, we can just defer specialization.
Invariants that must be enforced for each object.
size(valuesarray) >= size(shared_dict_keys)methane commentedon Sep 22, 2021
I expect this idea is not good at performance/complexity ratio.
How about starting with simpler approach?
valuesare not embedded in the instance.valueswith the size of shared dict keys.__dict__created on-demand.valuesare transferred to the dict.gvanrossum commentedon Sep 22, 2021
markshannon commentedon Sep 22, 2021
As an intermediate step, @methane's suggestion makes sense.
However, in the longer term we will want the compact layout described above.
There isn't that much more complexity. Mainly a test in the dict, so it knows who owns the values array when deallocating.
See also #30 (comment) which will allow values to map from a subset of the keys.
markshannon commentedon Dec 2, 2021
The layout we now have (since python/cpython#28802) is quite good and we should probably spend our efforts on making sure that almost all objects use the compact layout and making sure that the C API supports compact layout, rather than trying to make the layout even more compact.
So, I'm deferring this issue for now.
I'm deferring this rather than closing it, as I still think we will want to embed the values into the object eventually. Although, that may not happen until 3.12 or even later.
markshannon commentedon Mar 16, 2023
Definitely not 3.12, but maybe 3.13.
@carljm Would the Cinder team be interested in pursuing this?
carljm commentedon Mar 16, 2023
In principle, yes -- I think it's now acquired permanent residency on our long-term roadmap of things to look at :)
In practice, it's not near the top of the short-term roadmap, and I think it's unlikely that we would prioritize it before we upgrade to 3.12 and can experiment with it relative to the already-done dict-values stuff, which probably means 2024 at best.
So maybe/yes, but not soon.
cc @mpage as someone who has generally been interested in this topic, and @swtaarrs as the person currently managing the Cinder perf roadmap
benjamingr commentedon Dec 2, 2023
I just ran into this in "real life", note the idea in shapes/hidden classes is to learn the shape of objects which allows us to have both compact layout in practice (e.g. if I have a small integer member - it'll take just 32 bytes of memory rather than an object) and inline caches (the shape information is stored on the functions themselves which makes property access (like obj.x) behave like a memory offset "as fast as C".
This proposal doesn't actually address that?
carljm commentedon Dec 13, 2023
CPython 3.11+ has inline caching, and it already does make use of the learned object shape information to make attribute accesses fast. Not everything is described in a single discussion topic :) You may find it interesting to look at
Python/bytecodes.candPython/specialize.c.At this point, this topic is specifically about the remaining step of moving the instance attribute values array inline into the object itself, rather than in a separate block of memory.
markshannon commentedon May 7, 2024
It only took 2 and a half years, but this is done 🎉
kyungjunleeme commentedon Jul 15, 2025
@markshannon Hello :)
While studying slots, I came across your PR.
It looks like a valuable resource for my learning—thank you so much for sharing it!
By the way, may I ask what tool you used for the visualization?
auvipy commentedon Jul 15, 2025
any related PR for this?
kyungjunleeme commentedon Jul 15, 2025
@auvipy python/cpython#28802