Latmap 及其与 map 和 unorder_map 相比的性能

编程中的常识是，由于高速缓存的命中，内存本地性大大提高了性能。我最近发现了 boost::flat_map，它是一个基于矢量的映射实现。它似乎不像你的典型 map/unordered_map那样流行，所以我还没能找到任何性能比较。它是如何进行比较的? 它的最佳用例是什么？

谢谢！

60210 次浏览
小开

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

  • 当 size超过 capacity时，迭代器将失效。
  • 当它超过 capacity时，它需要重新分配和移动对象，即插入不能保证恒定的时间，除非在 capacity > size时插入到 end的特殊情况
  • 由于缓存本地化，查找比 std::map快，二进制搜索具有与 std::map相同的性能特征
  • 使用较少的内存，因为它不是链接的二叉树
  • 它永远不会收缩，除非你强迫它收缩(因为这会触发重新分配)

最佳用法是提前知道元素的数量(这样就可以提前知道 reserve) ，或者插入/删除操作很少但频繁地进行查找。迭代器失效使得它在某些用例中有点麻烦，因此它们在程序正确性方面是不可互换的。

小开
最佳答案

我最近在我的公司运行了一个关于不同数据结构的基准测试，所以我觉得我需要放弃一个词。正确的基准测试是非常复杂的。

Benchmarking

在 Web 上，我们很少找到(如果有的话)设计良好的基准。直到今天，我只发现基准测试是以记者的方式完成的(非常迅速，而且掩盖了数十个变量)。

1) You need to consider cache warming

大多数运行基准测试的人害怕计时器出现差异，因此他们运行自己的东西数千次，花费整个时间，他们只是小心翼翼地为每个操作采用相同的数千次，然后认为这是可比的。

事实上，在现实世界中，这样做没有什么意义，因为您的缓存不会是热的，而且您的操作很可能只被调用一次。因此，您需要使用 RDTSC 进行基准测试，并且时间资料只调用它们一次。 Intel 已经写了一篇论文 描述如何使用 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. 分配器
  2. 所包含类型的大小
  3. cost of implementation of the copy operation, assignment operation, move operation, construction operation, of the contained type.
  4. 容器中的元素数(问题的大小)
  5. type has trivial 3.-operations
  6. type is POD

第一点很重要，因为容器是不时分配的，如果它们使用 CRT“ new”或者一些用户定义的操作来分配，比如池分配、自由列表或者其他..。

(对于对 pt 1感兴趣的人，请加入 gamedev 关于系统分配器性能影响的神秘主题)

第二点是因为有些容器(比如 A)会浪费时间复制周围的内容，类型越大，开销就越大。问题是，与另一个集装箱 B 相比，小型集装箱 A 可能赢过 B，大型集装箱 A 可能输。

第三点和第二点是一样的，除了它是成本乘以某个加权因子。

第4点是一个大 O 和缓存问题混合在一起的问题。对于少数类型(比如 map和 vector，因为它们的缓存位置很好，但是 map会破坏内存) ，一些低复杂度容器的性能大大优于低复杂度容器。然后在某个交叉点，它们会丢失，因为包含的总体大小开始“泄漏”到主内存并导致缓存丢失，再加上渐近复杂性可以开始感觉到的事实。

Point 5 is about compilers being able to elide stuff that are empty or trivial at compile time. This can optimize greatly some operations because the containers are templated, therefore each type will have its own performance profile.

第6点与第5点相同，POD 可以从拷贝构造只是 memcpy这一事实中受益，并且一些容器可以为这些情况具有特定的实现，使用部分模板专门化或 SFINAE 根据 T 的特征选择算法。

关于平面地图

显然，平面映射是一个有序的向量包装器，就像 Loki AssocVector 一样，但是通过 C + + 11附带的一些补充现代化，利用 move 语义来加速单个元素的插入和删除。

这仍然是一个有序的集装箱。大多数人通常不需要订购部分，因此存在 unordered..。

你有没有想过也许你需要一个 flat_unorderedmap？比如像 google::sparse_map或者类似的东西-一个开放地址散列表。

开放地址散列映射的问题在于，在 rehash时，它们必须将周围的所有内容复制到新的扩展平地，而标准的无序映射只需重新创建散列索引，而分配的数据保持在原来的位置。当然，缺点是记忆支离破碎。

在开放地址哈希映射中重哈希的条件是当容量超过 bucket 向量的大小乘以加载因子时。

一个典型的加载因子是 0.8; 因此，您需要关注这一点，如果您可以在填充之前预先调整您的散列映射的大小，始终预先调整到: intended_filling * (1/0.8) + epsilon这将给您一个保证，永远不必在填充过程中虚假地重新散列和复制所有内容。

闭合地址映射(std::unordered..)的优点是您不必关心这些参数。

但是 boost::flat_map是一个有序向量，因此它总是具有 log (N)渐近复杂度，这不如开放地址散列映射(摊销常数时间)好。你也应该考虑一下。

基准结果

这是一个涉及不同地图(以 int键和 __int64/somestruct为值)和 std::vector的测试。

测试类别资料:

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

插入

编辑:

我以前的结果包括一个 bug: 它们实际上测试了有序插入，这显示了平面映射的一个非常快的行为。
我把这些结果留在本页后面，因为它们很有趣。 < br > 这是正确的测试: random insert 100

random insert 10000

I have checked the implementation, there is no such thing as a deferred sort implemented in the flat maps here. Each insertion sorts on the fly, therefore this benchmark exhibits the asymptotic tendencies:

Map: O (N * log (N))
散列表: O (N)
矢量图和平面图: O (N * N) < br >

警告 : 此后对 std::map和两个 flat_map的两个测试是 马车，实际上测试的是 ordered insertion(相对于其他容器的随机插入)。是的，这很让人困惑，对不起) :
mixed insert of 100 elements without reservation

我们可以看到，有序的插入，导致后推，并且非常快。然而，从我的基准测试的非图表结果来看，我还可以说，这并不接近于后插入的绝对最优性。在10k 元素下，在预留向量上获得了最佳的后插入性能。这给了我们300万个循环; 我们观察到4.8 M 有序地插入到 flat_map中(因此是最佳的160%)。

mixed insert of 10000 elements without reservation 分析: 记住这是向量的“随机插入”，所以大量的10亿个周期来自于在每次插入时将数据向上移动一半(平均)(一个元素一个元素)。

Random search of 3 elements (clocks renormalized to 1)

大小 = 100

rand search within a container of 100 elements

面积 = 10000

rand search within a container of 10000 elements

Iteration

大小超过100(只有 MediumPod 类型)

Iteration over 100 medium pods

大小超过10000(只有 MediumPod 类型)

Iteration over 10000 medium pods

最后一点盐

最后，我想回到“基准测试3Pt1”(系统分配器)。在最近的一个实验中，我正在做关于 我开发的一个开放地址散列表性能的测试，我测量了在一些 std::unordered_map用例(在这里讨论)中，Windows 7和 Windows 8之间的性能差距超过3000% 。
这让我想要警告读者以上的结果(他们是在 Win7上制作的) : 你的英里数可能会有所不同。


提交答案