Compact layout of Plain Python Objects

[markshannon]

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 = b

This 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.

1. The overhead of maintaining the dictionary, even if it is never used directly, is large.
2. If we cannot share keys, things get even worse.

Which suggests two broad strategies:

1. Avoid creating the dictionary, if we don't have to.
2. 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.attr accesses 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.

[gvanrossum]

I sense a connection to the idea of Hidden Classes (from the JavaScript world, esp. v8).

[markshannon]

Hidden classes (originally known as "maps" Chambers, 92 sect 6.1.1) have a couple of important disadvantages.

• The set of objects with the same set of attributes (a "clone family" in Chambers, 92) may not match the set of objects with the same class, requiring excessive specialization [1]
• Hidden classes can form a very large graph, with no lifetimes constraints. This graph may become very large and is very difficult to garbage collect, as it is rooted on the empty hidden class.

[1] Suppose we want to specialize for attribute lookup on an instance. Suppose our prototype object belongs to set S containing all object with the same map (hidden class) and the set C containing all objects with the same actual class.
We will have to specialize for the set S ∩ C which may well be considerably smaller than either S or C.

[markshannon]

There are two things we need to do to get close to the ideal layout.

1. In the compiler, or possibly using runtime feedback, select a dictionary keys to be shared that will maximize the size of S ∩ C, ideally making S ∩ C ≈ C.
2. Select an object layout that minimizes the space used for those object that are in the set S ∩ C and that degrades gracefully for other objects.

Where S in the set of all objects with the same dictionary keys, and C is 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 as

a → 1
b → 2

or as

a → 1
b → 2
c → ∅

The later form may be more efficient if it allows the keys {'a', 'b', 'c'} to be shared across many dictionaries.

[markshannon]

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]

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]

Instead of using some wild guesses heuristics 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:

1. Over allocating the shared dict keys in the class is reasonably cheap, costing a few hundred bytes. Classes already take a few KB.
2. Over allocating the values array for a few objects is also cheap.

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 = 20

For 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_size will 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)
• Values must not have gaps, or it violates dictionary ordering (unless we change the rules on attribute dicts)

[methane]

I expect this idea is not good at performance/complexity ratio.

How about starting with simpler approach?

• values are not embedded in the instance.
  • We can allocate values with the size of shared dict keys.
• __dict__ created on-demand. values are transferred to the dict.

[gvanrossum]

Mark can speak for himself, but to me the disadvantage of that is the need to allocate two blocks of memory instead of one for the values, and the extra pointer deref to get at the values in a specialized version of LOAD_ATTR. (And the fact that the guard in the specialized opcode would have to check that the values pointer is still there.) It's true that that approach is less complex to code, though.

[markshannon]

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.