High-performance C++ hash table using grouped SIMD metadata scanning
2 months ago
- #Data Structures
- #C++
- #High-Performance Computing
- 采用分组SIMD元数据扫描的高性能C++哈希表，在大规模场景下表现优于当前最先进(SOTA)的实现方案
- 与ankerl::unordered_dense的性能对比显示，GroupedSIMD在100万元素规模时开始显现优势，尤其在查询密集型场景中表现突出
- 核心特性包括：SSE2指令集支持、仅头文件实现、针对50万元以上元素表的优化设计
- 该设计借鉴Google瑞士表思想，通过连续内存访问提升SIMD指令效率
- 每个槽位使用1字节元数据标签进行快速过滤，显著提升查询性能
- 采用组间二次跳跃而非线性跳跃，既降低聚集效应又确保所有槽位可达
- 权衡取舍包括插入速度较慢(0.72倍SOTA)且不支持删除和动态扩容
- 该实现源于对Yao猜想的证伪过程，其中分组探测机制是关键突破
- 未来工作将增加删除功能支持，并探索ARM NEON指令集的兼容性