我们正在用 C++ 开发高性能关键软件。我们需要一个并发哈希映射并实现它。因此，我们编写了一个基准测试来弄清楚，我们的并发哈希映射与std::unordered_map.
But, std::unordered_map似乎非常慢...所以这是我们的微基准测试（对于并发映射，我们生成了一个新线程以确保锁定不会被优化掉，并注意我从不插入 0 因为我也用google::dense_hash_map，需要一个空值）：
boost::random::mt19937 rng;
boost::random::uniform_int_distribution<> dist(std::numeric_limits<uint64_t>::min(), std::numeric_limits<uint64_t>::max());
std::vector<uint64_t> vec(SIZE);
for (int i = 0; i < SIZE; ++i) {
uint64_t val = 0;
while (val == 0) {
val = dist(rng);
}
vec[i] = val;
}
std::unordered_map<int, long double> map;
auto begin = std::chrono::high_resolution_clock::now();
for (int i = 0; i < SIZE; ++i) {
map[vec[i]] = 0.0;
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - begin);
std::cout << "inserts: " << elapsed.count() << std::endl;
std::random_shuffle(vec.begin(), vec.end());
begin = std::chrono::high_resolution_clock::now();
long double val;
for (int i = 0; i < SIZE; ++i) {
val = map[vec[i]];
}
end = std::chrono::high_resolution_clock::now();
elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - begin);
std::cout << "get: " << elapsed.count() << std::endl;
（编辑：整个源代码可以在这里找到：http://pastebin.com/vPqf7eya http://pastebin.com/vPqf7eya)
结果为std::unordered_map is:
inserts: 35126
get : 2959
For google::dense_map:
inserts: 3653
get : 816
对于我们手动支持的并发映射（它执行锁定，尽管基准测试是单线程的 - 但在单独的生成线程中）：
inserts: 5213
get : 2594
如果我在没有 pthread 支持的情况下编译基准程序并在主线程中运行所有内容，我会得到以下手动支持并发映射的结果：
inserts: 4441
get : 1180
我使用以下命令进行编译：
g++-4.7 -O3 -DNDEBUG -I/tmp/benchmap/sparsehash-2.0.2/src/ -std=c++11 -pthread main.cc
所以特别插入std::unordered_map似乎非常昂贵 - 35 秒，而其他地图则为 3-5 秒。而且查找时间似乎相当长。
我的问题：这是为什么？我在 stackoverflow 上读到另一个问题，有人问，为什么std::tr1::unordered_map比他自己的实现慢。评分最高的答案指出，std::tr1::unordered_map需要实现更复杂的接口。但我看不到这个论点：我们在并发映射中使用存储桶方法，std::unordered_map也使用桶方法（google::dense_hash_map不，但比std::unordered_map应该至少和我们手工支持的并发安全版本一样快？）。除此之外，我在界面中看不到任何强制执行使哈希映射表现不佳的功能的内容......
所以我的问题是：这是真的吗std::unordered_map好像很慢？如果不是：出了什么问题？如果是：原因是什么？
我的主要问题是：为什么将一个值插入到std::unordered_map如此昂贵（即使我们在开始时保留足够的空间，它的性能也好不到哪里去 - 所以重新散列似乎不是问题）？
EDIT:
首先：是的，所提供的基准测试并不是完美无缺的 - 这是因为我们用它进行了很多尝试，它只是一个黑客（例如uint64生成整数的分布实际上不是一个好主意，在循环中排除 0 有点愚蠢等等...）。
目前大多数评论都解释说，我可以通过为其预先分配足够的空间来使 unordered_map 更快。在我们的应用程序中，这是不可能的：我们正在开发一个数据库管理系统，需要一个哈希映射来存储事务期间的一些数据（例如锁定信息）。因此，该映射可以是从 1（用户仅进行一次插入并提交）到数十亿个条目（如果发生全表扫描）的所有内容。这里不可能预先分配足够的空间（并且一开始就分配大量空间会消耗太多内存）。
此外，我很抱歉，我没有足够清楚地说明我的问题：我对让 unordered_map 快速运行并不真正感兴趣（使用谷歌密集哈希映射对我们来说效果很好），我只是不太明白这种巨大的性能差异来自哪里。它不能只是预分配（即使有足够的预分配内存，密集映射也比 unordered_map 快一个数量级，我们手工支持的并发映射以大小为 64 的数组开始 - 因此比 unordered_map 小）。
那么到底是什么原因导致了这种糟糕的表现呢？std::unordered_map？或者以不同的方式问：有人可以编写一个实现吗std::unordered_map符合标准并且（几乎）与谷歌密集哈希图一样快的接口？或者标准中是否有某些内容强制实施者选择一种低效的方式来实施它？
EDIT 2:
通过分析，我发现大量时间用于整数除法。std::unordered_map使用素数作为数组大小，而其他实现则使用 2 的幂。为什么std::unordered_map使用质数？如果哈希值不好，要表现得更好吗？对于好的哈希值来说，恕我直言，这没有什么区别。
EDIT 3:
这些数字是std::map:
inserts: 16462
get : 16978
Sooooooo：为什么插入到std::map比插入更快std::unordered_map...我的意思是WAT？std::map具有更差的局部性（树与数组），需要进行更多分配（每次插入与每次重新散列+每次碰撞加上〜1），并且最重要的是：具有另一种算法复杂性（O（logn）与O（1））！
