Implementing something like CPython's gc.freeze() in the C API?

[HaroldCindy]

My list of GC'd objects is generally dominated by Protos and Closures that are always added to the script environment by my binding code. I add a lot of helper functions, and GC traversal time for them adds up, even though they will never be collected, and they should never have references to data that should be collected before state destruction (I've removed setfenv() and they have no GC'd upvalues.)

CPython has a gc.freeze() function that moves all objects at the time of calling to a "permanent generation" where the objects are never traversed or considered for GC. That model fits well with a generational GC, but doing this with Luau's GC seems less trivial. It seems that I could mark walk the heap and mark all protos and closures with the fixedbit used for strings, and add a guard against traversing such objects in reallymarkobject() and propagatemark(). Ideally that would allow me to ignore any proto from the "initial" script state, but allow collecting protos generated by loadstring() and such later on.

I'm concerned about the validity of this approach given the various gclist fields and g->gray and g->grayagain lists. Is there a sensible way to reconstruct those linked lists once I've "frozen" everything, is there a better approach? I already have a traversal function for all GC'd objects that can mark all Protos and Closures as fixed appropriately.

[HaroldCindy]

Hmm, now that I look at it, g->gray and g->grayagain should be cleared out so long as I run a luaC_fullgc() before the freeze, so I don't think they should be an issue? Seems that marking all closures (without collectable upvals) and protos white + fixed after a luau_load() + luaC_fullgc() would be enough to get this to work. I'll try and hack something together and report back.

[HaroldCindy]

I got something basic working (not in PR-able form,) and the results are promising. Using my gc.freeze() equivalent runConformance() and forcing 50000 full GCs on every yield interrupt results in a conformance test runtime of 5.2s vs 9.7s without the freezing. Obviously this is a pretty synthetic test-case, but it does show that avoiding traversing builtins (and the readonly module tables that contain them) is valuable and can reduce GC overhead. I also double-checked that the GCCOUNT is the same for all tests before and after the change, everything was the same.

Branch is here https://github.com/luau-lang/luau/compare/master...HaroldCindy:luau:experiments/gc_freezing?expand=1.

One thing I'm having trouble with is marking Protos fixed. I seem to get a lot of ASAN use-after-poison errors if I try to freeze them after calling luau_load() (see note in lapi.cpp.) Any pointers from those who understand the GC mechanics? I going to work on this for my own stuff, but I think others might be interested in having some version of this functionality available upstream.

[HaroldCindy]

I've hacked around this for the moment by not fixing Protos with table or closure constants, and added some guardrails in lgcdebug.cpp to catch fixed->non-fixed reference errors if they occur.

[HaroldCindy]

@petrihakkinen This may be of interest, since i was initially looking at what would be involved in implementing your Light C Function suggestion, and arrived at this as a less invasive and perhaps more upstreamable solution.

We currently have over a thousand C functions exposed to Lua scripts (not counting the built-in Luau functions). Do you think it could make a difference for a full GC pass, if these functions would be light C functions?

Without going into too many details here, we are running certain, highly domain specific Lua scripts in a multithreaded environment. We have currently maybe 50 of these VM instances running in parallel, completely separated from each other. Luckily these scripts hardly allocate any memory at runtime (after initial setup) so GC cost should still be manageable.

While the alloc overhead is of course unavoidable without something like light C functions, a strategy of marking "simple" C functions and their enclosing (sandboxed / readonly) modules as fixed and avoiding traversing them in the GC seems like a viable avenue of reducing the associated GC overhead.

[HaroldCindy]

Made a little heap graphing utility that outputs to graphviz using the luaC_enumheap() function, all the traces make sense to me, but I can see what my issue was with closure and table constants before. I'm just going to avoid fixing protos with those constants for now, fixing with those properly would be a little hairy. I'll probably special-case fixing for ipairs and friends since those upvals should never change (and would allow fixing the readonly globals table,) but otherwise C functions with upvals shouldn't be fixed

[HaroldCindy]

Did some graph generation to show the paths that would have to be traversed during marking. I eliminated any fixed nodes that didn't have a downstream reference to a non-fixed object (other than function envs,) since they wouldn't have to be traversed. The results look promising, now that ipairs() and pairs() are fixed.

Green-bordered objects are fixed, red-bordered objects are unfixed.

native_userdata.lua with fixallcollectable(), called and graphed before luau_load()

native_userdata.lua with fixallcollectable(), called and graphed after luau_load()

native_userdata.lua without fixallcollectable(), called and graphed before luau_load()

native_userdata.lua without fixallcollectable(), called and graphed after luau_load()

Not embedded, it's enormous and even more unreadable than the above. Imagine the above but with tons of protos and constants sprinkled in.

[petrihakkinen]

This is interesting. I'll try to find some time to test this in a game project. Note that this not only decreases the GC overhead of C functions but also fixed strings which can be significant for some applications. For example, we use string atoms for enums in our binding layer and all those strings live forever...

[vegorov-rbx]

@HaroldCindy we don't have plans to support/accept freezing objects with references (only string are supported).

[HaroldCindy]

No worries, thanks for having a look!