Best data structure for `Map<u8,usize>`?

help
1

I'm looking to store some kind of map between u8 and usize. I'd like it to be as fast as possible, as I'll be going through a lot of these. The obvious option is [usize; 256], using usuze::MAX to represent unset values, but that does waste a lot of memory, which could lead to low memory locality, which wouldn't be ideal. I've also considered Vec<(u8, usize)> which may save space, but is slow to access and by using heap allocation gives up memory locality entirely. A hash map without actually hashing seems like it might be ideal, especially since most commonly I'll have b'a' to b'z' is my values, so a map size of 32 would give no collisions.

Does a better data structure exist for me than just an array?

2

Can you guarantee it is always <= 64 ?

If so, I'd go with something like this:

#[align(64)]
pub struct Foo {
  keys: [u8; 64];
  data: [usize; 64];
}

so all of keys fits in a single cache line. You can use SIMD instructions to figure out if the key is contained; and, if so, make one memory lookup to data

3

Could you point me at the simd code to use? I've never used simd before actually.

4

I never implemented this myself. The technique is described in swisstable / hashbrown.

5

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.