Repository navigation
Conversation
Codecov Report✅ All modified and coverable lines are covered by tests. Additional details and impacted files@@ Coverage Diff @@
## master #19476 +/- ##
=======================================
Coverage 98.58% 98.59%
=======================================
Files 182 182
Lines 23322 23353 +31
Branches 5 5
=======================================
+ Hits 22993 23024 +31
Misses 328 328
Partials 1 1
Flags with carried forward coverage won't be shown. Click here to find out more. ☔ View full report in Codecov by Harness. 🚀 New features to boost your workflow:
|
|
Code size report: |
|
I'm surprised how much code size this costs. You can see from the CI that a small samd board no longer fits in flash. Either we need to be able to disable this optimisation at compile-time, or maybe we do indeed need two separate implementations of the GC: minimal vs fast. |
Smells like something new is being pulled in that wasn't before- might have to poke into that! Even the RP2 numbers are quite surprising, but the instances of +2k are downright suspicious. |
ffef0a3 to
c015a47
Compare
|
Those |
|
Update: Much more realistic sizes. Many ports were unrolling a loop in GC that exploded out to ~2k. SAMD is still tight though, clearly doesn't take much to push it over the edge. WebAssembly test failures seem to be based on very specific memory checks. Looking into the others as I get time.
(I really ought to get myself some more hardware and build capacity locally 😭) |
Keep the packed 2-bit allocation table but read and write it a 32-bit word (16 blocks) at a time in the hot loops: - gc_sweep_free_blocks classifies a word of blocks in registers, with fast paths for all-free and full-tail-run words (one memset). - gc_deal_with_stack_overflow finds marked heads with a word scan and ctz rather than testing every block. - the gc_alloc free search skips fully-occupied words 16 blocks at a time while keeping the per-byte path for the common near-resume hit, so worst-case allocation latency drops without an alloc-throughput cost. The table is rounded to a whole number of scan words and its start is word-aligned. Representation and table memory are unchanged (2 bits per block). Signed-off-by: Phil Howard <[email protected]>
The mixed-word loop in gc_sweep_free_blocks has a compile-time-constant trip count, so at -O3 (and at -O2 once the vectoriser is enabled) the compiler fully unrolls it, inflating the function from ~230 bytes to ~2.4 KB. That is enough to push tight targets (e.g. the samd21 boards) over their flash budget. Pin the loop with #pragma GCC unroll 1; the word-at-a-time fast paths above it are unaffected. Signed-off-by: Phil Howard <[email protected]>
The sweep and stack-overflow scans read the allocation table a 32-bit word at a time and map word bit 2*k to block w*16+k, which only holds when the four table bytes load little-endian. On a big-endian host the bytes load reversed, so the sweep frees/keeps the wrong blocks and the overflow scan re-marks the wrong ones, corrupting the heap (seen as widespread failures on the big-endian qemu_mips CI target). The table is logically little-endian, so normalise each scanned word with MP_LE32TOH on load and MP_HTOLE32 on store; both are no-ops on little-endian targets. Add the MP_HTOLE16/32 and MP_LE16TOH/32TOH helpers alongside the existing MP_HTOBE ones to complete the set. The free-search word skip is a symmetric occupancy test and is unaffected. Signed-off-by: Phil Howard <[email protected]>
bead0a2 to
b393603
Compare
2 participants
Keep the packed 2-bit allocation table but read and write it a 32-bit word (16 blocks) at a time in the hot loops:
The table is rounded to a whole number of scan words and its start is word-aligned. Representation and table memory are unchanged (2 bits per block).
This is a broad, less band-aidy application of the technique in #19363 which is probably a better thing to focus on.
Testing
Fuzz and A/B testing between Unix and the RP2 port. Not sufficient to fully back this approach.
Gives up to a ~4.4x speedup on collection on an RP2350 (Pico LiPo 2, with PSRAM and split heap enabled), with no regressions:
Less impressive:
Live-buffer collection is dominated by marking the buffer, which word-aligning the table doesn't touch - so it only shaves the sweep portion (~7%). This is what #19367 aims to address (skip uninteresting buffers).
Trade-offs and Alternatives
I think it goes without saying that completely re-writing GC in the name of performance is not a task to be approached lightly.
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.