4 ms·

This is pretty great! I highly recommend building a parser for Wasm, it shows off the nice design that it can be compiled in a streaming fashion and other nice

This is pretty great! I highly recommend building a parser for Wasm, it shows off the nice design that it can be compiled in a streaming fashion and other nice properties. I built a small parser for a wasm runtime I was going to hack at, although that lost steam and now I just contribute to wasmtime, but it was a great way to learn. The source if you’re interested in C++20 and coroutines: https://github.com/rockwotj/wasmcc https://github.com/rockwotj/wasmcc

amelius 3y ago
> the nice design But integers are read 7 bits at a time. Wouldn't it be much easier to use 8 bits?
- teraflop 3y ago
  If you use all 8 bits of a byte for data, you need a separate way to store the length, or you need to make everything fixed-width which wastes space. "Varints" or variable-length integers, with 7 bits of data and 1 continuation bit per byte, are used in a fairly wide variety of formats (e.g. Protobuf, SQLite and Lucene). They're compact when most of your integers are small, while still being quite simple and fast to encode/decode. Faster alternatives tend to be more complicated, and more compact alternatives tend to be slower. See https://en.wikipedia.org/wiki/Variable-length_quantity https://en.wikipedia.org/wiki/Variable-length_quantity
  - joquarky 3y ago
    I wonder if something resembling this could have been better than how IPv6 attempts to solve the address space problem.
    - p1mrx 3y ago
      Variable-length IP addresses were considered at the time: https://datatracker.ietf.org/doc/html/rfc1752#section-10.2 https://datatracker.ietf.org/doc/html/rfc1752#section-10.2
- svat 3y ago
  This is basically the design of UTF-8 or varint encoding. The integer's representation is read one byte (8 bits) at a time, which can then be interpreted by looking at the first bit which says whether the integer is "done" or more bytes need to be read. (If we were using all 8 bits for the representation and an additional leading bit for whether it continues, we'd end up having to read 9 bits or something, which is awkward and not aligned with what the machine actually supports reading.)
  - flohofwoe 3y ago
    UTF-8 is a bit more complex than that. The first byte in a sequence basically tells you how many bytes are following by looking at the top-most bits. 0xxxxxxx => no followup bytes, just the 7-bit ASCII code 110xxxxx => 1 byte follows 1110xxxx => 2 bytes follow 11110xxx => 3 bytes follow The followup bytes then always have the pattern 10xxxxxx. E.g. the only bytes that have bit 7 cleared are the single-byte 7-bit ASCII character codes.
    - Mindless2112 3y ago
      A UTF-8-like encoding would probably be better than VLQ encoding because the length is known up-front, which allows for the decoder to have fewer branches. Something like [1] or alternatively [2]. See also [3]. [1] https://en.wikipedia.org/wiki/UTF-8#FSS-UTF https://en.wikipedia.org/wiki/UTF-8#FSS-UTF [2] https://sqlite.org/src4/doc/trunk/www/varint.wiki https://sqlite.org/src4/doc/trunk/www/varint.wiki [3] https://news.ycombinator.com/item?id=11263378 https://news.ycombinator.com/item?id=11263378
- rockwotj 3y ago
  It is a balance between simplicity, speed and size. They choose size, honesty leb128 isn’t *too* complex (you can see an implementation in my repo I pointed too). But yes they don’t take all the simplicity tradeoffs.
  - willtemperley 3y ago
    Protobuf seems to use a very similar encoding.
