py/gc: Track data and skip scan, MICROPY_GC_NO_SCAN - #19367

Code size report:

Reference:  extmod: Remove support for mbedTLS <3.0. [19e685e]
Comparison: unix/coverage: Add coverage test for the GC scan table. [merge of 5fc37c8]
  mpy-cross:   +24 +0.006% 
   bare-arm:    +0 +0.000% 
minimal x86:    +0 +0.000% 
   unix x64:  +312 +0.036% standard[incl +32(data)]
      stm32:   +76 +0.019% PYBV10
      esp32:   +76 +0.004% ESP32_GENERIC[incl +48(data)]
     mimxrt:   +96 +0.024% TEENSY40
        rp2:  +380 +0.039% RPI_PICO_W[incl +4(bss)]
       samd:   +60 +0.022% ADAFRUIT_ITSYBITSY_M4_EXPRESS
  qemu rv32:   +71 +0.016% VIRT_RV32

Codecov Report

✅ All modified and coverable lines are covered by tests.
✅ Project coverage is 98.59%. Comparing base (19e685e) to head (5fc37c8).

@@            Coverage Diff             @@
##           master   #19367      +/-   ##
==========================================
+ Coverage   98.55%   98.59%   +0.03%     
==========================================
  Files         182      182              
  Lines       23342    23380      +38     
  Branches        5        5              
==========================================
+ Hits        23005    23051      +46     
+ Misses        336      328       -8     
  Partials        1        1              

☔ View full report in Codecov by Harness.
📢 Have feedback on the report? Share it here.

This incredibly unhelpful graph illustrates that there's a very real, if vanishingly small cost to adding this change, affecting routing garbage collection in smaller memory environments.

It's only paid if the feature is turned on however, and the relative benefit for even modest buffers (96k is absolutely peanuts on 8MB PSRAM, but this was tested on an RP2040 to show the worst case tradeoff) far, far outweighs any cost.

And here's the same test on a Pico LiPo 2 with 8MB PSRAM enabled:

What each test measures

• frame_manual - Per-frame time (us) of a render loop that allocates a 1 KB bytearray + a small list each frame and calls gc.collect() EVERY frame (predictable pacing). p50=median frame, p99/max=worst-case stalls.
• frame_ondemand - Same render loop with no manual/threshold control - GC only fires when the heap fills (cheap average, large spikes).
• frame_threshold - Same render loop, but using gc.threshold() auto-collection instead of collecting manually.
• churn_per_alloc_ns - Per-allocation time (ns) churning 50000 transient 4-element lists - allocation throughput including amortised GC.
• collect_empty_us - gc.collect() pause (us) on a near-empty heap - the fixed overhead of a collection.
• collect_3000_lists_us - gc.collect() pause (us) with 3000 live small lists (real pointers) - these must be scanned, so no-scan cannot help.
• free_start - Free heap (bytes) after a full collect at start. Higher is better; the no-scan table costs ~1 bit/block of heap.
• collect_96k_bytearray_us - gc.collect() pause (us) with one live 96 KB bytearray. The headline case: a large pure-data buffer the mark phase would otherwise scan word-by-word for pointers.

Note that the 96k bytearray is only allocated in that specific test, since it would massively skew the other tests in favour of this feature being turned on.

And since those were so bad, here's a graph which cuts right to the gist of the change:

Again I'm shooting low here, this is just the difference in collect times in SRAM, which probably makes it a reasonable sell even for a stock Pico 2 / Pico 2 W. PSRAM's speed (or lack thereof) compounds this effect.

Since this ties in strongly with the optimised tail scan (#19363) here's a graph of them working together, again just SRAM:

Very persuasive graphs!

Of note, @tannewt implemented a very similar idea in CircuitPython last year, see adafruit#10264. CircuitPython went even further and updated most of the places they call m_malloc(). Not saying we have to follow their example instead, but it's useful to consider as an alternative base (and their implementation has been quite heavily tested at this point, I assume).

The main potential for problems I can see comes from code which might play fast and loose with what they keep in the bytearray. For example, use of uctypes.addressof(buf) and then the caller assumes they can store pointers to other data in that uctypes structure and have the other data stay alive. This pattern is rare enough that perhaps we could add a gc_mark_for_scan(ptr) C API that re-tags that buffer, and call it from the the implementation of functions like uctypes.addressof().

Of note, @tannewt implemented a very similar idea in CircuitPython last year

I've heard plenty of rumblings of long-lived data and seen some of @tannewt's videos diving deep into GC. They have such a closely aligned set of problems to what we (Pimoroni) deal with (big silly fun hardware projects) so it figures! I'll have a glance over and see how it compares. (I think it's obvious, but I kinda got carried away with this stuff, since we really wanted the extra perf downstream and were happy to own scary changes)

perhaps we could add a gc_mark_for_scan(ptr) C API that re-tags that buffer, and call it from the the implementation of functions like uctypes.addressof().

