6 ms·

As we get closer to having a WebAssembly demo ready in multiple browsers, the group has added a small little website on GitHub [0] that should provide a better

• KMag 11y ago
  About the binary encoding... It's a bit easy to armchair these things, and it's too late for WebAsm now... but if you're on the V8 team, you have access to Google's PrefixVarint implementation (originally by Doug Rhode, IIRC from my time as a Google engineer). A 128-bit prefix varint is exactly as big as an LEB128 int in all cases, but is dramatically faster to decode and encode. It's closely related to the encoding used by UTF-8. Doug benchmarked PrefixVarints and found both Protocol Buffer encoding and Protocol Buffer decoding would be significantly faster if they had thought of using a UTF-8-like encoding. LEB128 requires a mask operation and a branch operation on every single byte, maybe skipping the final byte, so 127 mask operations and 127 branches. Using 32-bit or 64-bit native loads gets tricky, and I suspect all of the bit twiddling necessary makes it slower than the naive byte-at-a-time mask-and-branch. 7 bits -> 0xxxxxxx 14 bits -> 1xxxxxxx 0xxxxxxx ... 35 bits -> 1xxxxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 0xxxxxxx ... 128 bits -> 1xxxxxxx 1xxxxxxx 1xxxxxxx ... xxxxxxxx Prefix varints just shift that unary encoding to the front, so you have at most 2 single-byte switch statements, for less branch misprediction, and for larger sizes it's trivial make use of the processor's native 32-bit and 64-bit load instructions (assuming a processor that supports unaligned loads). 7 bits -> 0xxxxxxx 14 bits -> 10xxxxxx xxxxxxxx ... 35 bits -> 11110xxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx ... 128 bits -> 11111111 11111111 xxxxxxxx xxxxxxxx ... xxxxxxxx There's literally no advantage to LEB128, other than more people have heard about it. A PrefixVarInt 128 is literally always the same number of bytes, it just puts the length-encoding bits all together so you can more easily branch on them, and doesn't make them get in the way of native loads for your data bits. Also, zigzag encoding and decoding is faster than sign extension, for variable-length integers. Protocol Buffers got that part right. Note that for security reasons, if there are no non-canonical representations, there can't be security bugs due to developers forgetting to check non-canonical representations. For this reason, you may want to use a bijective base 256[0] encoding, so that there aren't multiple encodings for a single integer. In the UTF-8 world, there have been several security issues due to UTF-8 decoders not properly checking for non-canonical encodings and programmers doing slightly silly checks against constant byte arrays. A bijective base 256 saves you less than half a percent in space usage, but the cost is only one subtraction at encoding time and one addition at decoding time. [0]https://en.wikipedia.org/wiki/Bijective_numeration https://en.wikipedia.org/wiki/Bijective_numeration
  • s3th 11y ago
    It's not too late! The wasm binary encoding is open to change up until the browsers ship a stable MVP implementation (then the plan is to freeze the encoding indefinitely at version 1). The primary advantage of LEB128 is (as you mentioned) that it's a relatively common encoding. PrefixVarint is not an open source encoding IIUC. We'll do some experiments in terms of speed. If the gains are significant we may be able to adopt something similar (this [0] looks like a related idea). Thanks for the suggestion. [0]: http://www.dlugosz.com/ZIP2/VLI.html http://www.dlugosz.com/ZIP2/VLI.html
    • KMag 11y ago
      PrefixVarint isn't open-source, but the encoding is trivial. PrefixVarints are a folk theorem of Computer Science, (re-)invented in many times and places. I actually coded it up once in Python and once in C before joining Google, and was chatting with an engineer, complaining about the Protocol Buffer varint encoding. The person I was complaining to, said "Yea, Doug Rhode did exactly that, called it PrefixVarint. He benchmarked it much faster."
    • KMag 11y ago
      See my other comments on this thread for a simple implementation of a bijective big-endian prefix varint encoder. You may or may not want a bijective encoding, and probably want little-endian. I'm just used to writing big-endian encoders (for lexographical sorting reasons), so that was faster for me to whip up a demonstration of a bijective encoder. A real implementation would use a switch statement instead of a loop. One might use a lookup table or a few instructions of inline assembly to calculate the number of leading ones in the first byte, and switch on that.
  • haberman 11y ago
    I have been advocating for the PrefixVarint encoding you mention for a while. One thing I'd mention though: as you've specified it here, it puts the continuation bits as the high bits of the first byte. I think it may be better to put them in the lower bits of that byte instead. It would allow for a simple loop-based implementation of the encoder/decoder (LEB128 also allows this). With continuation bits in the high bits of the first byte, you pretty much have to unroll everything. You have to give each length its own individual code-path, with hard-coded constants for the shifts and continuation bits. The downside is one extra shift of latency in the one-byte case, imposed on all encoders/decoders. Unrolling is probably a good idea for optimization anyway, but it seems better to standardize on something that at least allows a simple implementation. Here is some sample code for a loop-based implementation that uses low bits for continuation bits: // Little-endian only. Untested. char *encode(char *p, uint64 val) { int len = 1; uint64 encoded = val << 1; uint64 max = 1 << 7; while (val > max) { if (max == 1ULL << 63) { // Special case so 64 bits fits in 9 bytes. *p++ = 0xff; memcpy(p, &val, 8); return p + 8; } encoded = (encoded << 1) | 1; max <<= 7; len++; } memcpy(p, &encoded, len); return p + len; } const char *decode(const char *p, uint64* val) { if (*p == 0xff) { // 9-byte special case memcpy(val, p + 1, 8); return p + 9; } // Can optimize with something like // int len = __builtin_ctz(!*p); unsigned char b = *p; int len = 1; while (b & 1) { len++; b >>= 1; } *val = 0; memcpy(val, p, len); *val >>= len; return p + len; }