Type annotations on new instructions

So far, Wasm has been consciously designed such that the type of every instruction is self-contained. That is, every operand's type is either fully known (possibly with the help of a type immediate) or fully polymorphic.

With instructions like call_ref or func.bind this design choice starts to become a nuisance, and will be even more so under future extensions like those of the GC proposal. Redundant type annotations can also increase the cost of validation, since more types needs to be compared against each other (although it's not clear whether this extra cost is relevant, given the relative infrequency of most affected instructions).

Currently, the proposal omits the type on call_ref and the source type on func.bind. It requires constype immediates on null-related instructions, though, to be consistent with the instructions in the reference types proposal. Should more annotations be added for consistency and ease of type checking, or more removed for convenience/compactness?

More examples of instructions that could or could not have redundant type annotations:

input type annotation of block
input type annotation of if
output type annotation of loop
input type annotation of try
input and output type annotations of let

There will likely me many more such instructions in future proposals. For example, input and output type annotations for many of the instructions for stack primitives are redundant.

@RossTate

@RossTate, yeah, but as mentioned elsewhere, block typing has sailed long ago, and changing it now would be rather tough. In any case, it's outside the scope of this proposal.

That discussion indicated that the rationale behind the decision was that eliminating type annotations would complicate the pseudo-code interpreter by requiring end to check if the construct had an associated out-annotation and, if so, to restrict the outgoing types to that annotation and check them for compatibility.

That decision was also made at a time where only one block-like structure did not need an out-annotation, making the complexity seem unnecessary. But let will be another example where such an out-annotation is unnecessary, and there will likely be more examples down the line. let also introduces new complexities to end, such as cleaning up the local-variable stack, meaning that end will become more complicated anyways. So the landscape is changing in a way that suggests the decision should be reevaluated, and this proposal is the first sign of that change.

These type annotations increase binary size and mean more work for validation, but I don't see any clear benefits. In a fast single-pass compiler, you probably want to do validation together with code generation anyway, meaning the information in these immediates is available anyway. For a slower, optimizing compiler used for tier-up, this information could be cached or should be cheap enough to re-compute. For an interpreter working directly on the wire-bytes, it could in principle be helpful to have this type information right there, at least for some operations. But the Wasm binary format is already hard to interpret without additional sidetable information, and what you really want in an interpreter is often platform-specific, like real offsets in the case of Wasm GC object access. So this information needs to be put in a sidetable or engine-specific internal bytecode anyway. So I really can't imagine any situation where these immediates would be useful enough to pay for the increased size in the transport format, especially since this is a price paid by all users independently of the respective engine even profiting from it.

For those like me who are curious about the history, this pull request appears to be where the blocks got types. It seems like the primary concern at the time was knowing how many stack items are retained by a branch ("arity").

@taralx

Thanks, @taralx! Historical context is always super useful, and expect everyone involved in that conversation appreciates being saved from repeating the conversation 😄 Looking through it, it seems the option I am suggesting was never discussed: every block-like construct (i.e. has an end) specifies an arity to know how many values to leave on the stack (I suspect 0 is extremely common), and if the block-like construct provides a branch target (e.g. block, if, and loop) then specify a "label" type for the target (e.g. [i32, i32]). Now, given what already exists, it might just be easier to say that block-like constructs providing a branch target use block types, and those not providing a branch target (like let) use an arity. But we should try to reduce how much we rely on the compression granted by using type indices—as WebAssembly's type system grows there will be fewer and fewer identical block types within a module.

To clarify, let is consistent with other block constructs and binds a label -- as mentioned elsewhere, treating all block constructs uniformly as branch targets was the group's decision long ago.

That's implicit in the typing rule as stated in the proposal, though it may not be super-obvious. I added an explicit note (and fixed a bug on the way :) ).

Yes, I understand let currently binds a label solely due to a decision made long ago when all block constructs naturally bound a label. Above I gave reasons to revisit that decision. Could you link to the relevant discussion behind that decision so that we can see if/how its rationale carries over to let and other non-control-flow constructs (in addition to the one linked above, which I've already tried to incorporate into the discussion here)?

Unfortunately, there are no notes of that, as far as I'm aware; it was early times.

FWIW, I argued against that choice at the time, and explicitly raised the question whether this should then apply to all block constructs that we may add in the future. The resolution was yes, because otherwise the primary motivation (simplicity of decoders and validators, avoiding a separate stack for tracking labels) would have been moot.

That doesn't mean that we can't revisit, but none of the technical arguments to do so are specific to let. So such a discussion would probably deserve a more general topic and any resolution should consistently apply to all relevant block instructions. I would hence prefer to separate this particular discussion from the current proposal. Focus helps progress.

@tebbi

+1 to not requiring redundant type immediates for new instructions, in the interest of saving module size. Obviously, instructions that create new values must know a type for them; whereas instructions that consume stack values don't need to encode the expected type of these values.

From an engine implementation point of view, redundant type immediates only make us do more work at validation time, because equivalence of actual stack value type and expected type (per immediate) must be checked. Having the immediates provides no (performance or simplicity or safety) benefit. (Direct wire-byte interpreters might be an exception to this "no benefits" statement, but (1) as @tebbi explains above even that is unclear, and (2) it's also unclear whether that's the implementation strategy that Wasm should optimize for -- wouldn't most users of most engines expect to get the speed that comes from compilation to machine code?)

From a language point of view, I can see that such additional "consistency checks" might be helpful for a human-written language, but they seem significantly less useful for a compilation target.

(For background, I'm mostly looking at this from the GC proposal's perspective, but it's a design decision that should ideally be consistent. For example, struct.get could skip its type parameter and only have a field index, the semantics being "retrieve the n-th field from whatever struct is currently on top of the value stack; fail to validate if that struct doesn't have enough fields". In this proposal, ref.as_non_null could easily be polymorphic and simply return a non-null reference for whatever nullable reference type it found on the stack.)

One argument in favor of out annotations on block-like structures is that in a situation where the block leaves multiple values on the stack on the way out, a streaming compiler can pre-allocate space for those values to go into (they won't all fit in registers). As it is, our baseline compiler does not make use of that information and instead ends up emitting a fair amount of data shuffling code in some cases. I probably believe that it would be possible to get rid of that shuffling code if we can know something about how much space will be required along the exit edge from the block.

I don't know that this is a particularly strong argument for us, because it's a baseline compiler - some inefficiencies are to be expected - and because I've not done the detailed analysis, nor am I likely to. I guess there could also be streaming compilers that are not quite so simplistic and would benefit more from information up-front.

@rossberg

Hmm, interesting idea. But I suspect you'll have to have a bunch of shuffling code with that anyways. That is, even if you preallocate the space, you don't know which instruction outputs end up going into which spots until you reach the end of the block, so either you'll have to add shuffling code or you'll have to backpatch the code, which is probably what you would have done anyways 😕

But now that I understand where @rossberg meant to go with this post (sorry for the confusion, though the opening arguments do apply just as easily to block-like instructions), and that the pull requests for the relevant changes are in progress, it's probably best to let him close the issue when those are done and I'll open up another one to discuss the topic of annotations for blocks elsewhere.

it's probably best to let him close the issue when those are done and I'll open up another one to discuss the topic of annotations for blocks elsewhere.

Sgtm, I'd suggest the design repo, since this could be a separate proposal.

Thanks for the suggestion! I was wondering that exact question 😄

Done: WebAssembly/design#1352

@titzer

@titzer:

a layer 1 compression algorithm that is aware of Wasm's type system can and should completely outclass GP compression.

I encourage you to develop and/or present such an algorithm. On its own, "we shouldn't do anything now because I'm sure someone else will invent a rounder wheel in the future, which will solve all our problems" is not a convincing argument.

I suspect that the type annotations necessary for locals are also a big chunk of binary size

In the Sheets module measured above, 200 KB are used for defining 61K locals across 28K functions, accounting for 2.1% of the uncompressed code section size.

I don't think the discussion has turned up anything that has fundamentally changed the calculus, or any opinions, yet.

I had thought that the notable lack of motivating examples benefiting from annotations might have been a fundamental change to the decision calculus. If it would help move the discussion forward, I can explain why the one example that has been mentioned—Jawa—does not actually need multiple upper bounds on type imports, leaving us with no motivating examples. (The short of it is that, due to the complications caused by multiple inheritance, there's no significant run-time benefit to knowing an object implements an interface, so there's no need to encode subtyping between interfaces when compiling to wasm.)

If anything, it turned up how slippery the slope would be. ;)

Can you explain what you mean by this?

On the larger issue of binary size, my understanding is that j2wasm (and maybe dart2wasm) is using aggressive closed-world AOT optimizations to make performance competitive with j2cl. Is that understanding correct? If it is, such performance optimizations can substantially increase code size, so what happens to binary size (with and without annotations) and performance if instead one optimizes for size rather than performance?

Indeed dart2wasm performs closed-world optimizations, but most of these are ones that reduce code size, e.g. tree shaking, parameter elimination, constant propagation, devirtualization.

Ah, I would have thought it did inlining as well largely due to its symbiotic role with devirtualization (devirtualization provides an inlining opportunity, which moves virtual calls to a more specialized context, which enables more devirtualization).

About the importance of binary size, I look at it like this: if we could easily reduce the size of all images on the Web by 5% then we'd want to do that. Likewise for video, JS, etc. The scale of the Web is so big that even a 5% win on one format matters a lot! Maybe one user can't easily notice it by themselves, but plenty of data shows that even small changes to download size have real-world impacts on average user experience. And 5% less total bandwidth across the entire Web is a significant amount of work and electricity over billions of downloads.

Because of that there are various projects working to shrink images, video, JS etc., both on the spec side and tools side. As wasm rises in popularity its size will matter more and get closer to those. In fact we already do a lot of work for code size on the tools level, in Binaryen and elsewhere - that has been motivated by existing important real-world use cases that care about binary size today.

So even 5% is worth thinking about. Yes, there may be other ways to shrink size (L1 compression), and maybe we'll get to them, but that's uncertain. And, yes, maybe we are 2x larger than JS now, and maybe 5% won't fix that, but it's still 5% better. Whenever we have a good practical way to reduce size that's worth considering. Of course, we need to consider the other side of the tradeoff as well.

@kripken

@kripken Thanks for that, I think that's well said.

So even 5% is worth thinking about. Yes, there may be other ways to shrink size (L1 compression), and maybe we'll get to them, but that's uncertain. And, yes, maybe we are 2x larger than JS now, and maybe 5% won't fix that, but it's still 5% better. Whenever we have a good practical way to reduce size that's worth considering. Of course, we need to consider the other side of the tradeoff as well.

I just want to clarify my comments regarding the '5% vs 2x' point. I definitely agree that improvements are worth considering even if they don't solve the larger issue completely.

I would just like to better understand why wasm-GC binary size is 2x JS binary size. This would help me to evaluate the relative importance of a 5% improvement vs any spec concerns. Are the wasm-GC toolchains doing more inlining? Are call sequences or prologues larger? Is there a runtime library required with wasm that JS doesn't need? Is the data/elem section significant?

For example, if there's low hanging fruit elsewhere that doesn't have spec concerns then that seems like the first step before dropping annotations. If the other required fixes are likely to be difficult too, then it may make sense to start with dropping annotations.

But without more context on the '2x' number, it's hard for me to weigh the improvement against theoretical spec concerns.

@eqrion

@eqrion:

I would just like to better understand why wasm-GC binary size is 2x JS binary size.

Because JS is a high-level language and Wasm isn't. Respective size comparisons are mostly apples to oranges. Native code also tends to be much larger than JS source code, probably by more than 2x.

@eqrion

@eqrion:

I would just like to better understand why wasm-GC binary size is 2x JS binary size.

Because JS is a high-level language and Wasm isn't. Respective size comparisons are mostly apples to oranges. Native code also tends to be much larger than JS source code, probably by more than 2x.

I'm aware of the difference between JS and Wasm. All of the items I listed as possible reasons for a size difference would be due to Wasm being a lower-level language. What I'm asking for is quantification to help understand what, if anything, can be done about the difference.

One thing that might help move the conversation forward is if we could get an example of a type system extension for which the existence of unannotated struct.get and struct.set (even in the presence of additional annotated versions) would be a problem. In other words, it would be nice to have an example where the decision procedure for determining whether an annotation is required is greater than constant time (amortized).

Lacking such an example, it has been hard to convince ourselves that the risk of encountering such a situation is anything but vanishingly small and that the expected benefit of keeping annotations could outweigh the benefit of reducing code size.

Note that for the example with multiple supertypes on type imports, I believe an efficient and sufficient decision procedure for requiring annotations would be to require them when the type of the stack is a subtype of a type import, which would be amortized constant time after preprocessing the types.

@eqrion

@eqrion

I would just like to better understand why wasm-GC binary size is 2x JS binary size.

Things are still evolving so any specific measurement may end up changing. But I think these are some of the main factors, which include things you mentioned:

Inlining. While engines can inline at runtime, I don't think we can assume they'll do as well as JS (JS is higher level so there is more to work with). Also runtime inlining takes time to warm up and may differ between VMs. So we inline more than JS toolchains do, and this helps benchmarks.
Library support. Atm we're shipping Java library code for strings, for example - the Strings proposal should remove some of that, but not all. JS has a great standard library that helps lots of things. Sometimes we can call out to JS (e.g. to do Math.log, rather than bundle a log impl) but that has runtime costs.
Repeating code patterns like "if null, throw an exception". In JS the code can rely on the VM, but in wasm we'd get a nonrecoverable trap - but J2Wasm needs the ability to catch some of these. Lots of other patterns exist, like x.push in JS is just a few bytes but in wasm it's going to need to handle reallocating the backing array etc.
Lots of small stuff like a.x in minified JS is a read from a field in 3 bytes (in wasm that takes more with or without annotations), JS not having type annotations in general (regardless of the current topic, the annotations we definitely will keep are a significant source of entropy), JS having "overloading" ("+" works on numbers or strings), etc. etc.

Those are sorted in my current best guess at relative importance from the most to the least, but again, that's imprecise and may change.

I'm not sure about the data/elem sections. J2Wasm doesn't emit them, but it does emit equivalent stuff in arrays and structs. It's hard to measure that since it's interleaved in the code.

@rossberg

Native code also tends to be much larger than JS source code, probably by more than 2x.

That reminds me, I actually measured JS compared to native code over a decade ago 😄 yes, as you said, JS is surprisingly compact - and it's only gotten smaller since then!

Yes, this is somewhat expected. But the bottom line though is that this matters. If wasm is (say) 2x larger than JS then that will prevent some people from being able to use it. The smaller it is, the more people can use it, and the better it will work for those that do. I wouldn't go as far as to say that "if we make wasm 5% smaller it will be 5% more impactful", but there is a positive connection there.

Adding a note here that this was discussed in the GC subgroup meeting earlier this week (PR for notes here). The high order bit is that the poll of the room showed that the consensus is to retain type annotations on new instructions. Continuing the discussion for next steps here, some questions:

Is the consensus in the meeting sufficient to move forward?
If so, what should the next steps be for the OP of this issue w.r.t. call_ref, func.bind?
Other thoughts from people who didn't attend the meeting?

@rossberg

Let's move forward with keeping the existing annotations and adding annotations to call_ref and friends as well. I don't see a need to hold a further vote. @rossberg, can you prepare a spec PR for that? We'll work on updating V8 and Binaryen, too.

@tlively

@tlively, done: #76.

Closing via #76.

Navigation Menu

Repository navigation

Type annotations on new instructions #27

71 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Type annotations on new instructions #27

Description

Activity

RossTate commented on May 27, 2020

rossberg commented on May 28, 2020

RossTate commented on May 28, 2020

tebbi commented on May 29, 2020

taralx commented on May 30, 2020

RossTate commented on May 31, 2020

rossberg commented on Jun 2, 2020

RossTate commented on Jun 2, 2020

rossberg commented on Jun 2, 2020

jakobkummerow commented on Jun 5, 2020

lars-t-hansen commented on Jun 9, 2020

RossTate commented on Jun 10, 2020

binji commented on Jun 10, 2020

RossTate commented on Jun 10, 2020

RossTate commented on Jun 11, 2020

71 remaining items

jakobkummerow commented on Aug 10, 2022

RossTate commented on Aug 10, 2022

askeksa-google commented on Aug 11, 2022

RossTate commented on Aug 11, 2022

kripken commented on Aug 11, 2022

eqrion commented on Aug 11, 2022

rossberg commented on Aug 11, 2022

eqrion commented on Aug 11, 2022

tlively commented on Aug 11, 2022

kripken commented on Aug 12, 2022

dtig commented on Aug 25, 2022

tlively commented on Aug 25, 2022

rossberg commented on Aug 25, 2022

rossberg commented on Aug 25, 2022

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions