Yet Another MVP proposal

Update: More fleshed-out proposal in the follow-up issue.

Thinking about a true "MVP" for GC got me to this proposal, inspired by CHERI:

New type pointer, probably 64-bit for wasm32.
Memory instructions (new or augmented) to load/store from pointer instead of i32+memidx.
New instruction allocate that accepts i32 size and returns a new pointer of at least that size.
New instructions pointer.load and pointer.store that only accept pointer, not i32+memidx.
Add/sub instructions (either new or augmented) for moving a pointer around.

Big difference from existing proposals is that it doesn't try to track the full structure of a thing, only which parts of it are pointers.

As constructed above, requires tag bits to track which parts of the structure are pointers, which doesn't sound cheap. One alternative is to fix the region that can store pointers, which has the potential advantage of enabling code to be pointer-size agnostic.

Anyway, this is probably half-baked and doesn't work for some reason, but I figured I'd put it out there. :)

I suspect that if you were to refine this idea, you’d end up with something looking close to this: #78 (comment)

@RossTate

@RossTate Indeed it is similar! There's some things in here that I think are worth considering:

Separate pointer type to allow identification of roots.
Pointers can only come from allocate, host, or reading from another pointer, which means we can be certain about pointer validity.
Dynamic tracking of pointer-ness is much simpler than asking the compiler to pre-declare the pointer region or forcing the use of weird 31-bit numbers.

Also there is nothing stopping pointer values being pointers into the host, e.g. JS heap.

The thing I can’t figure out with your suggestion is how the garbage collector is supposed to walk structures after finding roots.

Let me write down a few more bits of my original idea:

pointer types are larger than 32-bit, because they carry the allocation bounds with them. (Bounds can be compressed, e.g. CHERI Concentrate.)
Every pointer-typed value and every memory location capable of storing a pointer has a validity bit telling us if the pointer is valid.
This is enough for the GC to perform full tracing. Typing gives us roots, pointers have bounds to know where to look, tag bits tell us which parts of memory are inner pointers.
Since pointers have bounds, we can reflect them into JS as e.g. typed arrays.

I then cut out all the extraneous stuff, because you can do all that in a variety of ways. But as you pointed out, that just results in a sketch that is similar to what you posted.

Okay, so it sounds like a structure is an array of cells that are dynamically either pointers or 32-bit integers. On 64-bit machines, each cell would likely be 64 bits in size, taking advantage of room for bit flags to distinguish pointers from integers. On 32-bit machines, each cell would likely be 32 bits in size with a bit set and negative offsets indicating which cells are pointers and which are integers (assuming no concurrent reads and writes). Does that sound like what you're envisioning?

The problem with that 32-bit option is what do you do when someone writes a negative integer into the memory? You're back to basically enshrining i31s, which doesn't mesh well with existing PLs.

Another option I came up with is to not mix pointers and data, a la capnproto. allocate would have to take two parameters, number of pointers and number of data bytes. The nice part there is you don't need to know how big pointers are. The problem is I don't know how one would best represent a pointer to pointer vs a pointer to data. Doing it at the type level gets complicated fast.

(FWIW, in CHERI there is a separate data region that stores the "valid pointer" bits.)

The problem with that 32-bit option is what do you do when someone writes a negative integer into the memory?

By "negative offsets" I meant with respect to the object's layout, not negative integers. But regardless, I can't tell what your proposal has in mind here. How are you mixing integers and pointers?

allocate would have to take two parameters, number of pointers and number of data bytes.

I had originally ruled out this option, but I figured out a way to address the problem I had foreseen. Do as you say, but have the space for pointers grow negatively and the space for integers grow positively. This still supports the common OO pattern where subclasses add more fields—both reference and primitive fields—and yet still need the layout to align with that of superclasses.

Oh, I see. Negative offsets, not negative values.

Hm, that might work?

I think so. It has various pros and cons, though I don't think any of them are particularly subtle at this point. So it seems we're at a good place for others to input their thoughts.

Reading this issue, it seems to have more in common with the existing proposal than with #78: it wants to have memory managed by the engine, whose pointers are always exact, and which can be exchanged with other modules or with JS refs. That is all very different from #78

So it is better to look at how it is different from the main proposal, and I guess it is trying to replace strongly typed GC struct/arrays with generic memory blocks, at the cost of more runtime tracking (bounds checks).. I don't see that as a win. I think if we're going to have GC objects entirely engine managed we might as well statically know the references in them.

