3 ms·

I've never heard of Typical but the fact they didn't repeat protobuf's sin regarding varint encoding (or use leb128 encoding...) makes me very interested! Thank

I've never heard of Typical but the fact they didn't repeat protobuf's sin regarding varint encoding (or use leb128 encoding...) makes me very interested! Thank you for sharing, I'm going to have to give it a spin.

zigzag312 1y ago
It looks similar to how vint64 lib encodes varints. Total length of varint can be determined via the first byte alone.
- haberman 1y ago
  I advocated for PrefixVarint (which seems equivalent to vint64 ) for WebAssembly, but it was decided against, in favor of LEB128: https://github.com/WebAssembly/design/issues/601 https://github.com/WebAssembly/design/issues/601 The recent CREL format for ELF also uses the more established LEB128: https://news.ycombinator.com/item?id=41222021 https://news.ycombinator.com/item?id=41222021 At this point I don't feel like I have a clear opinion about whether PrefixVarint is worth it, compared with LEB128.
  - zigzag312 1y ago
    Just remember that XML was more established than JSON for a long time.
  - kannanvijayan 1y ago
    Varint encoding is something I've peeked at in various contexts. My personal bias is towards the prefix-style, as it feels faster to decode and the segregation of the meta-data from the payload data is nice. But, the thing that tends to tip the scales is the fact that in almost all real world cases, small numbers dominate - as the github thread you linked relates in a comment. The LEB128 fast-path is a single conditional with no data-dependencies: if ! (x & 0x80) { x } Modern CPUs will characterize that branch really well and you'll pay almost zero cost for the fastpath which also happens to be the dominant path. It's hard to beat.
    - yencabulator 1y ago
      SQLite format equivalent: if x <= 240 { x } while strictly improving all other aspects (at least IMHO) https://sqlite.org/src4/doc/trunk/www/varint.wiki https://sqlite.org/src4/doc/trunk/www/varint.wiki

zigzag312 1y ago

It looks similar to how vint64 lib encodes varints. Total length of varint can be determined via the first byte alone.

haberman 1y ago
I advocated for PrefixVarint (which seems equivalent to vint64 ) for WebAssembly, but it was decided against, in favor of LEB128: https://github.com/WebAssembly/design/issues/601 https://github.com/WebAssembly/design/issues/601 The recent CREL format for ELF also uses the more established LEB128: https://news.ycombinator.com/item?id=41222021 https://news.ycombinator.com/item?id=41222021 At this point I don't feel like I have a clear opinion about whether PrefixVarint is worth it, compared with LEB128.
- zigzag312 1y ago
  Just remember that XML was more established than JSON for a long time.
- kannanvijayan 1y ago
  Varint encoding is something I've peeked at in various contexts. My personal bias is towards the prefix-style, as it feels faster to decode and the segregation of the meta-data from the payload data is nice. But, the thing that tends to tip the scales is the fact that in almost all real world cases, small numbers dominate - as the github thread you linked relates in a comment. The LEB128 fast-path is a single conditional with no data-dependencies: if ! (x & 0x80) { x } Modern CPUs will characterize that branch really well and you'll pay almost zero cost for the fastpath which also happens to be the dominant path. It's hard to beat.
  - yencabulator 1y ago
    SQLite format equivalent: if x <= 240 { x } while strictly improving all other aspects (at least IMHO) https://sqlite.org/src4/doc/trunk/www/varint.wiki https://sqlite.org/src4/doc/trunk/www/varint.wiki