Fast hashmap

Help
1

I need a lightning fast hashmap where the key exists of some struct containing enums.
(Using it for caching modified images and retrieving them during rendering a game).

A simple example:

const Key = struct {
    image_index: u32,
    modifier: Modifier,
    style: u8,
}

const Modifier = enum(u8) {
    flip_vert,
    flip_horz,
}

var map: std.HashMapUnmanaged(Key, Image);

How to accomplish a fast hashkey for Key?
Are there other know slowdowns in HashMap during hashing / lookup which I should know?

2

A small question beforehand:
You already have an image_index, why can’t you use it to lookup things in an array?

For hashing a small type like yours I would just treat it as an u64 and then put it into the std.hash.int function which is quite fast and good. Of course unused/padding bits should be masked of beforehand to make the hash and equality work correctly.

As for the HashMap design the default HashMap of the standard library should be fine enough for most purposes. If you need concurrency first try to just wrap it in a mutex/rw-lock and see if that is performant enough.

A big possible latency increase for a single operation can happen when the hashmap needs to rehash, either due changing its size or repeatedly inserting and removing keys. There are other possible designs that don’t need to ever rehash but those are then usually not quite as fast in the median(but do have better tail latency).
In general resizing hashmaps is a complicated topic – especially with concurrency in mind. So, if you need to write your own hashmap for more performance or other guarantees(deterministic iteration order, insertion order independent,…) try your hardest to make it fixed size.

4 Likes
3

If all possible image indexes are known at compile time, you can implement a static hash map of nullable images instead (StaticMap(Key, ?Image)). For example, std.StaticStringMap with .initComptime does this for string keys, in O(n) space and lookup.

If O(n) lookup is still too slow, generating a perfect hash function at compile time can give you constant time lookup. Andrew has a blog post on compile time perfect hashing in zig.

6 Likes