编程中的常识是，由于缓存命中，内存局部性可以大大提高性能。我最近发现boost::flat_map这是基于矢量的地图实现。它似乎并不像典型的那样受欢迎map/unordered_map所以我没能找到任何性能比较。它的比较如何？它的最佳用例是什么？
Thanks!
我最近在我的公司对不同的数据结构进行了基准测试，所以我觉得我需要说一句话。正确地对某些东西进行基准测试非常复杂。
在网络上，我们很少找到（如果有的话）精心设计的基准。直到今天，我只找到了以记者的方式完成的基准（速度相当快，并在地毯下清除了数十个变量）。
1)您需要考虑缓存预热
大多数运行基准测试的人都担心计时器差异，因此他们运行他们的东西数千次并花费整个时间，他们只是小心地为每个操作花费相同的数千次，然后考虑可比性。
事实是，在现实世界中它没有什么意义，因为您的缓存不会是热的，并且您的操作可能只会被调用一次。因此，您需要使用 RDTSC 进行基准测试，并且只对调用它们一次进行计时。 Intel 做了一篇论文描述 http://www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-32-ia-64-benchmark-code-execution-paper.pdf如何使用 RDTSC（使用 cpuid 指令刷新管道，并在程序开始时调用它至少 3 次以使其稳定）。
2)RDTSC 精度测量
我还建议这样做：
u64 g_correctionFactor; // number of clocks to offset after each measurement to remove the overhead of the measurer itself.
u64 g_accuracy;
static u64 const errormeasure = ~((u64)0);
#ifdef _MSC_VER
#pragma intrinsic(__rdtsc)
inline u64 GetRDTSC()
{
int a[4];
__cpuid(a, 0x80000000); // flush OOO instruction pipeline
return __rdtsc();
}
inline void WarmupRDTSC()
{
int a[4];
__cpuid(a, 0x80000000); // warmup cpuid.
__cpuid(a, 0x80000000);
__cpuid(a, 0x80000000);
// measure the measurer overhead with the measurer (crazy he..)
u64 minDiff = LLONG_MAX;
u64 maxDiff = 0; // this is going to help calculate our PRECISION ERROR MARGIN
for (int i = 0; i < 80; ++i)
{
u64 tick1 = GetRDTSC();
u64 tick2 = GetRDTSC();
minDiff = std::min(minDiff, tick2 - tick1); // make many takes, take the smallest that ever come.
maxDiff = std::max(maxDiff, tick2 - tick1);
}
g_correctionFactor = minDiff;
printf("Correction factor %llu clocks\n", g_correctionFactor);
g_accuracy = maxDiff - minDiff;
printf("Measurement Accuracy (in clocks) : %llu\n", g_accuracy);
}
#endif
这是一个差异测量器，它将取所有测量值的最小值，以避免时不时地得到 -10**18（64 位第一个负值）。
请注意使用内部函数而不是内联汇编。如今，编译器很少支持第一个内联汇编，但更糟糕的是，编译器在内联汇编周围创建了完整的排序障碍，因为它无法静态分析内部，所以这是对现实世界的东西进行基准测试的问题，特别是在调用东西时就一次。因此，内部函数适合这里，因为它不会破坏编译器对指令的自由重新排序。
3)参数
最后一个问题是人们通常测试的场景变化太少。 容器性能受以下因素影响：
第 1 点很重要，因为容器确实会不时进行分配，如果它们使用 CRT“new”或某些用户定义的操作（例如池分配或 freelist 或其他）进行分配，则非常重要......
(对于对第 1 部分感兴趣的人，加入 gamedev 上的神秘主题 http://www.gamedev.net/topic/669459-massive-allocation-perf-difference-between-win8-win7-and-linux/关于系统分配器性能影响)
第 2 点是因为某些容器（例如 A）会浪费时间来复制内容，并且类型越大，开销就越大。问题是，当与另一个容器 B 进行比较时，对于较小的类型，A 可能会胜过 B，而对于较大的类型，A 可能会输。
第 3 点与第 2 点相同，只是它将成本乘以某个权重因子。
第4点是大O问题与缓存问题混合在一起。对于少量类型，一些低复杂度容器的性能在很大程度上优于低复杂度容器（例如map vs. vector，因为它们的缓存局部性很好，但是map记忆碎片）。然后在某个交叉点，它们会失败，因为所包含的总体大小开始“泄漏”到主内存并导致缓存未命中，再加上可以开始感受到渐近复杂性的事实。
第 5 点是关于编译器能够在编译时删除空的或琐碎的内容。这可以极大地优化某些操作，因为容器是模板化的，因此每种类型都有自己的性能配置文件。
第 6 点与第 5 点相同，POD 可以受益于复制构造只是一个事实memcpy，并且某些容器可以针对这些情况有特定的实现，使用部分模板特化，或 SFINAE 根据 T 的特征选择算法。
显然，平面映射是一个排序向量包装器，如 Loki AssocVector，但 C++11 附带了一些补充现代化，利用移动语义来加速单个元素的插入和删除。
这仍然是一个订购的容器。大多数人通常不需要订购部分，因此存在unordered...
您是否考虑过也许您需要一个flat_unorderedmap？这会是这样的google::sparse_map或者类似的东西——开放地址哈希图。
开放地址哈希图的问题是，在rehash他们必须将周围的所有内容复制到新扩展的平坦土地上，而标准无序映射只需重新创建哈希索引，而分配的数据保留在原处。当然缺点就是内存碎片化得厉害。
开放地址哈希映射中的重新哈希的标准是当容量超过桶向量的大小乘以负载因子时。
典型的负载系数是0.8;因此，您需要关心的是，如果您可以在填充哈希图之前预先调整其大小，请始终将其预先调整为：intended_filling * (1/0.8) + epsilon这将保证您在填充过程中永远不必虚假地重新散列和重新复制所有内容。
封闭地址映射的优点（std::unordered..）是你不必关心这些参数。
But the boost::flat_map是有序向量；因此，它总是具有 log(N) 渐近复杂度，这不如开放地址哈希图（摊销常数时间）。您也应该考虑这一点。
这是一个涉及不同地图的测试（int钥匙和__int64/somestruct作为值）和std::vector.
测试类型信息：
typeid=__int64 . sizeof=8 . ispod=yes
typeid=struct MediumTypePod . sizeof=184 . ispod=yes
插入
EDIT:
My previous results included a bug: they actually tested ordered insertion, which exhibited a very fast behavior for the flat maps.
I left those results later down this page because they are interesting.
This is the correct test:
我检查了实现，这里的平面地图中没有实现延迟排序之类的东西。每个插入都会动态排序，因此该基准表现出渐近趋势：
地图： O(N * log(N))
哈希图：O(N)
向量和平面图：O(N * N)
Warning: hereafter the 2 tests for std::map and both flat_maps are buggy and actually test ordered insertion (vs random insertion for other containers. yes it's confusing sorry):
我们可以看到，有序插入会导致回推，并且速度非常快。然而，从我的基准测试的非图表结果来看，我也可以说这并不接近反向插入的绝对最优值。在 10k 个元素时，在预先保留的向量上获得了完美的反向插入最优性。这给了我们 300 万次循环；我们在这里观察到 4.8M 的有序插入flat_map（因此是最优的 160%）。
Analysis: remember this is 'random insert' for the vector, so the massive 1 billion cycles come from having to shift half (in average) the data upward (one element by one element) at each insertion.
随机搜索 3 个元素（时钟重新归一化为 1）
大小 = 100
大小 = 10000
迭代
尺寸超过 100（仅限 MediumPod 类型）
超大 10000（仅限中型 Pod 类型）
最后一粒盐
最后，我想回到“基准测试§3 Pt1”（系统分配器）。在最近的一项实验中，我正在围绕以下性能进行我开发的开放地址哈希图 http://sourceforge.net/projects/cgenericopenaddresshashmap/，我在某些计算机上测得 Windows 7 和 Windows 8 之间的性能差距超过 3000%std::unordered_map用例 （在这里讨论 http://www.gamedev.net/topic/669459-massive-allocation-perf-difference-between-win8-win7-and-linux/).
这让我想警告读者上述结果（它们是在Win7上进行的）：您的里程可能会有所不同。