Repository navigation
Compact object headers #70
Description
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.
Activity
gvanrossum commentedon Jul 20, 2021
Saturating refcounts will slow down INCREF/DECREF everywhere (this is why Facebook's immortal objects aren't accepted).
nascheme commentedon Jul 20, 2021
Doing something with
PyGC_Headis easier because it is an internal implementation detail, unlikeob_typeorob_refcnt. I did some work on trying to move thePyGC_Headinformation 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 theirmspandata structure would be a way to compactly store thePyGC_Headinfo. I was struggling to figure out how to handle different object sizes.The
gc_colorsgit 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 commentedon Jul 21, 2021
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 commentedon Aug 6, 2021
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:
Which should speed up cycle GC interactions in allocation and deallocation.
iritkatriel commentedon Aug 6, 2021
Wouldn't it be simpler to just use the high bits for these flags?
markshannon commentedon Aug 6, 2021
How would you test efficiently for
refcnt == 1whenDECREFing?iritkatriel commentedon Aug 6, 2021
mask the high bits away.
iritkatriel commentedon Aug 6, 2021
Either of these changes will make it confusing for people when they look at refcnts in the debugger.
markshannon commentedon Aug 6, 2021
(ob_refcnt & 0xfffffff) < 2is slower thanob_refcnt_shifted < 8Either can be offset to make the comparison faster.
(ob_refcnt_less_2 & 0xfffffff) < 0orob_refcnt_less_2_shifted < 0