Design: Add length field for the init_expr

[yurydelendik]

init_expr is defined as "normal encoding of the expression followed by the end opcode as a delimiter." It will be hard for naive scanner/parser to skip the this field without fully parsing the expression -- we cannot just scan till the end code since a constant might have this byte/code. Will it be better to add the length field similar to the function body?

[jfbastien]

That sounds fine and useful. It's getting close to being a function though...

[mbebenita]

Any reason for not just making it a function?

[lukewagner]

How important is it to be able to blindly skip over init_exprs given that (1) they are already contained by sections or function bodies that themselves have byte lengths and can be skipped, (2) the language of init_expr is extremely simple?

[binji]

Well, an extremely naive parser couldn't read all the globals, for example, without parsing init_exprs. But I agree with @lukewagner that this is pretty simple. And the init_exprs are at their longest 10 bytes (f64.const <value> end). Is the concern that we may relax this restriction? I suppose if we allow i32.add then the length could become unbounded.

[jfbastien]

I suppose if we allow i32.add then the length could become unbounded.

And then we allow unreachable code, whose shadow we then maybe have to validate (or maybe not), and then we've got functions :grin:

[binji]

I'm not falling for the slippery-slope argument. :)
And anyway, what naive parser are we talking about that can't parse functions?

[titzer]

BTW it doesn't have to parse functions (and I don't think we should extend
the init expr language to be functions), it just has to be able to skip
over all the allowed instructions in the init expr subset. That's 5
bytecodes now and hopefully won't grow very fast.

On Tue, Nov 1, 2016 at 10:51 PM, Ben Smith [email protected] wrote:

I'm not falling for the slippery-slope argument. :)
And anyway, what naive parser are we talking about that can't parse
functions?

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
https://github.com/WebAssembly/design/issues/857#issuecomment-257709837,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ALnq1Mz8nvAbVNG3RUvmRS9KxQ9zhR95ks5q57R-gaJpZM4KmYXT
.

[yurydelendik]

And anyway, what naive parser are we talking about that can't parse functions?

A naive parser in this case will be something that will not attempt to create any data structures during non-validating scan, e.g. for indexing the global or element section items or to retrieve byte offset of an item in these sections by its index.

[ghost]

I see some utility in having the size too, for the reason @yurydelendik noted, to allow skipping the init_expr without knowledge of the encoding (which might change in future). In particular I see a need to be able to build a directory quickly, so that tools can randomly seek the information needed to present an incremental part of the code, and the code that builds this directory might want to be very simple and more robust to changes in the spec.

[kmiller68]

Whatever happened with this? FWIW, I agree that init_expr should have a length. If for no other reason than it will make future changes much simpler and it has very low cost now. Is there any opposition to adding length to init_expr? I agree with @titzer, I'm not convinced that we need to allow arbitrary functions in the MVP (or ever). However, we already stated some interest in allowing addition in init_expr, which would imply that the init_expr can have arbitrary length. I think we should separate the discussion about making init_expr a full function from the length problem.

[rossberg]

Hm, it seems to me that a length prefix is only justified if we assume that _huge_ expressions will eventually be so common that it's worth parallelising their _decoding_ in implementations. I find that highly unlikely, even when we generalise them to allow almost all the language.

[ghost]

@rossberg-chromium Is the decoder guaranteed to catch a use of an unexpected instruction in the init expression? If not then a size might give a more predictable validation failure.

But even if the decoder can see that the init expression is not as expected it might make wasm more robust if the decoder could at least continue to decode other parts of the section, so that a single use of one unexpected instruction in an init expression does not make the entire section unreadable. While this might not help a runtime, it might help tools and error reporting.

A size is not the only solution, and the instruction table might have been another.

[jfbastien]

Isn't the binary size cost exactly one byte more per init_expr if we have size as an LEB128 as well as end, assuming all init_expr are small for now? And then it makes it easy to extend what they can do in the future, if we want, to be parsed the exact same as functions.

[kmiller68]

@jfbastien If we wanted init_expr to be decode the same as a function with a reduced instruction set we would actually need two bytes. One for the length and one for the local count, which in the MVP we would presumably assert is 0.

Regardless, as @jfbastien said, it's only two bytes per global and I expect that the number of globals will be relatively small. Do we have any evidence otherwise? If it's the case that there are only a few globals, it seems the consistency gain / complexity reduction is worth more than the cost of two bytes per global.

[binji]

init_exprs are also used for data segment and element segment offsets, not just global initial values.

[ghost]

@kmiller68 Remove locals from wasm, and the local count is not needed. Even just adding pick would avoid the need for locals unless these expressions allowed loops, and even then loops may well need to be re-thought to not require locals. The end code can also be removed, it's odd there on it's own without also having a branch target in scope and as it stands the end does not unwind the stack so is not compatible with pick usage. If people can not agree on adding a size now then lets just leave the decision for a later pre-MVP version, and try to settle some other key matters.

