> the nice design
But integers are read 7 bits at a time. Wouldn't it be much easier to use 8 bits?
But integers are read 7 bits at a time. Wouldn't it be much easier to use 8 bits?
"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.
(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.)
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
E.g. the only bytes that have bit 7 cleared are the single-byte 7-bit ASCII character codes.
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
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/
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 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.