Typos in garbage collector docs

[willy-b]

Documentation

Hello Python team!

Thanks so much for everything you do!
It seems there are a few typos and possibly unclear statements about memory usage in the InternalDocs garbage collector page (hopefully reporting it is useful to the team; I would have fixed the typos and the bad L2 cache size, e.g. where the Python team has written 6GB instead of MB, except that there appear also to be possible conceptual issues so I figured I should ask here.)

In describing the Python garbage collector, the Internal Docs at

cpython/InternalDocs/garbage_collector.md

Line 299 in 5539c2a

and neither does it in any other way require additional memory proportional to the

mention:

Pragmatically, it's important to note that no recursion is required by any of this,
and neither does it in any other way require additional memory proportional to the
number of objects, number of pointers, or the lengths of pointer chains.
Apart from O(1) storage for internal C needs, the objects themselves contain all the storage
the GC algorithms require.

This seems to be making the claim that the extra data stored on the objects (e.g. the doubly linked list bidirectional pointers used for GC) are the only O(n) storage used by the GC in any of its algorithms.

However, using a separate unbounded LIFO stack is mentioned:

cpython/InternalDocs/garbage_collector.md

Line 536 in 5539c2a

prefech buffer. Second, there is a LIFO stack, of unlimited size. When object

Second, there is a LIFO stack, of unlimited size. When object references are found using tp_traverse, they are enqueued in the buffer if it is not full, otherwise they are pushed to the stack.

(Note also the typo, "prefech" should be "prefetch" at

cpython/InternalDocs/garbage_collector.md

Line 536 in 5539c2a

prefech buffer. Second, there is a LIFO stack, of unlimited size. When object

.)

But a LIFO stack of unbounded size (for any GC phase) does not seem consistent with the earlier claim (see above for link) that "Apart from O(1) storage for internal C needs, the objects themselves contain all the storage
the GC algorithms require"

(Also a breadth first search is mentioned

cpython/InternalDocs/garbage_collector.md

Line 294 in 5539c2a

process is really a breadth first search over the object graph. Once all the objects

This process is really a breadth first search over the object graph.
).

---