- xjay 3y ago
  In this case, a 64-bit little-endian unsigned integer Ought to be enough for anyone. [1] Using variable-length "micro-compression" schemes like these merges concerns [2], add processing overhead, and lose out on the simplicity and efficiency of working on the data directly in memory, maybe even reusing the same memory/cache line after checking identifiers, etc. The 7-bit VLQ scheme [3] makes sense for MIDI sequences (1980s), as they were stored on MIDI hardware with limited memory, and had basic processing needs. [1] https://quoteinvestigator.com/2011/09/08/640k-enough/ https://quoteinvestigator.com/2011/09/08/640k-enough/ [2] https://en.wikipedia.org/wiki/Separation_of_concerns https://en.wikipedia.org/wiki/Separation_of_concerns [3] https://en.wikipedia.org/wiki/Variable-length_quantity https://en.wikipedia.org/wiki/Variable-length_quantity
  - monocasa 3y ago
    Eh, I don't think the .wasm file is intended to be an in memory format. For an on wire/storage format, variable length integers like protobuf uses is a perfectly valid choice.
    - dataangel 3y ago
      It's actually the protobuf design mistake that most adversely affects decoding performance. The original creator who went on to make Cap'N Proto makes the excellent point that it's better to leave the extra bytes and then just slap a compressor that only works on runs of 0 bytes on top. Faster for the same savings. There are also newer schemes from Daniel Lemire and others more amenable to SIMD decoding.
      - monocasa 3y ago
        Sure, but that decoding speed penalty doesn't stop protobuf (and similar encodings using leb128 like thrift) from being some of the most used binary encodings on the planet, even in relatively low latency spaces. Additionally, Cap'N Proto RLE encodes the bytestream, which is pretty similar to the overhead of LEB128 integers. And on top of all of that, .wasm isn't intended to be an IPC format, so the fact that it's choices are typical of that space (despite not being leading edge) reflect very well for the space it's intended to be in.
- kevingadd 3y ago
  It would be. The use of varints in wasm complicates encoding and decoding and introduces ambiguity into the format for cases like v128 constants (which despite technically being 128-bit integers, are not embedded using leb128.) It also makes it harder to write a single-pass compiler. It also isn't much of a wire size improvement, since the overall format design assumes you will compress it using brotli (or gzip, I guess) - there are lots of opportunities to make the format smaller or arrange it in a way that makes it more compressible, and the decision was made not to do those things since brotli is really good at compressing data. I think the people who took control of the binary format just really liked varints for some reason, so we ended up stuck with them. It's at least not particularly harmful, it's just a small waste of everyone's time. Thankfully, my understanding is that in practice most modules will only get decoded once or twice before the compiled code is cached by your browser.

amelius 3y ago

> the nice design But integers are read 7 bits at a time. Wouldn't it be much easier to use 8 bits?

teraflop 3y ago
If you use all 8 bits of a byte for data, you need a separate way to store the length, or you need to make everything fixed-width which wastes space. "Varints" or variable-length integers, with 7 bits of data and 1 continuation bit per byte, are used in a fairly wide variety of formats (e.g. Protobuf, SQLite and Lucene). They're compact when most of your integers are small, while still being quite simple and fast to encode/decode. Faster alternatives tend to be more complicated, and more compact alternatives tend to be slower. See https://en.wikipedia.org/wiki/Variable-length_quantity https://en.wikipedia.org/wiki/Variable-length_quantity
- joquarky 3y ago
  I wonder if something resembling this could have been better than how IPv6 attempts to solve the address space problem.
  - p1mrx 3y ago
    Variable-length IP addresses were considered at the time: https://datatracker.ietf.org/doc/html/rfc1752#section-10.2 https://datatracker.ietf.org/doc/html/rfc1752#section-10.2
