This PR implements prefetching as suggested in the issue. The benchmarks that are part of pyperformance generally don't show much difference since they don't use enough memory to make prefetch effective.

• Issue:Use "prefetch" CPU instructions during the marking phase of the GC #129201

Source code for the two "big" benchmarks. These create a fairly large object graph and then callgc.collect() to time it.

gc big tree
gc big

Updated benchmarks for commitabfc49a. The5ff2fbc commit made previous versions of this PR look much worse on certain benchmarks. That's because that commit improves the "mark alive" pass so that it can find many more alive objects in some cases (fixes finding objects referred to only from stack).

I tried optimizing this PR so that it was at least as fast as current "main" when the number of objects was relatively small. However, I was not successful with that so I instead made it so that the prefetch approach is only used if the number of long-lived objects is over 200k. Based on tests on my Ryzen 5, that seems about the point were the prefetch approach is faster.

Run on a Macbook Pro M3, clang 19, PGO/LTO enabled. Both "base" and "prefetch" are configured with./configure --enable-optimizations --disable-gil --with-lto.

Benchmarks below run on a Ryzen 5 7600X.

pyperformance results comparing to merge base.

Some notes about the implementation:

• On my Macbook M3, it seems that usingPREFETCH_T0 is slightly faster whereas on my AMD Ryzen 5 desktop thePREFETCH_T1 is a bit faster. The difference is pretty small. There are also prefetch instructions that indicate you are going to write to the word (second parameter in the__builtin_prefetch() variation). If we are visiting a GC object for the first time, we will be writing to it to set the "alive" bit in the flags. However if it's not a GC object or we have visited it already, we don't write. So reads would seem quite a bit more common.
• cross-platform prefetch preprocessor logic was inspired by the zstd source code. I haven't tested the Windows or__aarch64__ conditions of that block.
• TheBUFFER_SIZE,BUFFER_HI, andBUFFER_LO have been moderately tuned based on benchmarking on my Ryzen 5 machine. I'm kind of surprised thatBUFFER_HI is so small but that's what works best. There could be some additional tuning done on the logic of when to put objects on the stack vs into the buffer, when to push a new "span" vs adding part of it to the buffer. I did what I thought was logical but didn't benchmark all different approaches.
• I run some tests that recorded a trace of the prefetch and access (following pointer) and then computed some statistics from the trace log. Based on this, it seems like the prefetch buffer is working fairly well (the median delay between prefetch and access was 14 on one benchmark run, ASCII histogram below).

Prefetch window statsmean 52.07285263157895median 14.0max 256   25.60 |65,304  | ******************************   51.20 |5,590   | **   76.80 |3,562   | *  102.40 |2,683   | *  128.00 |2,278   | *  153.60 |2,285   | *  179.20 |2,377   | *  204.80 |2,238   | *  230.40 |2,753   | *  256.00 |5,930   | **-------- |------- | -------      N= |95,000

• Having the specializedgc_mark_traverse_list andgc_mark_traverse_tuple functions seems like a win. Even if the program doesn't use many long lists and tuples it doesn't cost much to have them.
• The_PyTuple_MaybeUntrack() call is a bit expensive and it gets done on every collection. I considered adding a_PyGC_BITS_NEW bit and set it on newly created tuples. Then we would only need to check a tuple once rather than once per collection. I tried disabling the tuple untracking but things got slower.
• As currently implemented, all the object pointers revealed bytp_traverse go through the mark buffer/stack. That seems wasteful given that a good fraction of them will be non-GC objects and some of them are known things like None or True. I tried adding a check for BSS allocated objects (using__bss_start andend) but that doesn't seem like a win. Maybe with some more refinement this would work. We could allocate a bunch of known non-GC objects into a certain region of memory and thengc_propagate_alive() could just quickly skip them based on the pointer address.
• I considered adding a new number field to the type object, to allowgc_propagate_alive() to use a switch statement to use the correct traverse function. Something likeswitch (Py_TYPE(ob)->tp_gc_ordinal) where thetp_gc_ordinal value on known types is set on startup. That way, the switch statement can use an efficient jump table or similar. However, with only list and tuple specialized at this time, it doesn't seem worth it.