boost :: flat_map和它的性能比较map和unordered_map

在编程中常见的知识是由于caching命中，存储器局部性提高了性能。 我最近发现了boost::flat_map这是一个基于vector的地图实现。 它似乎没有像你典型的map / unordered_map一样stream行，所以我一直没能find任何性能比较。 它如何比较以及它的最佳用例是什么？

谢谢！

Answer 1

我最近在我公司运行了不同的数据结构的基准testing，所以我觉得我需要删除一个字。 基准testing正确是非常复杂的。

标杆

在networking上，我们很less发现（如果有的话）一个精心devise的基准。 直到今天，我只find了新闻工作者的基准（很快，在地毯下面扫了几十个variables）。

1）您需要考虑caching升温

大多数运行基准的人都害怕计时器的差异，所以他们千百次运行，占用整个时间，每次操作都要小心千次，再考虑可比性。

事实是，在现实世界中，这是没有意义的，因为你的caching不会很温暖，你的操作可能只会被调用一次。 因此，您需要使用RDTSC进行基准testing，并且只需调用一次即可。 英特尔已经做了一篇文章， 介绍如何使用RDTSC（使用cpuid指令刷新pipe道，并在程序开始时至less调用3次以稳定pipe道）。

2） RDTSC准确度测量

我也build议这样做：

 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 = Aska::Min(minDiff, tick2 - tick1); // make many takes, take the smallest that ever come. maxDiff = Aska::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位的第一个负值）。

注意使用内在函数而不是内联汇编。 现在编译器很less支持第一个内联汇编，但是更糟糕的是，编译器在内联汇编上创build了一个完整的sorting屏障，因为它不能对内部进行静态分析，所以这是一个对现实世界进行基准testing的问题，一旦。 所以一个内在的东西适合这里，因为它不会中断编译器对指令的自由重新sorting。

3）参数

最后一个问题是人们通常testing的场景变化太less。 容器性能受以下因素的影响：

1. 分配器
2. 包含types的大小
3. 包含types的复制操作，分配操作，移动操作，施工操作的实施成本。
4. 容器中元素的数量（问题的大小）
5. types有微不足道的3.操作
6. types是POD

第一点是重要的，因为容器不时分配，如果他们分配使用CRT“新”或一些用户定义的操作，如池分配或freelist或其他…重要的是…

（ 对于pt 1感兴趣的人， joingamedev关于系统分配器性能影响的神秘线程 ）

第二点是因为一些容器（比如说A）会放弃复制周围的东西，而types越大，开销就越大。 问题是，当与另一个集装箱B比较时，A可能会赢得小型的B，而对于更大的types则可能会松动。

第3点与第2点相同，只是它将成本乘以一些加权因子。

第4点是一个大问题混合caching问题。 一些不好的复杂性容器在很大程度上可以胜过低复杂度的容器，因为它们的caching局部性好，但是map碎片化内存。 然后在某个交叉点，它们将会丢失，因为包含的整体大小开始“泄漏”到主存并导致caching未命中，而且还会开始感受到渐近复杂性的事实。

第5点是关于编译器能够在编译时避开空的或微不足道的东西。 这可以大大优化一些操作，因为容器是模板，因此每种types都会有自己的性能configuration文件。

第6点与第5点相同，PODS可以受益于复制构造仅仅是memcpy的事实，并且一些容器可以具有针对这些情况的特定实现，使用部分模板专门化或SFINAE根据T的特征来selectalgorithm。

关于平面地图

显然平面地图是一个sorting的向量包装，就像Loki AssocVector一样，但随着C ++ 11的一些补充现代化，利用移动语义来加速插入和删除单个元素。

这仍然是一个有序的容器。 大多数人通常不需要sorting部分，因此unordered..的存在。

你有没有flat_unorderedmap ，也许你需要一个flat_unorderedmap ？ 这将是像google::sparse_map或类似的东西 – 一个开放的地址哈希映射。

打开地址哈希映射的问题是，在重新哈希时，他们必须复制到新的扩展平坦的土地。 当一个标准的无序映射只需要重新创build散列索引，但分配的数据保持原来的位置。 当然缺点是内存像地狱一样碎片化。

开放地址哈希映射中重新哈希的标准是容量超过了桶vector的大小乘以负载因子。

典型的负载因数是0.8 ; 因此，你需要关心这一点，如果你可以在填充之前预先设定你的哈希映射的大小，总是预先设定的大小为： intended_filling * (1/0.8) + epsilon这将保证你永远不必虚假地重新哈希在填充期间复制一切。

封闭的地址映射（ std::unordered.. ）的优点是你不必关心这些参数。

但是boost::flat_map是一个有序的向量; 因此，它总会有一个log（N）渐近复杂度，这比开放地址散列图（摊销常量时间）要好。 你也应该考虑一下。

基准testing结果

这是一个涉及不同映射（int key和__int64 / somestruct作为值）和std :: vector的testing。

testingtypes信息：

 typeid=__int64 . sizeof=8 . ispod=yes typeid=struct MediumTypePod . sizeof=184 . ispod=yes 

插入

编辑：

我以前的结果包括一个错误：他们实际上testing了有序插入，这对于平面地图显示出非常快的行为。
我稍后将这些结果留在本页面，因为它们很有趣。
这是正确的testing：

我已经检查了实现，在这里的平面地图中没有延迟sorting的东西。 每个插入都是随机sorting的，因此这个基准显示出渐近趋势：

地图：N * log（N）
hashmaps：摊销N
vector和平面图：N * N

警告 ：以下对std::map和flat_map的testing是有问题的，实际上是testing有序插入 ：

我们可以看到有序的插入，导致后推，并且非常快。 然而，从我的基准testing的非图表结果来看，我也可以说这不是一个反向插入的绝对最佳值。 在预保留向量上获得完美的反向插入最优性。 这给了我们三百万个周期; 我们在这里观察4.8M来提升（因此是最佳的160％）。

随机search3个元素（时钟重新归一化为1）

大小= 100

大小= 10000

迭代

大小超过100（仅限MediumPodtypes）

大小超过10000（仅限MediumPodtypes）

最后的盐粒

最后我想回到“Benchmarking§3Pt1”（系统分配器）。 在最近的一个实验中，我正在开发一个开放地址哈希映射的性能，我测量了一些std::unordered_map用例（ 这里讨论 ）在Windows 7和Windows 8之间的性能差距超过3000％。
这让我想告诉读者以上的结果（他们是在Win7上做的）; 所以，你的里程可能会有所不同

最好的祝福

Answer 2

从文档看来，这是类似于Loki::AssocVector ，我是一个相当重的用户。 因为它是基于vector的，所以它具有vector的特征，也就是说：

• 每当size增长超过capacity时，迭代器就会失效。
• 当capacity超过capacity ，需要重新分配和移动对象，即插入不能保证恒定的时间，除了capacity > size end插入的特殊情况
• 由于caching局部性，查找速度比std::map要快，否则它与std::map具有相同的性能特点
• 使用较less的内存，因为它不是一个链接的二叉树
• 它不会收缩，除非你强行告诉它（因为这会触发重新分配）

最好的用法是事先知道元素的数量（这样可以预先reserve ），或者当插入/删除很less，但查找频繁时。 迭代器失效使得在一些用例中有点麻烦，所以它们在程序正确性方面不能互换。