Edit: I'm putting the final tests on optimising traversing gaps in the heap and finaliser scans which rely on this same technique. Please hold!

⚠️ Wrt to summary below, the description below covers the single case for tail traversal, but I've generalised this approach to skipping over free runs and finaliser scans. Needs some more testing to find the baseline impact of this change. Split into three commits to make it easier to bisect and test.

Tests in: free run doesn't do as much as I'd hoped, but it does something (~.5us/KB on PSRAM).

Summary

Somewhat a counterpart to: #19367

The GC sweep walked the allocation table one 16-byte block at a time. The interior of a large allocation is a long run of AT_TAIL entries (an ATB byte of 0xaa is four tail blocks, a 32-bit word 0xaaaaaaaa is sixteen).

Such a run never contains a HEAD/MARK, so it is wholly live or wholly dead and can be processed a word at a time - free the whole word when dead, or just advance the high-water mark when live - instead of touching every block. This is the dominant sweep cost for large pure-data buffers: e.g. on RP2040 a 96 KB bytearray collect drops from 7363us to 5747us.

The optimisation is gated behind a new MICROPY_GC_FAST_TAIL_SWEEP option, default disabled; when off the sweep is unchanged. Enabling it costs +112 bytes of flash and no RAM on RP2040 (Cortex-M0+).

The four ATB bytes are read via memcpy (with an alignment hint) rather than casting to uint32_t*, to avoid a strict-aliasing violation. A byte-step-to-alignment then word-step loop issues only aligned word accesses, so it is safe on cores that fault/trap on unaligned loads (Cortex-M0+, Hazard3 RISC-V); validated on M0+, Cortex-M33 and RISC-V. MICROPY_GC_HOOK_LOOP is called within the word loop.

Testing

I have rigorously tested this in every way I can contrive, including byte for byte comparisons of memory state before/after GC and before/after this change and multi-hour runtime tests (including benchmarking) on our Tufty 2350 board. Testing covered both the Hazard3(RISCV)/M33 cores of the RP2350, and the RP2040's M0.

Note that the standard perfbench suite will do anything from very small deviations in performance to wild swings (I measured -30% in aes and -20% in pystone ). Since GC rarely changes (it's one of the dark corners of the project that takes work to understand and care to change) I end up with some new contrived script every time I want to exercise it with benchmarks.

Would the perftest suite be the right place for a GC benchmark? Given how painful GC is on PSRAM (granted, MicroPython never envisioned leaping from 192k to 8MB RAM) it might be worth measuring it specifically.

Trade-offs and Alternatives

This feature is gated behind a flag since it uses about 112 bytes of flash. It is particularly performant for the large allocations - such as heavy bytearrays or buffers - that we're using in our graphics API, but does add a very small cost to gc.collect(). This is very much an enable-if-you-use-PSRAM change, since GC is absolutely pathological when you start storing megabytes of buffers.

I have another chain to add a new no-scan bitflag which gives an orders of magnitude improvement for GC on large PSRAM buffers. Again extremely rigorously tested and benchmarked by every angle I can contrive- this PR is the cherry on top, but also self contained and the less invasive of the two changes.

A weekend of crunching, tests and tweaks has left me with something I'm not completely terrified to raise in a PR. Nonetheless I would appreciate some thoughts/independent verification on this to catch anything I might have missed.

Generative AI

I used generative AI tools when creating this PR, but a human has checked the
code and is responsible for the code and the description above.

(and of course I forgot to --signoff 🤦)