Priority: JavaScript-integrated GC or primitives for implementing GC in WASM

[AndrewScheidecker]

My primary concern with WebAssembly right now is not anything in the current spec, but rather that the design anticipates the addition of GC reference types. I think this is an unnecessary coupling of WebAssembly to existing JavaScript engines.

I can understand the motivation for adding GC references, and that the cost doesn't seem so bad to most of you who are implementing runtimes within existing JavaScript engines. But I'm sure you can see that if GC reference types are a de facto requirement, that limits the use of WebAssembly outside of browsers.

Even if it is added as an optional extension, a WebAssembly implementation without it will become pointless if Emscripten uses it. I already have problems running Emscripten compiled binaries in WAVM due to the coupling of its C runtime to its JavaScript harness. If that interface starts to use GC references, then I will need to add a garbage collector to my standalone WebAssembly VM.

I don't want to add a garbage collector to my WebAssembly VM, not because I don't want to write a garbage collector, but because I want to write a garbage collector within WebAssembly. I'm developing a programming language that will compile to WebAssembly, and for many reasons, I think a language-specific garbage collector will be more effective than a language-independent TypedObject collector, even within the limitations of the WebAssembly abstraction.

GC.md is entirely about exposing the JavaScript object model to WebAssembly programs, with no mention of exposing primitives to WebAssembly that allow efficient implementation of a garbage collector. This worries me as much as the risk that Emscripten(or other toolchains) will make GC references a required feature; I know that folks are aware of, and not opposed to, the desire to implement a GC within WebAssembly, but that's clearly not where resources are focused.

In my opinion that focus is misplaced. The web will benefit the most from new applications that are enabled by WebAssembly performance, not from making existing applications faster. I anticipate new applications using WebAssembly will want to work with their own DOM in linear memory, with some isolated code to replicate that into the browser DOM.

I think the strongest argument for a VM-level GC is that for languages whose data maps well to TypedObjects, a VM-level GC benefits from direct access to the hardware and OS. Perhaps this is a worthwhile optimization, but I think enabling a WebAssembly application to do its own GC should be the primary goal.

[lukewagner]

Certainly it makes sense to design the GC feature and toolchain such that it is optional and that plain C/C++/Rust programs don't require it. A possible counterexample would be if using GC references allowed for more efficient integration with Web APIs, but that would presumably only be if the Web API was used.

That being said, if what you want is to compile is a GC'd language, there are several advantages to integrating with the host environment's GC over doing it all w/in linear memory:

• cycles that go between wasm objects and host environment (e.g., DOM) object could be collected by the host environment GC but not by a GC in linear memory; you'd end up with a strong edge that rooted the otherwise-collectable cycle
• host environment GCs are integrated with things like requestAnimationFrame and vsync, allowing them to, e.g., tailor incremental GC slices to end when it's time to start the next frame
• less internal fragmentation by allowing safe reuse of GC arenas between what would otherwise be disjoint wasm linear memories; esp. important on 32-bit with limited virtual address space
• better browser devtool integration since devtools better understand host GC objects
• smaller distributable runtime by reusing what's already in the browser

And I think these justify the work to integrate GC into wasm.

For example, a lisp implementation can store a cons in two words, yet using the web browser object model is unlikely to be nearly as memory efficient. There are also a lot of different tradeoffs that can be made in object models and in garbage collectors and I support wasm being free of the constraints of a particular host implementation. For example, if periodic pauses are not a show stopper for some applications, such as a symbolic mathematics application, then they can use more performance efficient garbage collectors. Also if the garbage collector is implemented within a wasm process then it can run independent of a runtime garbage collector and not block the runtime.

[lukewagner]

Yes, these are reasons why people may still want to implement their own GC using linear memory and adding GC support to wasm should not prevent them from doing so.

[AndrewScheidecker]

Yes, it's even possible to implement a garbage collector in wasm right now, but it would be a lot more practical if there was a way to scan GC references in locals and intermediates. That's a very useful feature that is a subset of the functionality needed for host-defined GC, but AFAICT isn't mentioned anywhere in the design repo.

My concern about host-defined GC is not that it would technically prevent more general GC building blocks, but that:

• It could easily become a required VM feature through adoption by popular toolchains
• And it might be seen as "enough", so efforts to support efficient GC implementations within wasm are blocked

better browser devtool integration since devtools better understand host GC objects

As a secondary benefit, the ability to scan locals and intermediates on the stack would be a big step toward browser-independent, language-specific debug tools.

[lukewagner]

I agree that some amount of opt-in/pay-as-you-go stack inspection would be a generally useful feature for wasm and we should add something like that before long.

I think you make a good point about the toolchain but I think we can accept this as a high-level goal of avoiding a hard dependency on GC for non-inherently-GC sources. I think that's a good idea even on the web because I think it should be possible to create a wasm-without-GC-only worker that doesn't get the usual GC-heap allocated for it.

If the local variables and the values stack can be accessed from anywhere in their dynamic scope then might that invalidate some assumptions implicit in the decoding to the SSA form? Perhaps some more thought needs to be given to the options here and perhaps it even impacts the language design.

One option would be for the wasm code producer to simply not keep pointers that need to be scavenged on the values stack or in local variables at points that might trigger a garbage collection, rather in linear memory. So the local variables and values stack could continue to be well constrained to lexical scope.

Might it help if the local variables and values stack could only be read and not written outside their lexical scope? At first thought that might be enough of a restriction to avoid impacting the SSA decoder? This would support a conservative scavenger of values in the local variables and values stack, but not a precise garbage collector that wants to move objects with pointers from the local variables or values stack.