svat 3y ago
This is basically the design of UTF-8 or varint encoding. The integer's representation is read one byte (8 bits) at a time, which can then be interpreted by looking at the first bit which says whether the integer is "done" or more bytes need to be read. (If we were using all 8 bits for the representation and an additional leading bit for whether it continues, we'd end up having to read 9 bits or something, which is awkward and not aligned with what the machine actually supports reading.)
- flohofwoe 3y ago
  UTF-8 is a bit more complex than that. The first byte in a sequence basically tells you how many bytes are following by looking at the top-most bits. 0xxxxxxx => no followup bytes, just the 7-bit ASCII code 110xxxxx => 1 byte follows 1110xxxx => 2 bytes follow 11110xxx => 3 bytes follow The followup bytes then always have the pattern 10xxxxxx. E.g. the only bytes that have bit 7 cleared are the single-byte 7-bit ASCII character codes.
  - Mindless2112 3y ago
    A UTF-8-like encoding would probably be better than VLQ encoding because the length is known up-front, which allows for the decoder to have fewer branches. Something like [1] or alternatively [2]. See also [3]. [1] https://en.wikipedia.org/wiki/UTF-8#FSS-UTF https://en.wikipedia.org/wiki/UTF-8#FSS-UTF [2] https://sqlite.org/src4/doc/trunk/www/varint.wiki https://sqlite.org/src4/doc/trunk/www/varint.wiki [3] https://news.ycombinator.com/item?id=11263378 https://news.ycombinator.com/item?id=11263378
rockwotj 3y ago
It is a balance between simplicity, speed and size. They choose size, honesty leb128 isn’t *too* complex (you can see an implementation in my repo I pointed too). But yes they don’t take all the simplicity tradeoffs.
- willtemperley 3y ago
  Protobuf seems to use a very similar encoding.
xjay 3y ago
In this case, a 64-bit little-endian unsigned integer Ought to be enough for anyone. [1] Using variable-length "micro-compression" schemes like these merges concerns [2], add processing overhead, and lose out on the simplicity and efficiency of working on the data directly in memory, maybe even reusing the same memory/cache line after checking identifiers, etc. The 7-bit VLQ scheme [3] makes sense for MIDI sequences (1980s), as they were stored on MIDI hardware with limited memory, and had basic processing needs. [1] https://quoteinvestigator.com/2011/09/08/640k-enough/ https://quoteinvestigator.com/2011/09/08/640k-enough/ [2] https://en.wikipedia.org/wiki/Separation_of_concerns https://en.wikipedia.org/wiki/Separation_of_concerns [3] https://en.wikipedia.org/wiki/Variable-length_quantity https://en.wikipedia.org/wiki/Variable-length_quantity
- monocasa 3y ago
  Eh, I don't think the .wasm file is intended to be an in memory format. For an on wire/storage format, variable length integers like protobuf uses is a perfectly valid choice.
  - dataangel 3y ago
    It's actually the protobuf design mistake that most adversely affects decoding performance. The original creator who went on to make Cap'N Proto makes the excellent point that it's better to leave the extra bytes and then just slap a compressor that only works on runs of 0 bytes on top. Faster for the same savings. There are also newer schemes from Daniel Lemire and others more amenable to SIMD decoding.
    - monocasa 3y ago
      Sure, but that decoding speed penalty doesn't stop protobuf (and similar encodings using leb128 like thrift) from being some of the most used binary encodings on the planet, even in relatively low latency spaces. Additionally, Cap'N Proto RLE encodes the bytestream, which is pretty similar to the overhead of LEB128 integers. And on top of all of that, .wasm isn't intended to be an IPC format, so the fact that it's choices are typical of that space (despite not being leading edge) reflect very well for the space it's intended to be in.
kevingadd 3y ago
It would be. The use of varints in wasm complicates encoding and decoding and introduces ambiguity into the format for cases like v128 constants (which despite technically being 128-bit integers, are not embedded using leb128.) It also makes it harder to write a single-pass compiler. It also isn't much of a wire size improvement, since the overall format design assumes you will compress it using brotli (or gzip, I guess) - there are lots of opportunities to make the format smaller or arrange it in a way that makes it more compressible, and the decision was made not to do those things since brotli is really good at compressing data. I think the people who took control of the binary format just really liked varints for some reason, so we ended up stuck with them. It's at least not particularly harmful, it's just a small waste of everyone's time. Thankfully, my understanding is that in practice most modules will only get decoded once or twice before the compiled code is cached by your browser.