Pushing RTTs to post-MVP

I would like to propose pushing RTT value types and all instructions that use them to post-MVP. Binaryen and V8 support RTT-less versions of all allocation and casting instructions that use static type index immediates instead of dynamic RTT values and j2wasm and Dart have both found these static versions of the instructions to be sufficient for their needs in the presence of explicit supertype declarations, as used in #243. In particular, Dart has implemented its own userspace type information that it uses to implement language-level casts, but that custom type information does not depend on RTT values.

We have also found that Binaryen can optimize modules that use RTT-less instructions to be about 3% faster than the same modules with RTTs because the reduced dynamism allows Binaryen to prove that more casts are unnecessary. This better optimizability will become increasingly important as engines do more inlining and follow-on optimizations themselves.

As a concrete example, consider an inlined method call that downcasts its this parameter. With RTTs, showing that the cast always succeeds requires proving that the this value has always been allocated with the same RTT used in the cast, whereas an RTT-less cast can be shown to always succeed just by looking at the static type of the this argument and seeing that it is a static subtype of the parameter's type.

If we find that we need to add RTT values back into the language as part of a post-MVP generics proposal or for some other reason, we can easily add RTT-using versions of the allocation and cast instructions back as well. That we have already been supporting both kinds of instruction in Binaryen and V8 demonstrates that the maintenance overhead of that duplication is not a problem.

I'd advise against that, for a number of reasons:

Without RTTs, which can be imported, there would be no way to customise the host-side appearance of Wasm GC objects (e.g., JS prototypes). We'd become dependent on type imports again, which I believe we'd all like to avoid for now. Furthermore, it's unlikely that the (ab)use of type imports for that purpose can be made to work for that without complicating the type system (AFAICS, it would require introducing a third type relation besides type equivalence and subtyping).
Making RTTs explicit is in line with Wasm's defining character as a low-level "assembly" language. It makes data and operations explicit that have a machine-level cost (typically involves at least an allocation). Furthermore, it allows expressing reuse of the result of that operation (e.g., by assigning it to a local or global), without assuming additional engine optimisations. It also allows distinguishing between types that require RTTs and those that don't. IOW, they create a more accurate, low-level cost model.
RTTs will be needed with generics. If we were to introduce them later, we'd need to duplicate all relevant GC instructions at that point (and presumably future ones as well).

We have also found that Binaryen can optimize modules that use RTT-less instructions to be about 3% faster than the same modules with RTTs because the reduced dynamism allows Binaryen to prove that more casts are unnecessary.

Ah, if that is your main motivation: I am pretty sure that this is no longer the case after #243. Because that change removes rtt.sub and makes subtyping part of the type definition itself, putting static and dynamic types into full sync. That is, there will always be a 1-1 correspondence between an RTT and a static type. RTTs are known to be equivalent precisely when their static types are. (Even though later, with generics, that static type may depend on a type parameter, and both RTTs and static types can be parameterised.)

Does that make sense?

Yes, thanks, your arguments make sense, but I still think removing RTTs is the best call for the MVP.

Without RTTs, which can be imported, there would be no way to customise the host-side appearance of Wasm GC objects (e.g., JS prototypes). We'd become dependent on type imports again...

This is making a lot of assumptions about what the JS API will look like and what capabilities it will have, when my understanding is that we haven't really focused on the JS API design so far. It seems backwards to put as cross-cutting a feature as RTTs into core Wasm in service of the JS spec layered on top of core Wasm, although I'd be happy to discuss this further once we have a better idea of what we want from the JS API.

Making RTTs explicit is in line with Wasm's defining character as a low-level "assembly" language... they create a more accurate, low-level cost model.

Maybe, but we don't have a cost model in any technical sense and I would hope that it's clear enough that struct.new and friends already require allocations, so I don't see this as sufficient reason to keep explicit RTTs.

RTTs will be needed with generics. If we were to introduce them later, we'd need to duplicate all relevant GC instructions at that point (and presumably future ones as well).

Understood, and I think that will be a very reasonable cost to pay for removing complexity from the MVP, given that it is a cost multiple implementations have been paying without issue.