I did wonder about having an explicit opt-in to make a memory region no-scan, but it feels like no-scan is the typically happy path (short of C bindings which allocate structs or objects that contain pointers... something I was repeatedly bitten by in the early days of my Pico exploits) so opting in to scan makes a lot of sense (as long as you, uh, don't forget).

I'm currently deep into benchmarking, verifying and testing a complete rewrite to GC to peer into the hypothetical future of what we could possibly gain. For large RAM allocations this skip change still absolutely demolishes any other optimisation we could make directly to GC, and I'm poised to ship this in our Badgeware builds for road testing.

I had a look at CircuitPython's version of this adafruit#10264 and I do prefer the one here:

• this one is a much smaller change to the GC, easier to understand
• this one only touches a few types to start with (str, array) which means less chance for a regression
• this one is more optimal in the GC sub-tree scanning phase when the block is skipped, because it does not unnecessarily compute n_blocks (CircuitPython implementation still computes n_blocks but never uses the value)

So IMO we should try to get this PR merged.

Some feedback for the changes themselves.

I think the feature should be named in the positive rather than in the negative with "no-scan table":

• rename NTB to STB (scan table byte) or PTB (pointer table byte) and invert the bit logic (set it if the corresponding block may contain GC pointers and should therefore be scanned)
• rename GC_ALLOC_FLAG_NO_SCAN -> GC_ALLOC_FLAG_CONTAINS_NO_GC_POINTERS to make it very clear what is going on
• rename malloc_no_scan() -> malloc_with_no_gc_pointers()
• rename m_new_no_scan() -> m_new_with_no_gc_pointers()
• rename the config option from MICROPY_GC_NO_SCAN to something like MICROPY_GC_ENABLE_CONTAINS_NO_GC_POINTERS

Changes made. Also did a pass over the comments.

Did you have any thoughts on projectgus's point, ie: adding something like gc_mark_has_pointers(ptr) so functions that deal with pointers can mark their target buffer?

Did you have any thoughts on projectgus's point, ie: adding something like gc_mark_has_pointers(ptr) so functions that deal with pointers can mark their target buffer?

Yes, it's probably a good idea to add such a facility.

Following @projectgus 's idea, what do you think about reusing the existing uctypes.addressof(buf) function to take an optional extra argument which specifies whether to set the STB bit on the corresponding buffer? (The argument would default to False.)

Also, I think this PR can be taken out of draft.

Following @projectgus 's idea, what do you think about reusing the existing uctypes.addressof(buf) function to take an optional extra argument which specifies whether to set the STB bit on the corresponding buffer? (The argument would default to False.)

I think at the point we're making it optional it ought to be a new function. Though I'd agree with the between-the-lines reading that making it quietly promote unscanned RAM to scanned is also not necessarily the right shape.

I'm not sure where such a function should be hung, but gc.mark_as_scanned(buf) seems... plausible?

I'm not sure where such a function should be hung, but gc.mark_as_scanned(buf) seems... plausible?

I'd rather add it in the micropython module, because CPython doesn't have such a function in the gc module.

@projectgus any thoughts/ideas about how this user-facing API could work? Either an optional argument to uctypes.addressof(buf, contains_pointers=False) or a new function micropython.buf_contains_pointers(buf)?

@projectgus and I discussed how to add a way to mark that an area of memory may contain pointers.

It's also possible to store pointers with viper, inline-asm and machine.mem32. Eg:

mport machine

@micropython.asm_thumb
def addressof(r0):
    pass

@micropython.viper
def store_ptr_viper(buf: ptr32, idx: int, obj: int):
    buf[idx] = obj

@micropython.asm_thumb
def store_ptr_asm(r0, r1, r2):
    add(r0, r0, r1)
    str(r2, [r0, 0])

obj = dict()
obj_addr = addressof(obj)
print("obj_addr", hex(obj_addr))

buf = bytearray(12)
buf_addr = addressof(buf)
print(hex(buf_addr), buf.hex())
machine.mem32[buf_addr] = obj_addr
print(hex(buf_addr), buf.hex())
store_ptr_viper(buf, 1, obj_addr)
print(hex(buf_addr), buf.hex())
store_ptr_asm(buf, 8, obj_addr)
print(hex(buf_addr), buf.hex())

That outputs (on RPI_PICO2):

obj_addr 0x20011360
0x200113a0 000000000000000000000000
0x200113a0 601301200000000000000000
0x200113a0 601301206013012000000000
0x200113a0 601301206013012060130120

Given that there are many ways to do this (including the uctypes approach) I think it's best to provide a helper function to mark that memory has pointers. And we can mention in the release notes that this is a change in behaviour.

I suggest to make the new Python function guarded against MICROPY_ENABLE_GC so it can be used regardless of whether this GC-no-scan feature is enabled or not.

Also we need a public C-level function for C users (as mentioned by @projectgus above).

Here is my suggestion for the Python-level API:

micropython.buf_contains_ptrs(buf)

It would accept anything with the buffer protocol (so makes sense to name it "buf" and not something like "mem_contains" or "array_contains").

Looking into this, but might have added a bug in the UNIX build which needs squashing first.