I suspect that this unaligned read apporach doesn't work for a bit length of 59, 61, 62 and 63.
In the case of 63, reading out value at offset 1, requires two reads as it need 1 bit from the first byte, then 56 bits from the next 7 bytes and finally 6 bits from the 9th byte. Nine bytes cannot be loaded in a single u64 load.
That's a good catch!! Thank you, you are right. I (incorrectly) assumed that a single u64 could capture the entire bit_width-value read starting from byte_pos. However, as you said, this assumption breaks for some large bit widths.
The support for BMI1 instruction set extension is almost universal by now. The extension was introduced in AMD Jaguar and Intel Haswell, both launched in 2013 i.e. 12 years ago.
Instead of doing stuff like (word >> bit_offset) & self.mask, in C or C++ I usually write _bextr_u64, or when using modern C# Bmi1.X64.BitFieldExtract. Note however these intrinsics compile into 2 instructions not one, because the CPU instruction takes start/length arguments from lower/higher bytes of a single 16-bit number.
Forgive me - much of the article went over my head so I’m trying to understand: this article is excellently written, but I’m struggling to understand why a `Vec<u8>` wouldn’t have sufficed? And disregarding the first question, is there a way to extend this to floats, for instance if I have a collection of values that I know will never exceed the bounds of +/- 10.0 with 1e-6 precision, can I use this technique for more efficient storage of them?
The other replies nailed it, but I'll add my two cents.
Vec<u8> may be the right call most of the time for most use cases. This library, however, is for when even 8 bits compared to 4 is too much. Another example, if all your values fit in 9 bits, you'd be forced to use Vec<u16> and waste 7 bits for every single number. With this structure, you just use 9 bits. That's almost a 2x space saving. At scale, that makes a difference.
For floats, you'd use fixed-point math, just like the other replies said. Your example of +/- 10.0 with 1e-6 precision would mean multiplying by 1,000,000 and storing the result as a 25-bit signed integer. When you read it back, you just divide. It's a decent saving over a 32-bit float.
For the 8 bits case in the first benchmark, why isn't `Vec<u8>` just as fast as the rest? Is it due to the compiler emitting poorer instructions in that case or doing extra checks the other implementations don't?
It's not about poorer instructions; a get_unchecked on a Vec<u8> is just a single memory access, which is as good as it gets. The difference is likely down to cache locality effects created by the benchmark loop itself.
The benchmark does a million random reads. For the FixedVec implementation with bit_width=8, the underlying storage is a Vec<u64>. This means the data is 8x more compact than the Vec<u8> baseline for the same number of elements.
When the random access indices are generated, they are more likely to fall within the same cache lines for the Vec<u64>-backed structure than for the Vec<u8>. Even though Vec<u8> has a simpler access instruction, it suffers more cache misses across the entire benchmark run.
Maybe this is a thing people commonly have to do, but I have never heard of it and would have wished the article started with an explanation why simply casting the u64 values to a more appropriate type (u16 in this case) is not good enough. 6 of 16 bits would go to waste. It isn't obvious to me why this is considered substantial enough to go through all this trouble.
I've certainly found myself in a situation where a few percent of memory use would be the difference between holding all data in RAM and having to do IO to load it on demand. 6 of 16 bits wasted is enormous then.
For many applications, casting to u16 and wasting 6 bits is perfectly fine. The "trouble" is only worth it when you're operating at a scale where those wasted bits add up to gigabytes.
This is common in fields like bioinformatics, search engine indexing, or implementing other succinct data structures. In these areas, the entire game is about squeezing massive datasets into RAM to avoid slow disk I/O. Wasting 6 out of 16 bits means your memory usage is almost 40% higher than it needs to be. That can be the difference between a server needing 64GB of RAM versus 100GB.
On top of that, as I mentioned in another comment, packing the data more tightly often makes random access faster than a standard Vec, not slower. Better cache locality means the CPU spends less time waiting for data from main memory, and that performance gain often outweighs the tiny cost of the bit-fiddling instructions.
You might be interested in https://github.com/spiraldb/fastlanes. It gives you fast bit packed vectors. It needs padding to 1024 elements though for the performance.
Tangentially (un)related, I recently had to implement a arbitrary bit vector Rust type backed by bytes 0-padded on the MSB side. It also offers an AsRef<[bool]> trait and iterator. Probably going to add serde as a feature and crate it at some point. The hardest part was removing bit(s). push() and append() were cake.
14 comments
[ 2.9 ms ] story [ 35.5 ms ] threadIn the case of 63, reading out value at offset 1, requires two reads as it need 1 bit from the first byte, then 56 bits from the next 7 bytes and finally 6 bits from the 9th byte. Nine bytes cannot be loaded in a single u64 load.
I already patched it, thanks again.
Instead of doing stuff like (word >> bit_offset) & self.mask, in C or C++ I usually write _bextr_u64, or when using modern C# Bmi1.X64.BitFieldExtract. Note however these intrinsics compile into 2 instructions not one, because the CPU instruction takes start/length arguments from lower/higher bytes of a single 16-bit number.
How deliciously rusty
Vec<u8> may be the right call most of the time for most use cases. This library, however, is for when even 8 bits compared to 4 is too much. Another example, if all your values fit in 9 bits, you'd be forced to use Vec<u16> and waste 7 bits for every single number. With this structure, you just use 9 bits. That's almost a 2x space saving. At scale, that makes a difference.
For floats, you'd use fixed-point math, just like the other replies said. Your example of +/- 10.0 with 1e-6 precision would mean multiplying by 1,000,000 and storing the result as a 25-bit signed integer. When you read it back, you just divide. It's a decent saving over a 32-bit float.
The benchmark does a million random reads. For the FixedVec implementation with bit_width=8, the underlying storage is a Vec<u64>. This means the data is 8x more compact than the Vec<u8> baseline for the same number of elements.
When the random access indices are generated, they are more likely to fall within the same cache lines for the Vec<u64>-backed structure than for the Vec<u8>. Even though Vec<u8> has a simpler access instruction, it suffers more cache misses across the entire benchmark run.
This is common in fields like bioinformatics, search engine indexing, or implementing other succinct data structures. In these areas, the entire game is about squeezing massive datasets into RAM to avoid slow disk I/O. Wasting 6 out of 16 bits means your memory usage is almost 40% higher than it needs to be. That can be the difference between a server needing 64GB of RAM versus 100GB.
On top of that, as I mentioned in another comment, packing the data more tightly often makes random access faster than a standard Vec, not slower. Better cache locality means the CPU spends less time waiting for data from main memory, and that performance gain often outweighs the tiny cost of the bit-fiddling instructions.