I am pretty sure that this is no longer the case after #243. Because that change removes rtt.sub and makes subtyping part of the type definition itself, putting static and dynamic types into full sync. That is, there will always be a 1-1 correspondence between an RTT and a static type.

Thanks, I had missed that we had already made RTTs and the static types completely equivalent for the MVP. This further convinces me that removing RTTs from the MVP is the best course of action.

This is making a lot of assumptions about what the JS API will look like and what capabilities it will have, when my understanding is that we haven't really focused on the JS API design so far.

FWIW, when this was discussed previously, the suggested design involved attaching JS property information to the RTT.

Due to canonicalisation, it would be somewhat tricky to associate the same information directly with the static type declarations if RTTs were made implicit - maybe object creation would have to be annotated through some custom section in order to to attach JS-specific information to the implicit RTT?

RTTs will be needed with generics. If we were to introduce them later, we'd need to duplicate all relevant GC instructions at that point (and presumably future ones as well).

There are only 10 instructions (including experimental ones) that require an rtt input:

the 6 allocation instructions struct.new, struct.new_default, array.new, array.new_default, array.init, array.init_from_data,
and the 4 test instructions ref.test, ref.cast, br_on_cast and br_on_cast_fail.

I do not think it is a big burden to duplicate 10 or a few more instructions later, especially given that the rtt-less instructions are simply syntactic sugar of the explicit-rtt ones, therefore easy to implement. Note that the V8 implementation already provides both alternatives.

Furthermore, it allows expressing reuse of the result of that operation (e.g., by assigning it to a local or global), without assuming additional engine optimisations.

I would agree that local assignment could perform better in absence of certain optimizations, but

these optimizations are already done (at least in V8) as a special case of load elimination, and
it is in my opinion unlikely to be used in practice, as a producer would need to detect multiple allocations in a function that use the same rtt, introduce additional locals for them etc.

When it comes to globals, I do not think reusing them is easier than rtts: Since canonical rtts are global to the module, they need to be loaded from the instance just as globals, therefore the same optimizations are required to eliminate multiple loads thereof. In fact, mutable-global loads are harder to eliminate than (immutable) rtt.canon loads.

@rossberg

@rossberg

#243. Because that change removes rtt.sub and makes subtyping part of the type definition itself, putting static and dynamic types into full sync. That is, there will always be a 1-1 correspondence between an RTT and a static type. RTTs are known to be equivalent precisely when their static types are.

I am not sure I follow this. To check my understanding, for the relevant optimization here, it is not enough to compare RTTs - we also need to know which RTT an object has based on its type, statically. Here is a concrete example:

(func $method.of.X (param $this (ref $Object))
  (ref.cast $X ;; $X is some subtype of the generic $Object
    (local.get $this)

;; =>
;; Inlining or some other VM or toolchain inference leads us to see that the
;; static type of $this is in fact $X, and not the more generic $Object.
;; =>

(func $method.of.X (param $this (ref $X)) ;; the type here changed
  (ref.cast $X
    (local.get $this)

;; =>
;; The relevant optimization: A ref.cast of something of type $X to $X is a no-op.
;; =>

(func $method.of.X (param $this (ref $X))
  (local.get $this) ;; the cast has been removed

Does #243 give us what we need for the last step here?

@kripken

@kripken Yes, because after #243 there is exactly one possible RTT value for each type, namely the value of rtt.canon, which is the same every time it is executed for a particular type.

@tlively

@tlively

I see, thanks. But do we expect that to stay the same in the future? If we extend wasm later in a way that makes it possible to construct an item with an RTTs other than rtt.canon of that item's type then we'd be losing the possibility to optimize in the way I sketched.

Yes, that's right. And to prevent optimization regressions for modules that don't need the post-MVP extensions that use RTTs, we would want to add the RTT-free instructions at that point anyway.

Add GC discussion about moving RTTs to post-MVP

Add GC discussion about moving RTTs to post-MVP (#974)

I added this to the agenda for our next meeting so we can discuss it in real time if necessary.

I hadn't seen this thread so I missed chiming in earlier, but I agree with Andreas and Conrad that it seems like this will be quite limiting for potential JS API designs.

FWIW, when this was discussed previously, the suggested design involved attaching JS property information to the RTT.

Due to canonicalisation, it would be somewhat tricky to associate the same information directly with the static type declarations if RTTs were made implicit - maybe object creation would have to be annotated through some custom section in order to to attach JS-specific information to the implicit RTT?

I agree that it would be tricky to do this kind of approach with a custom section. This has been brought up before in discussions, and there was also some concerns raised that this kind of use of a custom section would be new for Wasm, in that the behavior isn't really optional (e.g., for tooling or optimization) but would be required to be interpreted for the JS part of the program to work.

Another thing I wonder about is how casting at boundaries between Wasm and host programs will work without instructions like rtt.canon. Right now, especially with the removal of rtt.sub, there is a straightforward way to handle ToWebAssemblyValue(v, (ref $t)) where $t is a struct type and v a host value. It could just evaluate the cast (ref.cast v (rtt.canon $t)). Specifying this without RTT instructions seems trickier, unless the plan is that RTTs would still exist in the semantics somehow but not be exposed as values.

@takikawa

@takikawa If a custom section has issues, could this be done on the JS API side? Without RTTs we basically need the JS side to declare a mapping of wasm type index to JS info, which there are a few ways to bikeshed. Another benefit of using the JS API is that this is really a JS-specific issue, so leaving it out of the wasm file and core wasm spec seems to make sense.

The only maybe odd aspect that I can think of to such a mapping is handling of wasm canonicalization (which is I guess the issue you refer to before @conrad-watt ?). Say if type indexes i and j have different JS info associated with them, but the wasm ends up canonicalizing them, then we'd need to error. But that seems reasonable and unavoidable? If the JS wants to actually differentiate those two types then that is an ABI contract between wasm and JS, and the wasm should have reflected that (by putting the types in the same rec group where they will not be canonicalized).

If the goal of the GC MVP's JS API is to allow JS glue code to present wasm GC objects to JS code with nice idiomatic property names and methods on the prototype chain without an extra indirection through a JS wrapper object, I don't see a way to achieve this if the core wasm GC MVP doesn't provide the ability to supply something generative (i.e., not globally canonicalized) directly to struct.new. This generativity (of types or rtts, either way could work, iiuc) gives the JS API an address in the store with which to associate a fresh JS prototype object with -- just like how (for better or worse) WebAssembly.Function objects are associated with funcaddrs in the store.

You could of course imagine that each unified structural type is given an address in the store and so each Realm ends up associating one global prototype for each such unified structural type. However, I think this would, in the limit, lead to unrelated libraries accidentally clobbering each others' prototype chains when they happened to use the same structural type. (In particular, to avoid this problem, I've been assuming that wasm GC objects created with empty or canonical rtts would have a null prototype.)

The "directly to struct.new" part is critical, I believe, since this is the point where the shape/map/hidden-class is stored into the GC object header, thereby associating the particular prototype object with the particular allocation. Any later point (say, ToJSValue(), when a wasm GC object flows out to JS) is too late (which is why I don't see a pure-JS-API solution working -- I suppose you could call out to JS in place of struct.new, but I assume this is too slow).

The three possible sources of generativity I'm aware of are: type imports (allowing the JS API to generate fresh types imported by the module), rtts (allowing either wasm or the JS API to generate fresh rtts), private type definitions (but I believe the expected impl requires a layer of indirection so this wouldn't satisfy the base perf requirements). Thus, if we punt both rtts and type imports out of the MVP, I'm not aware of a viable solution that wouldn't cause problems down the line (i.e., not be a hack we'd regret later). Although of course I might be missing something. (Personally, I'm rooting for the (possibly stripped-down) type imports direction.)

If the goal of the GC MVP's JS API is to allow JS glue code to present wasm GC objects to JS code with nice idiomatic property names and methods on the prototype chain without an extra indirection through a JS wrapper object...

Whether we want this and how much complexity we are willing to add to the core Wasm part of the MVP to get it is definitely something we should discuss more.

My personal take is that this kind of rich interop would be a nice-to-have, but it's not worth complicating the core spec to get it. There are also potential benefits to not having such rich interop. Namely, if the JS API encourages the use of exported and imported getters and setters of more primitive data (e.g. raw numbers, opaque references, and arrays thereof) over the direct exposure of complex internal data types, that would give Binaryen more room to prove that certain fields are unused or always constant and remove them. If the JS API instead encourages exposing complex internal data types directly, Binaryen will need to be told how they will be used via some other more complicated means to perform those optimizations.

unless engines implicitly pass RTTs around almost everywhere, which is highly undesirable... because that would introduce inherent complexity and substantial hidden runtime costs (including non-trivial allocations at generic call sites).

I think this is the key point and I'd like to understand it more. It has previously come up that explicit RTTs could allow compilers to better express how the RTTs would be loaded and register allocated, but the feedback from implementers was that this wouldn't really be useful since engines do their own register allocation from scratch.

I know that in the future when we have type parameters to functions, the idea is that explicit RTTs corresponding to those type parameters would be passed as arguments. With implicit RTTs, the engine would add those arguments implicitly based on the type parameters to the function. For generic type imports the engine would similarly generate implicit RTT imports based on the static type imports.

Are there any other situations in which you expect the engine would have to implicitly pass RTTs around if we got rid of explicit RTTs?

It's not obvious to me that this implicit passing is undesirable. I expect that in the vast majority of cases explicit RTTs would be used to express the exact same passing schemes that the engine would have generated anyway. I don't see any intrinsic value in duplicating the static immediate/parameter/import as an additional value-typed immediate/parameter/import, since the former should make it clear that something is being passed. Is there more to this that I'm not seeing?

With implicit RTTs, the engine would add those arguments implicitly based on the type parameters to the function.

Right. The problem is that an engine generally needs to have a fixed calling convention. That implies that by default, the engine would have to pass RTTs to all generic functions, regardless of whether they need them or not. That would be terrible! An engine could possibly optimise those away in some limited cases where a function doesn't escape, but in general it is almost impossible to avoid that overhead.

And this overhead isn't just passing RTTs. Worse, it involves allocating and constructing RTTs at call sites with somewhat unbounded cost! For example, when a generic function calls another generic function with a type involving its own type parameters, then it cannot be pre-allocated:

(type $t (typeparam $X $Y) ...)

(func $f (typeparam $A) ...)

(func $g (typeparam $B)
  (call $f (type $t (typeparam $X) (typeparam $X)) ...)
)

Here, the call to $f requires an RTT for A that corresponds to $t<$B, B>, which will likely involve non-trivial computation and allocation that it must perform on every call. Modulo inline caches it could introduce. Both is very much against Wasm's spirit of "predictable cost".

Now, unlike an engine, a producer will have much more systematic knowledge about where casts are introduced and hence RTTs are needed in its compilation scheme. In fact, some producers may have no need for casts at all once we provide generics! So if RTTs are properly manifest, producers can systematically control and minimise their construction, caching, and passing for their use cases. Also, they can afford much more effort for expensive global analysis to optimise them.

This separation making the operational manifestation of runtime types explicit is pretty much standard, one way or the other, in principled designs for low-level languages combining runtime typing with generics [e.g., 1, 2, 3, 4]. The primary counter example would be the CIL (counting that as low-level), whose reified generics are notorious for the engine complexity they induce and probably inspired some of the cited work to do better.

Ah I didn't think about generic functions calling each other. That does make the possible overhead seem more "real".

Returning to the question of whether we could remove RTTs for now and add them in back later, could we make typeparam a separate per-function index space, so that future with-RTT instructions could (optionally?) reference this index space while the hypothetical-MVP "without-RTT" instructions would be prevented from doing so, and therefore still guaranteed to reference real type declarations?

If explicit RTTs are required for generics, then we should introduce generics and explicit RTTs at the same time. Both now, or both later.

(Yes, adding (ref.cast (rtt $T) ...) after (ref.cast <$T> ...) will lead to duplication of sorts, but the existing implementations in Binaryen and V8 demonstrate that this is acceptable. In fact, if we resolve #274 by allowing concrete/custom types on the generic as/is/br_on instructions, there'll be no duplication to speak of.)

@askeksa-google

After the latest discussion, it's clear that it will make sense to have RTTs in their current form once we introduce type imports/exports, generics, or potentially other post-MVP extensions. However, it remains the case that RTTs would have no benefit in the MVP, and in fact would come with a 6% code size penalty (as measured on Dart by @askeksa-google). This code size penalty would not go away or pay for itself in the future since some toolchains such as J2CL will never use post-MVP features that would benefit from having RTTs.

Removing RTTs from the MVP and introducing them later also does not have any cost beyond maintaining RTT-free and RTT-using versions of cast and allocation instructions. This cost is trivial not only in implementations but also in the spec, where the RTT-free instructions would be defined in terms of their RTT-using variants composed with rtt.canon. Notably, this composition of instructions is precisely what gc-MVP toolchains would emit for every cast or allocation if we did mandate the use of RTTs in the MVP.

Although I would welcome new information to the contrary, removing RTTs from the MVP would decrease MVP spec complexity without affecting future spec complexity, would have small but significant code size benefits, and would be in line with our philosophy of incremental development, especially since we have no clear timeline for working on generics or type imports.

Unless anyone can identify any concrete problems with removing RTTs from the MVP and adding them back in later, I would like to wrap up this discussion no later than our meeting on May 31.

@conrad-watt

Returning to the question of whether we could remove RTTs for now and add them in back later, could we make typeparam a separate per-function index space, so that future with-RTT instructions could (optionally?) reference this index space while the hypothetical-MVP "without-RTT" instructions would be prevented from doing so, and therefore still guaranteed to reference real type declarations?

I think this would work and I would be fine with that, but it might be even simpler to allow RTT-free instructions to work even with type parameters, where the implicit rtt.canon might require the engine to allocate. That would maintain the invariant that (rtt-free-inst $T) == (with-rtt-inst $T (rtt.canon $T)). I am assuming that (rtt.canon $T) works even when $T is a type parameter since those RTTs need to come from somewhere initially, but maybe that's a bad assumption, in which case I agree that (rtt-free-inst $T) should be disallowed by construction as @conrad-watt suggests.

After recent discussions, it is clear that the most active stakeholders agree on the technical details around this decision but will not be able to unanimously agree on a path forward. To settle this issue one way or the other and move on to other things, I've scheduled a consensus poll on this for our meeting on Tuesday.

The proposed question to poll for is "should we defer RTTs from the MVP and reintroduce them alongside generics, type imports, or another post-MVP proposal?" If the poll does not demonstrate consensus in favor of deferring RTTs, then we will keep them as currently proposed in the MVP.

After a good discussion this morning, we successfully polled for consensus to defer RTTs from the MVP with the precise text given above. I'll leave this issue open until we can update the proposal docs to reflect this change.

We landed #306, so closing this.

[Wasm-GC] Remove RTT support

Navigation Menu

Repository navigation

Pushing RTTs to post-MVP #275

21 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Pushing RTTs to post-MVP #275

Description

Activity

rossberg commented on Feb 14, 2022

tlively commented on Feb 14, 2022

conrad-watt commented on Feb 14, 2022

manoskouk commented on Feb 14, 2022

kripken commented on Feb 14, 2022

tlively commented on Feb 14, 2022

kripken commented on Feb 14, 2022

tlively commented on Feb 14, 2022

tlively commented on Feb 17, 2022

takikawa commented on Feb 17, 2022

kripken commented on Feb 17, 2022

lukewagner commented on Feb 17, 2022

tlively commented on Feb 17, 2022

21 remaining items

tlively commented on May 2, 2022

rossberg commented on May 3, 2022

conrad-watt commented on May 3, 2022

jakobkummerow commented on May 3, 2022

tlively commented on May 16, 2022

tlively commented on May 17, 2022

tlively commented on May 27, 2022

tlively commented on May 31, 2022

tlively commented on Jul 21, 2022

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions