High-performance C++ hash table using grouped SIMD metadata scanning
4 months ago
- #Data Structures
- #C++
- #High-Performance Computing
- A high-performance C++ hash table using grouped SIMD metadata scanning outperforms state-of-the-art (SOTA) implementations at scale.
- Performance comparison with ankerl::unordered_dense shows GroupedSIMD starts winning at 1M elements, especially in lookup-heavy workloads.
- Key features include SSE2 support, header-only implementation, and optimized for tables >500k elements.
- The design leverages contiguous memory access for SIMD efficiency, inspired by Google's Swiss Tables.
- Each slot uses a 1-byte metadata tag for quick filtering, improving lookup performance significantly.
- Quadratic jumps between groups reduce clustering and ensure all slots are reachable, unlike linear jumps.
- Trade-offs include slower inserts (0.72x SOTA) and no support for deletion or dynamic resizing.
- The implementation emerged from disproving Yao's conjecture, with grouped probing being the key insight.
- Future work includes adding deletion support and exploring ARM NEON compatibility.