google::dense_hash_map 与 boost::unordered_map 性能问题

Question

我最近一直在尝试提高软件的性能，该软件花费 60% 的时间在 hashmap 中搜索（通过 valgrind profiler 确认）。

当前的实现正在使用boost::unordered_map<long long, FrequencyKey>. 我想与它进行比较google::dense_hash_map<long long, FrequencyKey>。我改变了代码中的一行

boost::unordered_map<long long, FrequencyKey> result;

到

google::dense_hash_map<long long, FrequencyKey> result;
result.set_empty_key(-1);

地图的接口在两个地方被调用。大循环之前result.clear()。循环内result[key]。

我boost::unordered_map<long long, FrequencyKey>的软件性能是118 req/s。通过上面列出的更改，我得到了0.5 req/s。

我显然做错了什么，但在查看文档和 github代码后我自己无法弄清楚。

我正在 CentOS 6.5 上使用 gcc/g++ 4.4.7 编译代码。

Answer 1

我不认为你做错了什么。dense_hash_map针对内存而非速度进行优化。

我怀疑要么你的哈希函数真的很慢，要么数据对于哈希映射来说不太好。

如果 hash_map 中的值很少（例如 < 128），请尝试使用向量并进行线性搜索。有时它往往足够快。

如果您有自定义哈希函数，请尝试为其编写基准测试。如果它内联到二进制文件中，Valgring 可能会跳过它。

此外，如果您可以为条目分配连续的 ID，则可以跳过地图并仅使用向量来存储数据。并不总是可能，但它总是比 hash_map 更快。

最后， result[key] 应该插入具有默认值的键。该值的构造函数可能是问题的根源，或者是副本（如果有的话）。同样，这可能作为二进制文件中的优化内联，因此不能保证您在 Valgrind 中看到它。如果您没有预料到插入会发生，那么也可能会使地图充分膨胀从而产生性能问题。