bijou64: A Canonical, High‑Performance Varint Encoding for Sync Protocols
Benchmark bijou64 against LEB128 in your sync protocol and migrate if performance gains justify.
Benchmark bijou64 against LEB128 in your sync protocol and migrate if performance gains justify.
Summary
bijou64 is a new variable‑length integer encoding designed for the Subduction CRDT sync protocol, aiming to provide a canonical representation that eliminates multiple encodings per value. The format uses the first byte as a tag: values 0–247 encode directly, while 248–255 indicate how many subsequent bytes represent the number, allowing the decoder to know the length in O(1). Offsets are applied to the data bytes so that each integer has a unique encoding, removing the need for runtime canonicality checks that LEB128 requires. Benchmarks on Apple M2 Pro and AMD Zen 5 show bijou64 decodes 2–10× faster than LEB128, especially for larger numbers where LEB128 must scan continuation bits. Encoding speed is slightly slower for very small numbers but comparable for typical workloads. Wire‑size is within a few percent of LEB128 across realistic distributions, and the format supports up to 64‑bit values. The design also ensures that the decoder can preallocate memory based on the tag, improving cache locality and branch prediction. bijou64’s canonical nature makes it suitable for protocols where security and deterministic encoding are critical.
Key changes
- First byte 0–247 encodes directly; 248–255 tag indicates number of following bytes
- Offsets applied to data bytes ensure a unique encoding per integer
- Decoder knows length in O(1), eliminating continuation‑bit scanning
- Decoding 2–10× faster than LEB128, especially for large numbers
- Encoding slightly slower for very small numbers but comparable overall
- Wire‑size within a few percent of LEB128 across realistic distributions
- Supports up to 64‑bit values with a single encoding per value
- Canonical encoding removes the need for runtime canonicality checks