[HN Gopher] Engineering a fixed-width bit-packed integer vector ...
       ___________________________________________________________________
        
       Engineering a fixed-width bit-packed integer vector in Rust
        
       Author : lukefleed
       Score  : 35 points
       Date   : 2025-09-24 15:17 UTC (7 hours ago)
        
 (HTM) web link (lukefleed.xyz)
 (TXT) w3m dump (lukefleed.xyz)
        
       | pjsg wrote:
       | 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.
        
       | Const-me wrote:
       | 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.
        
         | Phemist wrote:
         | I am handling a lot of vectors of size 6 or less with integers
         | of values lower than 500.000. I am packing individual vectors
         | in a u128, which comes down to 6*19 + a 3 bit length field =
         | 117 bits with 11 bit left to spare.
         | 
         | I chose u128 instead of an array of [u64;2] due to the boundary
         | crossing issue that I saw would happen, which I could avoid
         | using u128.
         | 
         | I am not very familiar with these specific bit manipulation
         | instruction sets, so would you know if there is something
         | similar that works on u128 instead of just u32/u64?
        
       ___________________________________________________________________
       (page generated 2025-09-24 23:00 UTC)