c++ - google::dense_hash_map 与 boost::unordered_map 性能问题

Question

我最近一直在尝试 boost 软件的性能，该软件将 60% 的时间用于在 hashmap 中进行搜索(已通过 valgrind 分析器确认)。

当前的实现是使用 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);

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

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

我显然做错了什么，但在浏览了文档和 github 之后我无法自己弄清楚 code .

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

Answer 1

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

我怀疑您的散列函数真的很慢，或者数据对于散列映射来说不是很好。

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

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

此外，如果您可以为条目分配连续的 ID，则可以跳过 map ，只需使用 vector 来存储数据。并非总是可行，但它总是比 hash_map 更快。

最后，result[key] 应该插入具有默认值的键。该值的构造函数可能是问题的根源，或者是拷贝(如果有的话)。同样，这可能作为二进制文件中的优化内联，因此您不能保证在 Valgrind 中看到它。如果您没有预料到插入会发生，那也可能会使 map 膨胀到足以造成性能问题。