SIMD Within a Register: How I Doubled Hash Table Lookup Performance
10 months ago
- #Performance Optimization
- #Bit Manipulation
- #Cuckoo Filter
- 作者在C#中实现了使用8位指纹的布谷鸟过滤器，实现了3%的误判率。
- 最初使用字节数组作为哈希表，每个桶包含4个槽位（4字节）。
- 作者尝试用32位无符号整数(uint)替代4字节桶结构以提升性能。
- 测试了两种基于uint的查询方法：一种使用位移操作，另一种使用BitConverter。
- 位移法比原始字节数组循环快35%，而BitConverter因Span开销反而更慢。
- 引入基于异或和位操作的无分支查询方法，正向查询性能提升超60%，负向查询速度提升两倍以上。
- 最终实现通过异或桶值与指纹掩码后，采用位操作技巧检测零字节。
- 尽管降低了代码可读性，但性能提升使位操作在C#实现中具有显著价值。