Bijou64: A variable-length integer encoding • Hacker News Board

Re: Bijou64: A variable-length integer encoding

#91

Post by nwmcsween » Sat, May 30, 2026, 7:54 PM UTC

kstenerud wrote: post #37

nine_k wrote: post #36

Earlier quoted context omitted.

I think these are different use cases. If you talk about SIMD, you talk about the CPU and efficient processing of large numbers of integers. I think that when a solution like this crops up, it's about storage or transmission, and dense packing at the cost of non-uniformity. It's more like time-series databases pack numbers by delta encoding.

The thing is, most real-world numbers will fit within 1-3 bytes (even at 7 bits per byte), so ultradense packing doesn't actually buy much outside of benchmarks. I spent WAYYYYYYYY too much time exploring this...

This is like string functions, there are some variants with just crazy SIMD when the mean string length is ~14-20 bytes

Re: Bijou64: A variable-length integer encoding

#92

Post by sparkie » Sat, May 30, 2026, 8:30 PM UTC

billpg wrote: post #26

I forget where I encountered it, but I've seen similar encodings that eliminated the possibility of many possible encodings for the same number by making the length part of the value. Values 0-127 are a single byte, but if that first byte has the continuation bit set, not only does that indicate the next byte has 7 more bits to contribute, it also moves the base up to the next window. 10000000 00000000 is the only wa…

Bitcoin has a variable width encoding (`CompactSize`), but it doesn't prevent overlong encodings - however there are various canonicalization rules in the Bitcoin protocol to require minimal encoding.

Re: Bijou64: A variable-length integer encoding

#93

Post by pta2002 » Sun, May 31, 2026, 12:05 PM UTC

chrismorgan wrote: post #81

pta2002 wrote: post #28

Earlier quoted context omitted.

I believe that's how the varint encoding used by protobut works: https://protobuf.dev/programming-guides/encoding/#varints

> Drop continuation bits. Clearly not.

Indeed, I was misinterpreting the OP's suggestion. Can't edit the comment anymore, unfortunately.