Typos in garbage collector docs

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

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

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?)

@Michael-WhiteCapData

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.

@willy-b

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

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:

."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 ↩
.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.) ↩ ↩²
."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 ↩ ↩²
._PyObjectStack_Pop is used by gc_propagate_alive, e.g. at https://github.com/python/cpython/blob/e2ff498cc03886b73fca0429ee745b04646ad8e0/Python/gc_free_threading.c#L1346 ↩
._PyObjectStack_Push is used by gc_propagate_alive, e.g. at https://github.com/python/cpython/blob/e2ff498cc03886b73fca0429ee745b04646ad8e0/Python/gc_free_threading.c#L705 ↩
. _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 ↩
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 ↩

(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.)

pythonGH-157724: In InternalDocs Garbage Collector docs make clear so…

pythonGH-157724: Comment typo fixes ONLY for gc.c and gc_free_threadi…

pythonGH-157724 - more GC documentation cleanup

pythonGH-157724 - GC doc cleanup

pythonGH-157724: Fix external gc.rst outdated `gc.is_tracked({})` val…

Hello Python team!

I sent up a PR at #157879 (needs skip news label added by a team member to show as passing tests), with what I mentioned so far in this issue plus

Typo fixes in comments (no code changes) in gc.c and gc_free_threading.c
Added a note in a few places where something is specific to the non-free-threaded build
- At
  
  cpython/InternalDocs/garbage_collector.md
  
  Line 285 in 41d0922
  
  objects that have already been visited once (by unsetting the `PREV_MASK_COLLECTING`
  
  note "PREV_MASK_COLLECTING" is the name of the flag used in the non-free-threaded build
- At
  
  cpython/InternalDocs/garbage_collector.md
  
  Line 634 in 41d0922
  
  In order to save memory, the two linked list pointers in every object with GC
  
  , note the "fat pointer"/"tagged pointer" memory saving techniques applied to the two linked list pointers discussed in that section are specific to the non-free-threaded build
- noted "Why moving unreachable objects is better" applies only to the non-free-threaded build (update
  
  cpython/InternalDocs/garbage_collector.md
  
  Line 304 in 212e603
  
  Why moving unreachable objects is better
  
  )
- noted that objects do not move to/from an unreachable list in the free-threaded build (the _PyGC_BITS_UNREACHABLE ob_gc_bits flag is set)
For the free-threaded build object header description, replaced the pad field with ob_flags:
At bc262de#diff-87272721a5cf1cd9915d6f503f6a7bbefa2f26c935c7ce83ca78706afd0ad05aR155
it seems _padding was replaced with ob_flags as part of GH-125174: Mark objects as statically allocated. #127797 .
Noted ob_ref_shared is Py_ssize_t so size_t-sized and not necessarily pointer sized.
See

cpython/Include/object.h

Line 165 in b0dda15

Py_ssize_t ob_ref_shared; // shared (atomic) reference count

, vs claim in original

cpython/InternalDocs/garbage_collector.md

Line 150 in b0dda15

other fields, `ob_tid`, `ob_ref_shared`, and `ob_type`, are all

.
Also https://peps.python.org/pep-0353/#why-not-py-intptr-t .
removed "This process is really a breadth first search over the object graph" regarding propagating reachable status from objects found to be reachable as it is not so simple
e.g. on the free-threaded build, for each object during the heap traversal found to be reachable within the unreachable flagged items,
it seems a new depth-first (not breadth-first) search is initiated to propagate the reachability status
see

cpython/Python/gc_free_threading.c

Line 1461 in 212e603

if (gc_visit_heaps(interp, &mark_heap_visitor, &state->base) < 0) {

, mark_heap_visitor , calls gc_clear_unreachable then
mark_reachable (important)

cpython/Python/gc_free_threading.c

Line 1039 in 212e603

mark_reachable(PyObject *op)

which seems to use a stack to do a DFS

cpython/Python/gc_free_threading.c

Line 1032 in 212e603

return _PyObjectStack_Push((_PyObjectStack *)stack, op);

,

cpython/Python/gc_free_threading.c

Line 1048 in 212e603

op = _PyObjectStack_Pop(&stack);
updated the external-facing gc.rst for an outdated gc.is_tracked({}) value to reflect the results post- Remove lazy dictionary tracking #127010
it appears that since at least Remove lazy dictionary tracking #127010 in 3.14 gc.is_tracked({}) has returned True, but as of

cpython/Doc/library/gc.rst

Line 205 in 9232c21

>>> gc.is_tracked({})

the external GC documentation was not updated for this while the internal documentation, e.g.

cpython/InternalDocs/garbage_collector.md

Line 726 in 9232c21

>>> gc.is_tracked({})

was, so I update the external to be consistent here.

Caveats: This PR #157879 concerns InternalDocs/garbage_collector.md which was reviewed in order to find the items fixed (mostly just brought up to date) here. However, there may still be additional aspects that are out of date -- if I find them, I will send a follow up PR, but in a first pass, these are what I find and it is a review sized batch of updates that I am confident are needed (to improve accuracy for readers) so I am sending them.
Only one item is reviewed from Doc/library/gc.rst in this PR that was found to be out of date and inconsistent with InternalDocs/garbage_collector.md but that article may have further items needing to be brought up to date. Other GC related documentation, e.g. Doc/c-api/gcsupport.rst , Doc/c-api/refcounting.rst WERE NOT reviewed at all yet in preparing this and are not covered by this PR. I will review those and come back to this ticket.

Thanks so much to the Python team for considering these updates to fix mostly outdated content in the InternalDocs garbage_collector.md article and some typos.

Navigation Menu

Repository navigation

Typos in garbage collector docs #157724

Documentation

Linked PRs

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

	_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;
	}

Typos in garbage collector docs #157724

Description

Documentation

Linked PRs

Activity

zware commented on Sep 18, 2026

gvanrossum commented on Sep 18, 2026

willy-b commented on Sep 18, 2026

StanFromIreland commented on Sep 18, 2026

willy-b commented on Sep 18, 2026

Footnotes

willy-b commented on Sep 18, 2026

willy-b commented on Sep 23, 2026

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions