Arbitrary size bit vectors with SIMD


#1

Hi all,

I have a question about bitvectors with SIMD (question at the end). I like to have a type where i can store bits. I like to specify how many bits. I don’t really care about the details of implementation if this is a vector or array or how the bits are stored. I do care about performance and leveraging SIMD. Also without runtime feature detection that needs to branch on every operation. The type should have arithmetic operations like +, -. /, * but also bit operations like AND, OR, shift LEFT/RIGHT, NOT, XOR and so on. Also signed (two-complement) and unsigned should be supported. When for example + is used on 2 bitvectors of size 64 bits the results should be a 65 size bitvector to store the additional bit which can occur. So i like some type safety to prevent overflows. It should also be smart enough that if i trim back to 64 bits after that it doesn’t need to expand to 65 bits first but just let it overflow at 64 bits. I choose 64 bits in my example but this can by any size.

There are a bunch of crates and webpages i found on both SIMD and also on bitvectors.

SIMD:

4 links removed (i can only post 2 links in a post because i’m a new user)

Bitvectors:

8 links removed (i can only post 2 links in a post because i’m a new user)

How far is the state of rust, rustc and the crates? It this possible yet? Should something like https://github.com/rust-lang/rust/issues/44580 be implemented first to get automatic type of result of + operation? Maybe there are other RFC’s, features, crates not in place yet as well?

Does anyone know what exactly would be needed and how far the progress is to make the thing possible i described in the first paragraph?

See https://bpaste.net/show/235f5ab7800a for the missing links

Thanks