Lets say that the expressionless encoding, which avoided the values stack but still used local variables, were taken to another extreme and did not even use local variables so that every operator reads and writes to the linear memory. It would have similar problems for the decoder as allowing access to the local variables and stack from any dynamic scope, but perhaps even worse problems because the changes to linear memory persist past the end of the function and would need to be written back.

So at first thought the only practical option seems to be to keep pointers that need to be scavenged out of the local variables and off the values stack?

Would be interested in opinions on the impact of allowing only the reading of the local variables and values stack from any dynamic context, and not writing to these, and would take impact the SSA decoders?

Let's say that it is ok to allow reading of any local variable and the values stack from within their dynamic context, then it seems that the get_value proposal (which is a static reference up the stack) should be fine too? The model would then be that the values stack has read-only values that are dynamically scoped, and the local variables have values that can be read in their dynamic scope but only written in their lexical scope.

Do any of these issues impact the discussed wasm-GC variant? Wouldn't it have the some of these issues too, possible frustrating SSA decoding if GC pointers in local variables or the values stack could be written from any dynamic context?

Sorry, giving this a little more thought it does not seem practical at all to allow access to the local variables or the values stack outside their lexical scope, as that would appear to require they be backed by memory and written back before all calls which does not look practical for performance.

That would seem to leave producers implementing garbage collection to write back any pointers to linear memory at points that can trigger a garbage collection and scavenge them there.

[AndrewScheidecker]

If the local variables and the values stack can be accessed from anywhere in their dynamic scope then might that invalidate some assumptions implicit in the decoding to the SSA form? Perhaps some more thought needs to be given to the options here and perhaps it even impacts the language design.

I think you're observing that there's implementation non-determinism in the lifetime of local variables and intermediate values. Is that right?

I think it's necessary to add something like the LLVM GC statepoint intrinsic: a call that additionally takes a set of value stack locations and local variables that may be mutated by the call. That allows serialization of local state mutations with the call, without pessimistically assuming everything needs to be serialized with the call.

Beyond the local state explicitly serialized through this GC-aware call, it may be useful to allow a stack inspection to observe non-determinism in the form of other live locals and intermediate values.

Might it help if the local variables and values stack could only be read and not written outside their lexical scope? At first thought that might be enough of a restriction to avoid impacting the SSA decoder? This would support a conservative scavenger of values in the local variables and values stack, but not a precise garbage collector that wants to move objects with pointers from the local variables or values stack.

IMO the goal should be precise, compacting GC.

It's not immediately obvious what would be gained by allowing the definition of value stack and local variable locations that can be mutated at a call. Practically these would need to be written back to memory and re-loaded and this could be done explicitly by the producer by just storing them to the linear memory which is already supported. Why add complexity if it is not necessary.

[AndrewScheidecker]

Sorry, giving this a little more thought it does not seem practical at all to allow access to the local variables or the values stack outside their lexical scope, as that would appear to require they be backed by memory and written back before all calls which does not look practical for performance.

The same information used to unwind the callstack for zero cost exception handling can reconstruct the register state at the point of each call. The same information can be used to find and mutate GC references that were in registers at the point of a call, whether they have been saved to the stack by a callee, or are still in a register when GC is triggered.

Thank you, I guess that might work, using meta information to note the live locations and where they are, but it sounds like a lot of complexity for the runtimes. There might still be issues for the SSA decoder if the state can be mutated outside the lexical scope.

[AndrewScheidecker]

Thank you, I guess that might work, using meta information to note the live locations and where they are, but it sounds like a lot of complexity for the runtimes.

It's definitely tricky to implement. However, zero cost exception handling is already on the post-MVP roadmap, and a runtime that prefers simplicity can always just spill those GC references to the shadow stack across calls.

There might still be issues for the SSA decoder if the state can be mutated outside the lexical scope.

You can encode the possibility of this mutation in SSA like this:

%gcRef0 = ... ; The initial value of gcRef.
%gcStatepoint = call ... gcstate=[%gcRef0...]
%gcRef1 = gcmutate %gcStatepoint 0 ; The new, possibly mutated value of gcRef after the GC statepoint
%result = gcresult %gcStatepoint   ; The result of the function called by the GC statepoint

@lars-t-hansen The VM need only sandbox the memory, so a language implementing it's own object system (and possible pointer tagging) need not always be type safe and need not protect the identity of its pointers. Whereas opaque GC pointers need to always be safe to protect the sandbox and you mention not wanting to expose the pointer value to the code running in the VM. Also memory management can often implement this sandbox at little cost, and hardware might even add features to better support a memory managed sandbox in future. Thus code implementing it's own object heap within the sandbox can offer better performance and little burden to the VM.

For example, consider a list (a linked list of cons cells) in which each element is a tagged small integer (like your tagged integers) and code that adds all the list elements. The producer might take advantage of a declaration that these are small integers and that the sum does not overflow a small integer and simply load and add these in single instruction on the x86. I don't see how a language targeting gc-heap allocated objects could approach this level of performance.

For example, with pointer tagging a pointer to a cons cell can have a tagged type which allows a cons cell to consume only two words of memory. I don't see how a gc-heap allocated object system could approach this level of memory efficiency.

I would like to see symbolic maths software such as maxima written in a lisp running on the web efficiently, it seems a fair use case.

If rust is targeting wasm then perhaps the burden should be on the producer to at least try to implement their object system in wasm rather than just lean on the VM consumer to offer an object system with tagged pointers etc to be a target.