Repository navigation
Conversation
Codecov Report✅ All modified and coverable lines are covered by tests. Additional details and impacted files@@ Coverage Diff @@
## master #19363 +/- ##
=======================================
Coverage 98.51% 98.51%
=======================================
Files 177 177
Lines 22992 22993 +1
=======================================
+ Hits 22651 22652 +1
Misses 341 341 ☔ View full report in Codecov by Harness. 🚀 New features to boost your workflow:
|
|
Code size report: |
|
Did some more crunching and benchmarking to discover I'd missed that this same optimisation applies in two other places (ATB all-free and FTB all-zero), currently working on implementing and verifying it, since it conceptually matches this change and they'd make a nice combined package. Will change the flag to something like |
Gadgetoid
changed the title
|
Starting from the no-scan and building the optimised allocation table traversal on top gets us from ~130us/KB down to ~1.6us/KB. This is a very synthetic benchmark with large buffers and a small amount of baseline fragmentation, but it does more or less reflect the real world issues we ran into: 
|
|
FWIW, I've been wanting to explore making a bunch of the byte-oriented parts of gc.c (like the ftb table) into word arrays (with the restriction that the number of blocks then has to be a multiple of the word size, so some ports might lose a little RAM.) I have a theory that codegen for modern 32-bit CPUs will be both smaller and faster, even with some in-register shifting to check each byte in a word. This also makes it very easy to do optimisations like skipping these "all tail" blocks. |
|
These kinds of optimisations are such low-hanging fruit that I'm not surprised I'm not the first to trend that way. Doing this properly from first principles is a good idea, but quite a deep change. Is there precent in MicroPython for maintaining two versions of a thing like GC (easy to swap out in the make/cmake files) for a softer transition? I wonder if we ought to have an agreed-upon benchmark for GC performance so we're not- as I have done- leaning on metrics that support our specific use case. |
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 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: on RP2040 a 96 KB bytearray collect drops from 7363 to 5747 us. This introduces MICROPY_GC_FAST_TABLE_SCANS (default disabled), which gates a family of word-at-a-time scans over the GC's per-block tables; when off the behaviour is unchanged. This commit adds the first: coalescing tail-block runs in the sweep. Following commits add free-run coalescing and a finaliser-table skip under the same option. Enabling this commit alone costs +112 bytes of flash and no RAM on RP2040. 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 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. Signed-off-by: Phil Howard <[email protected]>
Extend the sweep's fast path (MICROPY_GC_FAST_TABLE_SCANS) to skip long runs of free blocks a word at a time, not just all-tail runs. An all-free ATB byte/word (0x00) needs no work - the blocks are already free and not in use - so a large gap (e.g. a freed buffer below still-live data, which keeps the high-water mark up) is crossed 16 blocks per word instead of one at a time. Shares the same word read and byte-step-to-alignment dance as the tail-run coalescing. On a Pico LiPo 2 (RP2350B, 8 MB PSRAM) a collect crossing a 2 MB free hole below live data saves ~.5us/KB. Signed-off-by: Phil Howard <[email protected]>
gc_sweep_run_finalisers() reads the finaliser table (FTB) byte by byte up to the high-water mark to find blocks that may have a __del__. The FTB over a large pure-data buffer is all zero, yet is still scanned a byte at a time - costly when the table lives in slow PSRAM. Under MICROPY_GC_FAST_TABLE_SCANS, skip all-zero FTB words (32 blocks) at a time, using the same aligned-word read as the sweep. A non-zero word (a block that may have a finaliser) always falls through to the unchanged per-byte handler, so finaliser execution is unaffected. Applied only when the FTB is the sole table scanned here (weakref disabled). On a Pico LiPo 2 the finaliser scan for a live 4 MB buffer drops from ~4.0 to ~1.8 ms. Signed-off-by: Phil Howard <[email protected]>
For CI, build tests only. Signed-off-by: Phil Howard <[email protected]>
Not that I can think, but I guess I wouldn't totally rule it out? Would need to ask Damien.
Yes, this can be hard to gauge. Actually some of the "run-perfbench" benchmarks exercise small object GC quite heavily, so if there's no regression (or an improvement) there it's a very good sign. For optimisations around a small number of large buffers then it might be worth adding a benchmark there that uses those, AFAIK none of them do. |
Not really any precedent, but we could do it if it made sense. But I feel like if there's an implementation that's better all round, we should just switch to it. The tests are pretty extensive so should prevent any regressions. |
That's the catch! We have a fine balance of performance vs SRAM/flash cost that skews differently on larger chips. @projectgus did you mean what I know as bitplanes? I had missed the significance of the ftb table reference. It makes sense for individual GC marker bits and makes bolt-on flags much easier to reason about (since everything behaves the same way, rather than special casing ftb and my "uninteresting RAM, don't scan" flag) The downside is that 00 is no longer a reliable marker for "free" since those bits live in different planes, so you need an additional run of bits for "FREE" on top of having everything be strictly - as you say - a multiple of word size. That gives us HEAD, USED and MARK bitplanes with:
Certainly worth sketching that out, because it renders two of my optimisations redundant and gives the third a much cleaner implementation. Edit: I missed the obvious idea that you can just bitplane the two original bits and treat them pretty much as they were before, avoiding any additional memory overhead save for the alignment. |
|
Really early sketch and testing suggests we can get a 3-5x speedup traversing over dead buffers/areas of fragmented data by switching to bitplaned GC, with very little SRAM cost. It might be the "better all round" we're looking for. The difference on Unix doesn't hit until multi megabyte buffers but it does hit, on RP2 PSRAM it's an immediate 3x speedup over a 100k gap and that performance boost is pretty flat up to 4MB (and most likely beyond). Most of my "win" on PSRAM was entirely skipping the mark phase on uninteresting buffers (the 10x speedup in the graph above) and the rest is a very comparable 4x speedup to the numbers I'm seeing in this (maybe a throwaway prototype) GC rewrite. I'm probably comparing apples to oranges though so I'll rustle up some comparable numbers to this band-aid fix and see what we get. |
|
Maybe not relevant here but @tannewt found (adafruit#10264 (comment)) that raising |
|
Somewhat relevant, we set this in PSRAM builds on RP2 or it is - indeed - terribly slow- micropython/ports/rp2/mpconfigport.h Line 91 in ff2ed49 |
I actually meant something else, although bitplanes might also be useful. Need to think carefully about cache locality if grouping multiple things into the bitplane I guess. The change I was thinking of is simpler: For example, the Similarly the ATB array is loaded a byte at a time in As a consequence I think it would make implementing the optimisation from this PR into a very small modification that doesn't take much code at all. (This is all speculation, at this point.) |
|
Aha! I get ya. I did a speculative dive into bitplanes and, indeed, cache locality (especially with PSRAM) does bite very quickly. Ironically the fix is to load and operate upon a word at a time 🤦 I'll put some time into prototyping a word-aligned, bit-packed table and see how it benches. Maybe it's worth exploring with a little more care, If nothing else I'll have learned from it. |
|
Replaced by a less band-aidy fix as suggested by @projectgus - better to focus our efforts on that. Indeed, the code size difference for RP2 is much for muchness this change, though the impact of an un-gated GC change is predictably much pain. See: #19476 |
4 participants
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!
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_SWEEPoption, 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🤦)