Settings

Theme

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

github.com

2 points by kushalt 3 months ago · 2 comments

Reader

kushaltOP 3 months ago

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.

Keyboard Shortcuts

j
Next item
k
Previous item
o / Enter
Open selected item
?
Show this help
Esc
Close modal / clear selection