Hacker News Reader

Comment by rockwotj | Hacker News Reader

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

View on HN

> the nice design

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

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

I wonder if something resembling this could have been better than how IPv6 attempts to solve the address space problem.

Variable-length IP addresses were considered at the time: https://datatracker.ietf.org/doc/html/rfc1752#section-10.2

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

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.

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 [2] https://sqlite.org/src4/doc/trunk/www/varint.wiki [3] https://news.ycombinator.com/item?id=11263378

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.

Protobuf seems to use a very similar encoding.

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/

[2] https://en.wikipedia.org/wiki/Separation_of_concerns

[3] https://en.wikipedia.org/wiki/Variable-length_quantity

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.

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.

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.

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.

Reply on news.ycombinator.com