If more flexibility is required, you could make the current GC proposal more flexible by making scalars untyped: rather than declaring a struct with certain sized int/float types in them, you'd declare a struct with N exact anyrefs and M bytes of "scalar memory" that can be addressed in whatever way.

@taralx

Good point on the comparison with #78!

I think if we're going to have GC objects entirely engine managed we might as well statically know the references in them.

The current GC proposal does not provide that. An anyref and any reference to a struct can always have more references in the referent than the type indicates.

you'd declare a struct with ... M bytes of "scalar memory" that can be addressed in whatever way

This is more what I had in mind (and I'm guessing @taralx too) for the integer portion. That is, a structure is a chunk of linear memory (at positive offsets) and an array of references (at negative offsets).

I don't see that as a win.

My sense is that the win here lies in its simplicity. It adds just one or two types and doesn't introduce subtyping, and yet it seems flexible enough to express GC languages. It would be relatively easy to implement and ship quickly. And although it's not particularly efficient due to bounds checks (which there are many mitigation techniques for), it would be easy to express in a more advanced GC proposal that is more efficient, so it could serve well as a holdover.

Sorry, I should have said "strongly" rather than "statically". But yes, to your point, some level of dynamic checks are already required.

I do like the elegance of all GC objects being uniformly 2 adjacent arrays (refs + bytes).. but would be good to have an idea what the expected cost would be compared to the current proposal.

Sounds good! More comments and ideas are always welcome.

@jakobkummerow

@jakobkummerow

the mission for Wasm-GC, should we choose to accept it, is to provide a better alternative, and that primarily means better performance according to one or more of the metrics: execution performance, memory consumption, wire bytes size. So adding a bit of complexity to the concept (like fully typing each pointer field in a struct) seems like a good tradeoff if it makes it more likely that the end result will have compelling arguments going for it

Open questions:

Do we have a language where the current proposal is likely to enable better performance than this conceptually simpler approach?
Is adding types the right kind of complexity to add, in order to gain better performance?
are runtime types cheaper than bounds checks or more expensive? Note that, for arrays in the current MVP, we must do bounds-checks, too, when accessing them.

Looking at languages that compile to JavaScript, I think

there is no need for the WASM GC to be significantly faster than the JavaScript GC, but it should not be slower to compile to WASM GC than to JavaScript GC
running a language on WASM enables performance gains and the ability to faithfully represent language semantics which were problematic on JavaScript. The benefits here are in other areas than GC (e.g. exception handling, fine-grained control over low-level operations).
WASM GC must provide a reasonably friendly memory model from the point of view of compiling to it - in particular, we need to be sure that it is possible to compile various languages to use WASM GC. Ideally, without jumping through too many performance-degrading hoops in order to represent their heap model, and without redoing entire compilers. At the same time, the implementation burden on the WASM engines must be reasonable. A WASM GC that is viable in production is a compromise.
where execution performance is the main goal, there is no way around for a language to bring their own GC on WASM linear memory. The requirements of different languages just imply very different GC strategies, so that an optimal GC will look quite different between them. Still, where wire bytes size (-> time to first render on the web for web applications) and interop with JavaScript is a main goal, the built-in WASM GC will win hands-down, despite being slower than the GC strategy usually employed by the language, for purely practical reasons.

The current proposal seems well suited for the assumption that most code is monomorphic and casts are rare (either because types are known statically, or because a single runtime cast guards a nontrivial amount of code, i.e. a statically typed section). In such a scenario, having precise types on fields means that values loaded from fields don't have to be cast or typechecked at all.

There are plenty of examples where this assumption holds (e.g. pretty much all languages that have a notion of "classes" with "methods", so long as they don't have high-frequency calls that interleave methods defined on subtypes and supertypes). There are also plenty of examples where it doesn't hold (e.g. hashing any generic object's contents, as was discussed on the other thread).

(FWIW, in JavaScript we see both: a large part of V8's performance is based on the insight that most code ends up being monomorphic even in such a highly dynamic language; at the same time we've seen plenty of examples where code makes use of the language's flexibility, and any engine feature that assumes otherwise falls flat onto its face.)

There are plenty of examples where this assumption holds (e.g. pretty much all languages that have a notion of "classes" with "methods", so long as they don't have high-frequency calls that interleave methods defined on subtypes and supertypes).

Unfortunately not true for C# due to reified generics, nested structures, interior pointers, and so on. Nested structures and interior pointers are also issues for Go. I don't know enough about Dart these days to assess. Also doesn't work well for Scala due to multiple inheritance of traits, though they at least have the infrastructure for compiling to the JVM that they can possibly fall back on. (I'm assuming your statement was only meant to apply to typed languages.)

So, amongst the top 50 TIOBE languages, this statement really only seems to hold for Java and Kotlin (and possibly Dart).

Hrm. Makes me wonder if the heterogenous version from earlier isn't better, despite the need to maintain word types.

@sabine

@sabine

Open questions:

Do we have a language where the current proposal is likely to enable better performance than this conceptually simpler approach?

Is adding types the right kind of complexity to add, in order to gain better performance?

Are runtime types cheaper than bounds checks or more expensive? Note that, for arrays in the current MVP, we must do bounds-checks, too, when accessing them.

Very good questions and observations IMHO! I think that creating a heap model supporting so many different languages can only end in two ways:

A very complicated proposal with a lot of type information that tries to support as much memory and casting models that languages currently use.
Or a very simple one, only having the type info to support GC and be as dynamic as possible on all other facets.

I think the last point is the reason why compiling high level statically typed languages to dynamic languages like Scheme or JavaScript works so well, while you've to double fold yourself when compiling a "non-OO language" to the JVM or CLR. However, Wasm wants to provide some safety with its memory model. This means we can't be too dynamic.

So the question is if adding more type information to a GC reference, besides its lower level layout, is better or not. I.e. what is the added value of knowing that a reference is of type struct i32 (ref (array i32)) (ref f64) i32 instead of structref 2 8 knowing that it has 2 references and 8 bytes of linear memory? As well for language designers as for engine implementors? That is, I think the common denominator to compile to is reasoning about layout and making bound checks as cheap as possible. (And yes, I'm saying this as a very big proponent of strong type systems 😆)

@taralx

Hrm. Makes me wonder if the heterogenous version from earlier isn't better, despite the need to maintain word types.

Which version are you referring to?

what is the added value of knowing that a reference is of type struct i32 (ref (array i32)) (ref f64) i32 instead of structref 2 8 knowing that it has 2 references and 8 bytes of linear memory?

The value is that whenever we know the static type, we don't need any checks at all to access the struct's fields, and static type knowledge propagates over dependent field loads. So the question becomes: how often do we know the static types of things? And how large or small is the performance penalty when we don't?

When we start with a property loading chain like foo.bar.baz.qux() in the source language, and we have static types for everything, then this can compile to three loads (and a call) without any checks in between. If we lack type information at first, then we'll need a single cast for the foo object, and the rest follows without checks.
Whereas if our type system only knows the number of pointer fields and linear memory bytes, then we need a bounds check before every single load, and presumably a type check before the final call. (In fact, "knowing that a reference is of type structref 2 8" is easier said than done: even if we somehow know that foo has this type, then once we load .bar from it, all we statically know is that bar is a reference. To figure out that bar is of type structref <n> <m>, we have to query it at runtime. If the type system wanted to know that statically, then foo's type would have to be structref (references (to a structref <n> <m>) (to a structref <n'> <m'>)) (8 bytes), which would get pretty close to the fully typed system that this approach wanted to avoid, and would quickly become unwieldy if we wanted to express more than one step of nesting.)

If we think about scenarios where most things are statically typed as anyref and we have to typecheck/cast everything all the time, then just doing bounds checks is faster than RTT-based subtype checks, no doubt about that. If we consider scenarios where most types are statically known, then having all those types allows skipping all checks, which obviously yields higher peak performance.

I suppose in an ideal world, someone would volunteer to prototype both approaches end-to-end, so that we could measure their practical performance on a wide range of real-world applications... any takers? :-)

@sabine

@sabine

Ideally, without jumping through too many performance-degrading hoops in order to represent their heap model, and without redoing entire compilers.

Yes, this is a point I think we're not taking into account enough. Sadly I think "performance thru strong typing at the Wasm level" and "ease of porting as many existing language representation/runtimes as possible" are fundamentally at odds with eachother.

where execution performance is the main goal, there is no way around for a language to bring their own GC on WASM linear memory. The requirements of different languages just imply very different GC strategies, so that an optimal GC will look quite different between them.

There is one point where a dedicated Wasm GC can win over a linear memory GC in performance, and that is the stack. A linear memory GC has to put most of its stack into memory, for it to be scannable, turning many local.get into i32.load, which will generally be a significant slowdown.

But yes, a dedicated Wasm GC shouldn't be slower than the linear memory alternative, which would make it an unattractive target for many languages also.

@aardappel

the common denominator to compile to is reasoning about layout and making bound checks as cheap as possible. (And yes, I'm saying this as a very big proponent of strong type systems laughing)

I like that thought because it goes well with the mental model of a compiler person. It provides some feeling of "being in control of the layout", or maybe the superficial notion of "being able to reuse the layout of the existing compiler to the degree possible". I suspect that this is mostly prejudice on my part, though, and we must identify what the qualitative difference to the "more typed" proposals actually is. (Or whether, in the end, with all the necessary extensions, this proposal turns into more or less the same thing as the existing proposal, but with value types replaced by byte sequences.)

Generally, when looking at linear memory, and the heap, I see only the size in bytes and alignment of values (which compilers traditionally have to deal with). I don't need to see whether there is a float, an unsigned int or a signed int or whatever stored in that linear memory of a heap block.

On the linear memory implementation, WASM gets this right: Only when I read from the memory and the value goes into a register, it needs a type (in order for the engine to know what registers it can reasonably go in! So that makes perfect sense!).
Having "register-typed values" instead of bytes in a model of a heap block seems like an unnecessary hoop for the WASM engine implementers to jump through, and, if that needs to be type-checked, an unnecessary waste of time. As a producer, I know whether I read an (signed or unsigned) int or a float at the time the read happens (because I would also have to know to what register to load that thing).

If I write an int and read a float, that's my own, harmless mistake: WASM doesn't need to prevent me from running that, as there is no security risk associated with that, right? If I'm wrong here, correct me please.

@aardappel

There is one point where a dedicated Wasm GC can win over a linear memory GC in performance, and that is the stack. A linear memory GC has to put most of its stack into memory, for it to be scannable, turning many local.get into i32.load, which will generally be a significant slowdown.

Currently, this is true. If WASM engines implemented support for stack operations (e.g. allow linear memory GCs to walk the local variables of the stack to relocate their references), linear memory GC could be faster.

But... for the sake of reduction of overall complexity, I would rather not want to have to deal with two (or more) GCs. What is really quite interesting is that, with one shared GC, suddenly the complexity cost of interoperating with other garbage collected languages becomes manageable. Yes, you still have to write some wrappers to account for calling conventions and heap representation, but there is no need to carefully place and remove pointers in GC root tables, deal with circular unreachable structures, etc. in addition.

@sabine

@sabine

with one shared GC, suddenly the complexity cost of interoperating with other garbage collected languages becomes manageable. Yes, you still have to write some wrappers to account for calling conventions and heap representation, but there is no need to carefully place and remove pointers in GC root tables, deal with circular unreachable structures, etc.

Then default to copies, not pointers ;) No really, that's what I argue in #78

@jakobkummerow

@jakobkummerow Thanks, I see the qualitative difference between structref (without typed reference arrays) and the current GC MVP proposal now.

Well, let's start with fleshing this proposal out, since it has drawn so much attention. I'll try to put together a more detailed proposal (including considerations like non-reference type imports) in time for the GC meeting in 2 weeks.

@taralx

@taralx

Let me know if you'd like some help.

(moved to new issue since people probably muted this one)

Navigation Menu

Yet Another MVP proposal #94

35 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Yet Another MVP proposal #94

Description

Activity

RossTate commented on May 31, 2020

taralx commented on May 31, 2020

taralx commented on May 31, 2020

RossTate commented on May 31, 2020

taralx commented on May 31, 2020

taralx commented on May 31, 2020

RossTate commented on May 31, 2020

taralx commented on May 31, 2020

taralx commented on May 31, 2020

RossTate commented on May 31, 2020

taralx commented on Jun 1, 2020

RossTate commented on Jun 1, 2020

aardappel commented on Jun 1, 2020

RossTate commented on Jun 1, 2020

aardappel commented on Jun 1, 2020

35 remaining items

timjs commented on Jun 16, 2020

sabine commented on Jul 7, 2020

jakobkummerow commented on Jul 7, 2020

RossTate commented on Jul 8, 2020

taralx commented on Jul 9, 2020

timjs commented on Jul 9, 2020

jakobkummerow commented on Jul 9, 2020

aardappel commented on Jul 9, 2020

sabine commented on Jul 10, 2020

aardappel commented on Jul 10, 2020

sabine commented on Jul 10, 2020

taralx commented on Jul 12, 2020

timjs commented on Jul 13, 2020

taralx commented on Jul 31, 2020

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions