Pushing RTTs to post-MVP

[tlively]

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.

[rossberg]

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?

[tlively]

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.

[conrad-watt]

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?

[manoskouk]

• 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.

[kripken]

@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?

[tlively]

@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.

[kripken]

@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.

[tlively]

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.