In this talk at time 39:31, D. Richard Hipp (creator of SQLite)
describes the variable-length integer format used for SQLite’s BTrees.
The format is similar to the format currently described in this
repository, with the differences that the content is stored in
big-endian order and that the ninth byte is entirely filled with content
so that the maximum magnitude is exactly 64 bits.
He describes the result as “a mistake” and “a failure”, and advises
designers of any varint system to consider the following criteria:
- The first byte should determine the magnitude of the integer.
- The encoded ordering should be compatible with the logical ordering.
In particular, he suggests the following scheme (here, A0 through A8 are
code units to be decoded):
| A0 |
Value |
| 0–240 |
A0 |
| 241–248 |
240 + 256 × (A0 – 241) + A1 |
| 249 |
2288 + 256 × A1 + A2 |
| 250 |
A1…A3 as a 3-byte big-endian integer |
| 251 |
A1…A4 as a 4-byte big-endian integer |
| 252 |
A1…A5 as a 5-byte big-endian integer |
| 253 |
A1…A6 as a 6-byte big-endian integer |
| 254 |
A1…A7 as a 7-byte big-endian integer |
| 255 |
A1…A8 as a 8-byte big-endian integer |
It appears that this was important enough for SQLite4 to switch its
varint format to exactly what is described above. More details,
including the decoding and encoding algorithms, appear in the SQLite
docs.
The importance of property (1) is recognized by multihash; this
(according to its README) is why a multihash’s size appears at the
beginning of the hash instead of the end. Without this property, you
can’t skip over elements in a stream; you have to read every byte.
The importance of property (2) is recognized by UTF-8, which has the
analogous property: to compare two UTF-8 encoded codepoints, it suffices
to compare their raw code units. This raises the performance ceiling on
hot-loop operations by removing an encode/decode step, which in turn
enables hardware-accelerated implementations, like repz cmpsb on x86.
The format described above is compatible with raw unsigned 8-bit
integers of value at most 240, so preserves the soft-guarantee in the
multihash specification that “you do not need to implement varints until
the standard multihash table has more than 127 functions.”
Note that this scheme encodes unsigned integers of size up to 64 bits.
As discussed in previous issues (#9), this limitation is a good thing.
Thoughts?
(Posting this given that the README reads, “There is time to discuss the
details of this. All multiformats are far from requiring this varint.”)
In this talk at time 39:31, D. Richard Hipp (creator of SQLite)
describes the variable-length integer format used for SQLite’s BTrees.
The format is similar to the format currently described in this
repository, with the differences that the content is stored in
big-endian order and that the ninth byte is entirely filled with content
so that the maximum magnitude is exactly 64 bits.
He describes the result as “a mistake” and “a failure”, and advises
designers of any varint system to consider the following criteria:
In particular, he suggests the following scheme (here, A0 through A8 are
code units to be decoded):
It appears that this was important enough for SQLite4 to switch its
varint format to exactly what is described above. More details,
including the decoding and encoding algorithms, appear in the SQLite
docs.
The importance of property (1) is recognized by multihash; this
(according to its README) is why a multihash’s size appears at the
beginning of the hash instead of the end. Without this property, you
can’t skip over elements in a stream; you have to read every byte.
The importance of property (2) is recognized by UTF-8, which has the
analogous property: to compare two UTF-8 encoded codepoints, it suffices
to compare their raw code units. This raises the performance ceiling on
hot-loop operations by removing an encode/decode step, which in turn
enables hardware-accelerated implementations, like
repz cmpsbon x86.The format described above is compatible with raw unsigned 8-bit
integers of value at most 240, so preserves the soft-guarantee in the
multihash specification that “you do not need to implement varints until
the standard multihash table has more than 127 functions.”
Note that this scheme encodes unsigned integers of size up to 64 bits.
As discussed in previous issues (#9), this limitation is a good thing.
Thoughts?
(Posting this given that the README reads, “There is time to discuss the
details of this. All multiformats are far from requiring this varint.”)