Harrier: A high-performance Rust hashmap using SIMD-accelerated cuckoo hashing(github.com)

2 pointsby kushaltvor 5 Monaten2 comments

Harrier: A high-performance Rust hashmap using SIMD-accelerated cuckoo hashing

https://github.com/kushalthaman/harrier

2 comments

kushaltvor 5 Monaten

Harrier is a Rust hashmap focused on very fast lookups with modern hash-table techniques. The library was inspired by Reiner Pope's https://reiner.org/cuckoo-hashing. We created a production-ready hashmap library out the SIMD-accelerated cuckoo hashing idea he proposes. Here are some things it uses:

- SIMD control-byte probing (16-byte groups) - Two-choice cuckoo placement with BFS displacement on insert pressure - Bounded main-table lookup path (no long probe chains in the common path) - Rare-path safety valves: overflow stash + optional hasher reseed hook

It provides 2 key APIs: - HarrierMap<K, V> (generic) - HarrierU64Map<V> (specialized hot path for integer keys)

We have various performance results. Here is one:

In our strict lookup gate (same harness repeatedly with process-repeat stability checks), at ~75% load and n=786,432, harrier_u64 is typically around 6.5–7.1 ns for find_hit. For comparison, hashbrown is typically around 7.1–7.7 ns. So the specialized u64 path is usually in the ~10% faster range on hit lookups, at least in this regime.

ycombinatrixvor 5 Monaten

Have you considered no_std support?