[pipcet]

I think this isn't a major issue, but I would prefer init_exprs to have a length field, and it would make some of my code (a standalone wasm rewriter that shortens LEB128 integers but is otherwise pass-through) a little simpler.

[ghost]

@jfbastien Great a thumbs down, but can you justify it in technical terms? I don't yet know if wasm without locals is a better place, but have good reason to suspect it will be compelling, it certainly simplifies decoding to validated SSA, and it certainly helps the reader, and I see good reason why it will help a simple compiler, but I will get the remaining answers. But do you know? If not then why give it a thumbs down?

[jfbastien]

@wllang I simply disagree with removing locals without data backing up your assertions.

[ghost]

@jfbastien So you don't know if a decoder would be simpler and faster without local variables? Surely some people here who have implemented decoders would know, and couldn't you confirm with someone on your team. After confirming these advantages, it would appear that the only remaining question is the encoding efficiency, and why hasn't your team or other teams got these results on what is a clear performance improvement and simplification? Who are you expecting to do the design work and when did you expect to reach a MVP, or are you going to push a MVP out with such low hanging fruit unexplored?

[jfbastien]

@wllang the burden is on you to do these things. I'll be delighted if you confirm such opportunities. Please move this discussion to another github issue, it is not relevant to init_expr.

[lukewagner]

So getting back to this: I think the root concern here is that these initializer expressions will eventually be generalized to essentially full-powered function bodies or at least fully generalized expressions and then we'll want to do things like parallel compilation if there are many of them.

However, that is necessarily not the case. First, initializer expressions have no valid execution environment (they are used to establish the initial execution environment) so they can't run anything beyond trivial pure operations. Furthermore, initializer expressions are not intended to be used to implement C/C++ global variable initializer expressions: those need to go in linear memory and thus any runtime initialization would be executed by the start function along with all the other complex things that need to happen before main.

Really, initializer expressions are just an encoding of a non-recursive variant. The entire reason for having initializer expressions at all is to be able to place data and elem segments at either constant or instantiation-time-computed offsets. In the case of the latter, any general computation (like mallocing a region of linear memory) needed to compute the offset is performed by the caller (before instantiation) in the caller's execution environment.

The only reason I can think of to generalize what we have now, ever so slightly, is if a code generator wanted to emit multiple data segments that all shared the same imported base address plus varying constant offsets. (This could realistically arise as an optimization when there were large contiguous blocks of zeroes in what would otherwise be a big single data segment.) To optimize this case, we could generalize initializer expressions to allow the additional fixed form:

(i32.add (get_global $import) (i32.const offset))

(not even allowing nested i32.add so that all the internal initializer-expression variants would stay fixed-size, non-recursive structures) But I think that's it.

So given all that, I think adding a length is overkill, now and in the future. Sound reasonable @yurydelendik @jfbastien @kmiller68 ?

[RyanLamansky]

As someone who recently wrote a WASM parser, I found init_expr to be intimidating... initially. After that momentary panic, it was clear that with only 5 allowed opcodes (and simple opcodes at that), it really wasn't a big deal.

Every added opcode increases difficulty of use as an init_expr parser has to become that much closer to a fully-featured function body parser. Adding anything that requires an extra end is a cliff, as it requires a primitive parser to not only know how to skip opcodes, it also needs to keep track of block depth.

I'm okay with leaving things as they are, but we can make things easier for beginners by making available a series of WASM samples that allow them to set milestones and build out their parser incrementally. I had to start with AngryBots13.wasm because it was the only one I could find...

[rossberg]

@Kardax, the easiest source of samples with good coverage probably is the test suite in the spec repo (currently at https://github.com/WebAssembly/spec/tree/master/interpreter/test). You can convert these .wast files into .wasm using either the spec interpreter or a separate tool like wabt.

[kmiller68]

@lukewagner, I think I have been convinced that the length isn't necessary (although I still think it would be a good safety net). So, I'm willing to withdraw my objections.

[ghost]

If all that is needed and will even be needed is a global constant reference plus a constant offset then I suggest just encoding those and forget about the init_exp. Could even the offset be handled in a community developed decoder, and what about the global constant too, so might this just need a constant value? Why provision for features in the wasm file format that could be handled efficiently in a community developed decoder anyway which would be far more future proof and flexible.

[yurydelendik]

To optimize this case, we could generalize initializer expressions to allow the additional fixed form

So given all that, I think adding a length is overkill, now and in the future.

I somewhat agree that for very limited expression format we don't need length and considering it is listed as a language type in BinaryEncoding it will/might require some special parser (different from function body one). I'm closing the issue. Perhaps having example/description/format of the possible values in the BinaryEncoding's init_expr description will avoid future concerns.

[turbolent]

Too bad the length was not added in the end. Even though the opcodes are limited, it still requires a simple binary parser to parse them properly, even if all it wants to do is analyze the structure of the binary and skip over the expression.