Address review comments and clarify code a bit

python · markshannon · Dec 6, 2024 · Nov 9, 2024 · Nov 10, 2024 · Nov 11, 2024
commit d3c21bb57092428592b86af28246ed1221b002f5
diff --git a/InternalDocs/garbage_collector.md b/InternalDocs/garbage_collector.md
@@ -523,15 +523,15 @@ but doing too much work slows down execution.

 To work out how much work we need to do, consider a heap with `L` live objects
 and `G0` garbage objects at the start of a full scavenge and `G1` garbage objects
-at the end of the scavenge. We don't want amount of garbage to grow, `G1 ≤ G0`, and
+at the end of the scavenge. We don't want the amount of garbage to grow, `G1 ≤ G0`, and
 we don't want too much garbage (say 1/3 of the heap maximum), `G0 ≤ L/2`.
 For each full scavenge we must visit all objects, `T == L + G0 + G1`, during which
 `G1` garbage objects are created.

 The number of new objects created `N` must be at least the new garbage created, `N ≥ G1`,
 assuming that the number of live objects remains roughly constant.
 If we set `T == 4*N` we get `T > 4*G1` and `T = L + G0 + G1` => `L + G0 > 3G1`
-For a steady state heap `G0 == G1` we get `L > 2G` and the desired garbage ratio.
+For a steady state heap (`G0 == G1`) we get `L > 2G0` and the desired garbage ratio.

 In other words, to keep the garbage fraction to 1/3 or less we need to visit
 4 times as many objects as are newly created.
@@ -544,11 +544,11 @@ Everything in `M` is live, so `I ≥ G0` and in practice `I` is closer to `G0 +

 If we choose the amount of work done such that `2*M + I == 6N` then we can do
 less work in most cases, but are still guaranteed to keep up.
-Since `I ≥ G0 + G1` (not strictly true, but close enough)
-`T == M + I == (6N + I)/2` and `(6N + I)/2 ≥ 4G`, so we can keep up.
+Since `I ≳ G0 + G1` (not strictly true, but close enough)
+`T == M + I == (6N + I)/2` and `(6N + I)/2 ≳ 4G`, so we can keep up.

 The reason that this improves performance is that `M` is usually much larger
-than `I` Suppose `M == 10I`, then `T ≅ 3N`.
+than `I`. If `M == 10I`, then `T ≅ 3N`.

 Finally, instead of using a fixed multiple of 8, we gradually increase it as the
 heap grows. This avoids wasting work for small heaps and during startup.

diff --git a/Python/gc.c b/Python/gc.c
@@ -1544,40 +1544,32 @@ mark_at_start(PyThreadState *tstate)
    return objects_marked;
 }

+
+/* See InternalDocs/garbage_collector.md for more details. */
+#define MAX_HEAP_PORTION_MULTIPLIER 5
+#define MARKING_PROGRESS_MULTIPLIER 2
+
 static intptr_t
 assess_work_to_do(GCState *gcstate)
 {
    /* The amount of work we want to do depends on two things.
     * 1. The number of new objects created
-     * 2. The heap size (up to twice the number of new objects, to avoid quadratic effects)
-     * 3. The amount of garbage.
-     *
-     * We cannot know how much of the heap is garbage, but we know that no reachable object
-     * is garbage. We make a (fairly pessismistic) assumption that half the heap not
-     * reachable from the roots is garbage, and count collections of increments as half as efficient
-     * as processing the heap as the marking phase.
-     *
-     * For a large, steady state heap, the amount of work to do is at least three times the
-     * number of new objects added to the heap. This ensures that we stay ahead in the
-     * worst case of all new objects being garbage.
+     * 2. The heap size (up to a multiple of the number of new objects, to avoid quadratic effects)
     */
    intptr_t scale_factor = gcstate->old[0].threshold;
    if (scale_factor < 2) {
        scale_factor = 2;
    }
    intptr_t new_objects = gcstate->young.count;
-    intptr_t max_heap_fraction = new_objects*5;
-    intptr_t heap_fraction = gcstate->heap_size / SCAN_RATE_DIVISOR / scale_factor;
-    if (heap_fraction > max_heap_fraction) {
-        heap_fraction = max_heap_fraction;
+    intptr_t max_heap_portion = new_objects * MAX_HEAP_PORTION_MULTIPLIER;
+    intptr_t heap_portion = gcstate->heap_size / SCAN_RATE_DIVISOR / scale_factor;
+    if (heap_portion > max_heap_portion) {
+        heap_portion = max_heap_portion;
    }
    gcstate->young.count = 0;
-    return new_objects + heap_fraction;
+    return new_objects + heap_portion;
 }

-/* See Internal GC docs for explanation */
-#define MARKING_PROGRESS_MULTIPLIER 2
-
 static void
 gc_collect_increment(PyThreadState *tstate, struct gc_collection_stats *stats)
 {