Compact object headers

[markshannon]

How much space do the various fields of an object header need?

Field	Currently uses	Minimum	Realistic goal
class	1 word (pointer)	Depends on how many classes ~24 bits	1 word less 8 bits for alignment (it shouldn't be that hard to align class objects to 256 bytes, or to steal a few top bits for a few years before hardware needs all 64).
Reference count	1 word	Half word or less using saturating reference counting	1 word less 3+n bits. Where 1/2**n is the fraction of memory that can be allocated to objects
GC data	2 words	~5 bits, plus external data for younger generations	~5 bits (can go in class word) + temporary ref count in top half of ref count
weakref	1 word	1 bit if no weakrefs	1 bit + external table when needed
Total	5 words	1 word	2 words

A 1 word header is going to be tricky and may well be so convoluted that it makes performance worse.
However I think the two word header is feasible.

The bits required for GC and finalization are:

• Generation: 2 bits
• Scratch bits: 2 bits (for internal GC state)
• Needs finalizing: 1 bit
• Has weakref: 1 bit

Of course, aiming for a two word header doesn't mean we can't improve things incrementally.
A three word header would still be a significant improvement and would be significantly simpler to implement.

[gvanrossum]

Saturating refcounts will slow down INCREF/DECREF everywhere (this is why Facebook's immortal objects aren't accepted).

[nascheme]

Doing something with PyGC_Head is easier because it is an internal implementation detail, unlike ob_type or ob_refcnt. I did some work on trying to move the PyGC_Head information into packed data structured stored inside the obmalloc memory arenas. See https://discuss.python.org/t/removing-pygc-head-for-small-objects/1743 . Since I posted to that thread, I studied the Go memory management. Adopting a scheme like their mspan data structure would be a way to compactly store the PyGC_Head info. I was struggling to figure out how to handle different object sizes.

The gc_colors git branch is a proof of concept, showing that we can do the cyclic GC work without having double-linked lists (stored with gc_prev/gc_next). The code is rough and slow but I think it basically works. You don't say it explicitly but since you have 2 bits for GC generation and 2 bits for internal GC state, you must be thinking of something similar.

My current thinking on the "removal of PyGC_Head" idea is that it's probably not a win for memory usage. You gain by packing info compactly, rather than using whole machine words for things. However, there are other overheads that bring the memory usage back to similar levels. I think it's possible the alternative scheme could be faster. Manipulating and traversing double-linked lists is quite slow on modern CPUs. Memory bitmaps that define object sets could be faster. If you benchmark gcmodule.c, you should see that a lot of time is spent on the linked-list manipulation.

[markshannon]

Saturating refcounts will slow down INCREF/DECREF everywhere (this is why Facebook's immortal objects aren't accepted).

I didn't say it would be fast 🙂 Just that's what would use the least amount of memory

I don't know what the sweet spot that uses as little memory as possible without negatively impacting performance will be.
I expect that we will never reach that point, but I'm hoping that we can get a "good enough" solution that uses significantly less memory than we do now.

[markshannon]

The low 4 bits of the refcount can be freed for flags very easily:
https://github.com/python/cpython/compare/main...faster-cpython:experimental-free-4-bit-in-refcount?expand=1

Three of these can be used for:

• May be part of a cycle
• Needs finalizing
• Has weakref

Which should speed up cycle GC interactions in allocation and deallocation.

[iritkatriel]

Wouldn't it be simpler to just use the high bits for these flags?

[markshannon]

How would you test efficiently for refcnt == 1 when DECREFing?

[iritkatriel]

mask the high bits away.

[iritkatriel]

Either of these changes will make it confusing for people when they look at refcnts in the debugger.

[markshannon]

mask the high bits away.

(ob_refcnt & 0xfffffff) < 2 is slower than ob_refcnt_shifted < 8
Either can be offset to make the comparison faster.
(ob_refcnt_less_2 & 0xfffffff) < 0 or ob_refcnt_less_2_shifted < 0

[markshannon]

Given that immortal objects look likely, it makes sense to use saturating reference counts, as they use less memory.
We can reduce the size of a plain Python object header from 7 words (8 allocated) to 4 and speedup a few key look ups.

Here's a possible object header for 3.12:

struct object_header {
     half_uintptr_t ob_saturating_refcount;
     uint8_t gc_bits;
     uint8_t flags;
     PyObject *ob_type;
}

Flags would include:

• Has weakref
• Needs finalizing
• Has preheader (saves looking this up in type when freeing object)
• Is GC (saves looking this up in type when doing GC)

GC objects would have a two word pre-header

struct object_pre_header {
     void *tagged_dict_or_values_pointer;
     uintptr_t gc; /* Data needed by the GC */
};

It might be cleaner to put the "dict or values" flag in flags, but that would need an extra memory read to access the values.

[markshannon]

The first step is to combine the dict and values pointer and move the weakref to that slot.

     PyDictValues *values;
     PyObject *dict;
     GC_HEAD;
     intptr_t refcnt;
     PyTypeObject *type;
     ...
     PyWeakReference *weakref;

becomes

     PyWeakReference *weakref;
     PyDictOrValues *dict_or_values;
     GC_HEAD;
     intptr_t refcnt;
     PyTypeObject *type;
     ...

which reduces the size of the header from 7 (often taking 8) words to 6.

[kumaraditya303]

Since PyDictOrValues cannot be accessed using the C API we could implement this with a tagged pointer with LSB = 1 for values and LSB = 0 for __dict__ or vice-versa.

[gvanrossum]

Doesn't this break the ABI?

[kumaraditya303]

No, the offset of ob_refcnt and ob_type are still the same so is stable ABI compatible. PyGC_Head currently takes 2 words so it is at ((PyGC_Head *)(((char *)(o))-sizeof(PyGC_Head))) where o is the pointer so 16 bytes negative offset on 64 bit builds. With this header scheme weakref slot would be at 32 bytes negative offset from the object.

[gvanrossum]

Cool, Mark's message made me forget that the actual "PyObject *" points in the middle of the struct. :-)