Next, the display of text seems to be broken for most markdown viewers (including Github's) at

cpython/InternalDocs/garbage_collector.md

Line 451 in 5539c2a

been remarked that doing a full collection every <constant number> of object

Indeed, it has
been remarked that doing a full collection every of object
creations entails a dramatic performance degradation in workloads which consist
of creating and storing lots of long-lived objects (for example, building a large list
of GC-tracked objects would show quadratic performance, instead of linear as
expected). Using the above ratio, instead, yields amortized linear performance
in the total number of objects (the effect of which can be summarized thusly:
"each full garbage collection is more and more costly as the number of objects
grows, but we do fewer and fewer of them").

where <constant number> doesn't display on GitHub's markdown viewer (so it is showing instead as "doing a full collection every of object creations"):

Indeed, it has been remarked that doing a full collection every of object creations entails a dramatic performance degradation in workloads which consist of creating and storing lots of long-lived objects (for example, building a large list of GC-tracked objects would show quadratic performance, instead of linear as expected).

See the following screenshots:

---

Finally, at:

cpython/InternalDocs/garbage_collector.md

Line 619 in 5539c2a

- AMD Ryzen 5 7600X, 64 GB RAM, 384 KB L1, 6 GB L2, 32 MB L3, compiled with GCC 12.2.0

specifications for a machine used for testing are given:

AMD Ryzen 5 7600X, 64 GB RAM, 384 KB L1, 6 GB L2, 32 MB L3

where "6 GB L2" should be "6 MB L2" (off by ~1000x) ( compare to AMD's listing also https://web.archive.org/web/20260918004211/https://www.amd.com/en/products/processors/desktops/ryzen/7000-series/amd-ryzen-5-7600x.html )

---

Thanks so much!

Linked PRs

• gh-157724: Fix garbage collector documentation typos #157733

[zware]

Would you like to submit a PR to fix these things?

[gvanrossum]

Maybe shorten the title to "Typos in garbage collector docs" and put the remaining text in the body of the initial comment? (You can edit that, you know?)

[willy-b]

I agreed right away in emoji to send a PR to fix these after the team encouraged it (and pushed up a commit) but it looks like @Michael-WhiteCapData wants to take the low hanging parts in #157733 and beat me to it, which is fine by me.

[StanFromIreland]

@willy-b I've closed the other one, and assigned you.

[willy-b]

Thanks team, working on this now!

Re: the possible non-typo, conceptual part of this issue,
for one example, in the free-threaded build ( https://peps.python.org/pep-0703/ , https://peps.python.org/pep-0779/ )
already discussed in many places in this article,
the "LIFO stack, of unlimited size"¹ mentioned seems to not use the existing pointers on "the objects themselves"²,
e.g. in gc_propagate_alive (of which it is said "In most programs, this marks nearly all objects that are not actually unreachable"³)
_PyObjectStack_Pop⁴
and _PyObjectStack_Push⁵
are used,
and the push seems to allocate fresh memory⁶

cpython/Include/internal/pycore_object_stack.h

Lines 37 to 48 in e2ff498

	_PyObjectStack_Push(_PyObjectStack *stack, PyObject *obj)
	{
	_PyObjectStackChunk *buf = stack->head;
	if (buf == NULL || buf->n == _Py_OBJECT_STACK_CHUNK_SIZE) {
	buf = _PyObjectStackChunk_New();
	if (buf == NULL) {
	return -1;
	}
	buf->prev = stack->head;
	buf->n = 0;
	stack->head = buf;
	}

(for one simple case to consider, in the free threaded build with prefetch disabled,
the gc_propagate_alive appears to be a DFS of "nearly all objects that are not actually unreachable"³ so would seem to have worst case O(n) additional memory requirements -- contrary to "neither does it in any other way require additional memory proportional to the
number of objects"²).

Thus in the first version of my PR in addition to the typo fixes I am proposing to remove the following paragraph in its current form as potentially confusing:

cpython/InternalDocs/garbage_collector.md

Line 299 in 5539c2a

and neither does it in any other way require additional memory proportional to the

Pragmatically, it's important to note that no recursion is required by any of this,
and neither does it in any other way require additional memory proportional to the
number of objects, number of pointers, or the lengths of pointer chains.
Apart from O(1) storage for internal C needs, the objects themselves contain all the storage
the GC algorithms require.

(it might still be descriptive of some configuration of the non-free threaded GC⁷, to gc.c instead of gc_free_threading.c, only if the doubly linked list pointers used for all traversals in that implementation are built into the objects in advance, with the caveat that adding overhead to each object, instead of externalizing it to a separate stack, still requires memory proportional to the number of objects)

Thanks so much to the Python team for building great tools and a welcoming and productive community!

References:

Footnotes

1. ."LIFO stack, of unlimited size" used during mark alive free threaded build GC phase: https://github.com/python/cpython/blob/5539c2a5437acc4f4719aabac375368e0d310bd9/InternalDocs/garbage_collector.md?plain=1#L536 ↩

2. .vs. "the objects themselves contain all the storage the GC algorithms require" https://github.com/python/cpython/blob/5539c2a5437acc4f4719aabac375368e0d310bd9/InternalDocs/garbage_collector.md?plain=1#L301 (may be true for the non-free threaded build only, for gc.c NOT gc_free_threading.c ; though "neither does it in any other way require additional memory proportional to the number of objects" is still possibly misleading as adding per object overhead still requires memory proportional to the number of objects and is not necessarily more scalable than externalizing that cost to a separate data structure.) ↩ ↩²

3. ."nearly all objects that are not actually unreachable" are visited during the mark alive free threaded build GC phase: https://github.com/python/cpython/blob/e2ff498cc03886b73fca0429ee745b04646ad8e0/Python/gc_free_threading.c#L1363 ↩ ↩²

4. ._PyObjectStack_Pop is used by gc_propagate_alive, e.g. at https://github.com/python/cpython/blob/e2ff498cc03886b73fca0429ee745b04646ad8e0/Python/gc_free_threading.c#L1346 ↩

5. ._PyObjectStack_Push is used by gc_propagate_alive, e.g. at https://github.com/python/cpython/blob/e2ff498cc03886b73fca0429ee745b04646ad8e0/Python/gc_free_threading.c#L705 ↩

6. . _PyObjectStack_Push seems to allocate fresh memory, not reuse pointers already on the "objects themselves": https://github.com/python/cpython/blob/e2ff498cc03886b73fca0429ee745b04646ad8e0/Include/internal/pycore_object_stack.h#L37-L48 ; and see also gc_mark_span_push https://github.com/python/cpython/blob/e2ff498cc03886b73fca0429ee745b04646ad8e0/Python/gc_free_threading.c#L666-L678 ↩

7. in other places in the same section distinctions are made between the free threaded and non-free threaded GCs, e.g. at https://github.com/python/cpython/blob/5539c2a5437acc4f4719aabac375368e0d310bd9/InternalDocs/garbage_collector.md?plain=1#L229 but not for this paragraph ↩

[willy-b]

(Also, for the record, no AI or LLMs were used in discovering, reporting, or writing up this issue, the comment above, or in preparing the commits that I am putting into a PR soon.)