c++ - 对于非常小的表(通常<10个项目)的高性能表结构，一旦创建表就不会改变？

Question

我正在为表寻找高性能的 C++ 结构。该表将以 void* 作为键，以 uint32 作为值。

表本身很小，创建后不会改变。我想到的第一个想法是使用类似 ska::flat_hash_map<void*, int32_t> 的东西。或std::unordered_map<void*, int32_t> 。然而，这将是矫枉过正，不会为我提供我想要的性能(这些表也适合大量项目)。

所以我考虑使用std::vector<std::pair<void*, int32_t>> ，在创建时对其进行排序并对其进行线性探测。下一个想法将是使用 SIMD 指令，但在当前结构中这是可能的。

我将很快评估的另一个解决方案是这样的:

struct Group
{
    void* items[5]; // search using SIMD
    int32_t items[5]; 
}; // fits in cache line

struct Table
{
     Group* groups;
     size_t capacity;
};

还有更好的选择吗？我只需要 1 次操作:通过键查找值，而不是修改它们，而不是任何东西。谢谢!

编辑:我认为我应该提到的另一件事是访问模式:假设我有一个这些哈希表的数组，每次我都会从数组中的随机表中查找。

Answer 1

在这种情况下，线性探测可能是常见主流架构上最快的解决方案，特别是因为元素数量非常小且有界(即<10)。对项目进行排序不应加快对如此少项目的探测(它仅对二分搜索有用，在这种情况下，二分搜索的成本要高得多)。

如果你想使用SIMD指令，那么为了性能的考虑，你需要使用数组结构而不是结构数组。这意味着您应该使用 std::pair<std::vector<void*>, std::vector<int32_t>>而不是std::vector<std::pair<void*, int32_t>> (由于 64 位架构上 void* 的对齐约束，它会在内存中交替 int32_t 类型和 void* 值，并产生一些填充开销)。有两个std::vector也不是很好，因为你支付了两次管理费用。正如@JorgeBellon 提到的 在评论中，您可以简单地使用 std::array而不是std::vector假设项目的数量已知或有界。

SIMD 指令的一个可能的优化是通过将关键指针拆分为 32 位低位/高位部分来压缩 64 位架构上的关键指针。事实上，两个指针不太可能具有相同的下部(最低有效位)而具有不同的上部。这个技巧可以帮助您一次检查 2 倍以上的指针。

请注意，在实际情况中，使用 SIMD 指令可能效果不是很好。如果项目数量小于 SIMD vector 中的项目数量，则尤其如此。例如，使用 AVX2(在 86-64 处理器上)，您可以一次处理 4 个 64 位值(或 8 个 32 位值)，但如果您的值少于 8 个，则需要屏蔽检查不需要的值(或者如果内存缓冲区不包含一些填充，甚至不加载它们)。这会带来额外的开销。对于 AVX-512 和 SVE(仅在一小部分处理器上可用)来说这并不是什么大问题，因为它们提供了高级屏蔽操作。此外，某些处理器在执行 SIMD 指令时会降低频率(尤其是使用 AVX-512，尽管整数指令的降频效果并不那么强)。与标量版本(可以更好地流水线化)相比，SIMD 指令还引入了一些额外的延迟，并且现代处理器往往能够比 SIMD 并行执行更多的标量指令。出于所有这些原因，尝试编写标量无分支实现当然是一个好主意(如果在编译时已知项目数量，则可能展开以获得更好的性能) .