#variable-length #u64 #quickcheck #order #round


Varint encoding that preserves memcmp order

1 unstable release

0.1.0 Aug 29, 2020

MIT license

112 lines


A Better Varint encoding that preserves memcmp order.

Based on "A Better Varint..." slide from D. Richard Hipp's talk:

We use variable length integers.

[snip: how traditional VLQ works]

This was a mistake. If you need variable length integers, don't do them this way. Instead, do them like this where the first byte tells you the magnitude of the integer.

This is very important for efficiency in parsing. The other thing is that you can actually compare two integers using memcmp without having to decode them.


A Better Varint

Based on D. Richard Hipp.'s "A Better Varint" idea. See https://youtu.be/gpxnbly9bz4?t=2386.

Slightly changed so leading 0xff is reserved for larger integers.

No runtime deps