tldr:
Replaces the current generational-only cycle GC with a generational-incremental GC with lower overhead.
Much faster: 3-5% speedup on pyperformance
Shorter pause times: How much shorter depends on the application, a lot. Sometimes 100x shorter, sometimes no shorter
The PEP in full:
Hi,
This looks promising but I feel like the PEP is a bit short on explanations, especially how you came to that particular design.
Regarding some of the PEP details:
The performance improvements come from doing less work in the young generations (one collection per object, not two) and doing less work in the old generation due to the lower survivor rate from the young generations.
Where does the “lower survivor rate” come from? Is it simply the fact that the nursery is now twice as large, or something else? In other words, if you were to double the size of gens 0 and 1 in the legacy GC, such as to halve the number of non-full collections, would that erase the performance uplift of the incremental GC?
For small and short-lived applications, memory consumption is likely to increase due to the larger young generations, but the extra space is bounded at 24MB by default
How does the bounding work? In other words, what kind of metric is used to decide whether the 24MB limit is reached?
Now to the algorithm description:
work_to_do: int = -100_000
Why start at this value? Is it so that the interpreter startup phase isn’t interrupted by too many GC collections?
Also, how did you come to this value?
def scan_reachable(limit):
"""Move some reachable objects from pending to reachable and from
reachable to visited. They are reachable and cannot be garbage.
"""
moved_to_visited = 0
while reachable:
root = reachable.pop()
visited.append(root)
moved_to_visited += 1
for obj in gc.get_referents(root):
if obj in pending:
pending.remove(obj)
reachable.append(obj)
if moved_to_visited >= limit:
return moved_to_visited
return moved_to_visited
What does limit do here? Not only it does not seem to limit the number of values visited, but it also doesn’t affect the return the value (moved_to_visited is always returned).
The work_to_do updates are the particularly opaque part IMHO. This sentence seems to suggest that work_to_do should be roughly equal to len(pending_space), or a fraction thereof:
Increments are collected until sufficient objects have been scanned to keep up with the rate of objects being added to the old generation by the young collections
However, there is then this weird heuristic:
survivors = collect_cycles(increment)
work_to_do -= survivors
collected = candidates - survivors
# If we are collecting lots of objects, that means
# there is a lot of cycle garbage and we need to
# sweep the heap faster.
work_to_do += 2 * collected
(more concisely, work_to_do += 2 * candidates - 3 * survivors, which looks a bit magic)
Did you find this to be useful on some workloads? Detrimental on others? And on which metric? IMHO it would be really useful to have more explanations on how you decided to go with this.
Moreover, it seems that “we need to sweep the heap faster” could be applied in two different ways:
IIUC, this algorithm is implementing option 1 of doing more work at once, but wouldn’t an incremental collector be better served by option 2, so as to avoid ballooning GC pauses?
(that probably implies some kind of dynamic threshold for collections, based on observed collection behavior)
Where does the “lower survivor rate” come from? Is it simply the fact that the nursery is now twice as large, or something else?
It is from allowing objects longer to die.
The difference is that the new GC only scans the oldest part of the young gen, never all of it, and never the nursery.
The nursery may be a twice the size, but the young generation as a whole (nursery and aging) is only 10% larger.
In other words, if you were to double the size of gens 0 and 1 in the legacy GC, such as to halve the number of non-full collections, would that erase the performance uplift of the incremental GC?
No, because you would still be collecting very young objects. And for a fair comparison, you could only increase the size of gen0, not gen1 (doubling threshold0 and halving threshold1)
Why start at this value? Is it so that the interpreter startup phase isn’t interrupted by too many GC collections?
Yes, it is to avoid excessive GC collections at startup.
The number of fairly arbitrary, but assuming objects in 100-200 byte range it represents 10-20Mb which seems reasonable.
What does
limitdo here? …
Whoops, I mis-formatted the pseudo code. The code should be this (note the change in indendation for if moved_to_visited >= limit:
def scan_reachable(limit):
"""Move some reachable objects from pending to reachable and from
reachable to visited. They are reachable and cannot be garbage.
"""
moved_to_visited = 0
while reachable:
root = reachable.pop()
visited.append(root)
moved_to_visited += 1
for obj in gc.get_referents(root):
if obj in pending:
pending.remove(obj)
reachable.append(obj)
if moved_to_visited >= limit:
return moved_to_visited
return moved_to_visited
limit is intended to limit the amount of work done in a single scan, to avoid long pauses.
The
work_to_doupdates are the particularly opaque part IMHO.
I’ll add some more explanation to the PEP.
This sentence seems to suggest that
work_to_doshould be roughly equal tolen(pending_space), or a fraction thereof:
The work_to_do represents the amount of work that the GC needs to do scanning the old gen to keep up. So it must equal or exceed the rate at which objects are added to the old gen, hence the work_to_do += len(survivors) in young_collection()
However, there is then this weird heuristic:
work_to_do -= survivors
work_to_do += 2 * collected
Another mistake. It should be
work_to_do -= candidates
work_to_do += 2 * collected
Each object we scan reduces the work to do, hence work_to_do -= candidates, although most objects scanned aren’t garbage and candidates ≈ survivors.
In theory, the work_to_do += len(survivors) in young_collection() is sufficient to keep up, but by just keeping, quite a lot of garbage could accumulate before it is eventually collected.
Since we are collecting from the least recently scanned part of the heap, the number of objects collected is at least proportional to (and will typically exceed) the ratio of garbage in the heap. So if collected is larger, then the amount of garbage is likely larger and we should accelerate to keep the amount of garbage down, hence the work_to_do += 2 * collected. The 2 * is arbitrary, but it is simple and feels about right.
Sorry for the delay! Hope this is the right place.
I have a few questions after reading the latest PEP and reference implementation.
old_work may reach very low values like -700,000 objects. Maybe it makes sense to add a setting to cap it?-X option?(aging_threshold + 1) / 2 aging spaces plus one nursery space. Each space is 2000 KB, which gives me 12 MB, not 24.Thanks!