作者在实现C#中的Cuckoo Filter时，将哈希表的底层结构从字节数组改为32位整数，利用SIMD（单指令多数据）技术，成功将查找性能提升了一倍。通过将每个桶的4个字节视为一个整数，并使用掩码操作快速查找目标字节，显著优化了哈希表的查询效率。

标题：寄存器内的SIMD：如何将哈希表查找性能提升一倍

在C#中实现Cuckoo Filter时，我为其底层的哈希表设计了一个类似数组的结构。我选择了8位的指纹（fingerprint），因为它能很好地与字节边界对齐，并且将误判率保持在3%左右。

最初的设计是一个简单的字节数组，每个桶的起始位置通过bucketIdx * bucketSize计算得出。每个桶的大小为4个槽位，这是Cuckoo Filter的一个合理选择。然而，桶中的4个字节让我联想到一个32位整数。尽管C#并不追求极低延迟，但我还是忍不住想尝试用32位整数替换4字节的桶，看看是否能提升查找性能。

实现与优化

最初，我使用了一个预分配的字节数组来存储哈希表，每个桶有4个槽位。查找指纹的代码如下：

csharp public bool Contains(byte fingerprint, uint bucketIdx) { var s = bucketIdx * 4; for (var i = s; i < s + BucketSize; i++) { if (_table[i] == fingerprint) return true; } return false; }

随后，我将底层数组从byte[]改为uint[]，并重构了查找逻辑。通过位移操作，查找性能提升了约35%。然而，使用BitConverter的方法反而比原始实现更慢，因此被放弃。

位操作优化

为了进一步提升性能，我借鉴了Sean Anderson的《Bit Twiddling Hacks》中的技巧，通过位操作来检测零字节。具体来说，使用(v - 0x01010101U) & ~v & 0x80808080U来判断是否存在零字节。接着，通过XOR操作将目标字节转换为零，从而利用上述技巧快速判断指纹是否存在于桶中。

最终的查找代码如下：

csharp public bool Contains(byte fingerprint, uint bucketIdx) { uint bucket = _table[bucketIdx]; uint mask = fingerprint * 0x01010101U; uint xored = bucket ^ mask; return ((xored - 0x01010101U) & ~xored & 0x80808080U) != 0; }

性能提升

通过这一系列的优化，查找性能得到了显著提升。正向查找的速度提升了超过60%，而反向查找的速度更是提升了一倍以上。尽管代码的可读性有所下降，但性能的提升使得这一优化值得。

总结

虽然我并不热衷于在C#生产代码中使用复杂的位操作，但这次优化确实带来了显著的性能提升。代码库仍然保持紧凑，且通过注释可以很好地解释这些技巧。希望这些经验能为其他人提供帮助，或者至少让你在这次优化之旅中有所收获。

评论主要围绕哈希表性能优化、布谷鸟过滤器（Cuckoo Filter）的实现细节以及基准测试的改进建议展开。以下是总结：

1. 哈希表性能优化：

   • warangal 提到在已知最大迭代次数的热循环中使用自定义哈希表，通过不存储哈希值来减少缓存未命中，提升15-20%的性能。他还质疑布谷鸟过滤器在热循环中的插入成本可能较高。
     • 引用：“i use a custom hash-table initialized with that value... leads to speed up about 15-20% due to less cache misses.”
   • mizmar 讨论了瑞士表（Swiss Table）的实现，指出其使用线性探测法处理冲突，尽管初始版本存在哈希碰撞问题，但通过快速探测使其性能不受影响。
     • 引用：“It’s just open-addressing linear probe with no technique to deal with collisions and clustering.”

2. 布谷鸟过滤器的实现：

   • warangal 提到布谷鸟过滤器允许假阳性，与字典不同，后者确保假阳性率为0。
     • 引用：“false-positives are allowed, unlike data-structure like dictionary, which makes sure that false-positive rate is 0.”

3. 基准测试的改进建议：

   • curiouscoding 提出多个改进建议，包括优化分支预测、展示每次查找的时间、避免重复查询以测量内存延迟，以及使用SIMD指令。
     • 引用：“Probably much better is something like table[0] == fp | table[1] == fp | table[2] == fp | table[3] == fp.”
     • 引用：“best is to only do each query once in your benchmark.”

4. 哈希表查找的复杂度：

   • alwahi 对哈希表查找的O(1)复杂度表示疑惑。
     • 引用：“i thought hash table lookup was already O(1)...”

5. C#中的溢出检查：

   • Const-me 提到在C#中使用unchecked块处理溢出，并认为溢出检查对性能影响微乎其微，但有助于发现和修复bug。
     • 引用：“the performance impact of that option is negligible... exposed bugs which were trivial to fix.”

总结中，评论者们在哈希表优化、布谷鸟过滤器实现和基准测试方法上提出了不同的见解和建议，反映了对性能优化的关注和不同技术细节的探讨。