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