c++ - boost::flat_map 及其与 map 和 unordered_map 相比的性能

Question

编程中的常识是，由于缓存命中，内存局部性可以大大 boost 性能。我最近发现了 boost::flat_map这是一个基于 vector 的 map 实现。它似乎不像您典型的那样受欢迎 map/unordered_map所以我找不到任何性能比较。它如何比较以及它的最佳用例是什么？

谢谢!

Answer 1

我最近在我的公司对不同的数据结构运行了一个基准测试，所以我觉得我需要放弃一个词。正确地对某些东西进行基准测试是非常复杂的。
基准测试
在网络上，我们很少找到(如果有的话)精心设计的基准测试。直到今天，我只找到了以记者的方式完成的基准测试(很快，并在地毯下扫描了数十个变量)。
1) 您需要考虑缓存预热
大多数运行基准测试的人都害怕计时器差异，因此他们运行他们的东西数千次并花费全部时间，他们只是小心翼翼地为每次操作采取相同的数千次，然后认为它具有可比性。
事实是，在现实世界中它没有什么意义，因为您的缓存不会是热的，并且您的操作可能只会被调用一次。因此，您需要使用 RDTSC 进行基准测试，并且只计算一次调用它们的时间。
英特尔发论文describing如何使用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) 参数
最后一个问题是人们通常测试场景的变化太少。
容器性能受以下因素影响:

分配器

包含类型的大小

所包含类型的复制操作、赋值操作、移动操作、构造操作的实现成本。

容器中的元素数量(问题的大小)

类型有简单的 3.-操作

类型为 POD

第 1 点很重要，因为容器会不时分配，如果它们使用 CRT"new"或某些用户定义的操作(如池分配或空闲列表或其他...
(对于对第 1 点感兴趣的人， join the mystery thread on gamedev 关于系统分配器性能影响)
第 2 点是因为一些容器(比如 A)会浪费时间复制东西，而且类型越大开销越大。问题在于，与另一个容器 B 相比，A 可能会在小型类型上胜过 B，而在较大类型上输掉。
第 3 点与第 2 点相同，只是它将成本乘以某个加权因子。
第 4 点是大 O 与缓存问题混合的问题。对于少数类型(例如 map 与 vector ，因为它们的缓存位置很好，但 map 会分割内存)，一些复杂度差的容器在很大程度上可以胜过低复杂度容器。然后在某个交叉点，它们将失败，因为包含的整体大小开始“泄漏”到主内存并导致缓存未命中，再加上可以开始感觉到渐近复杂性的事实。
第 5 点是关于编译器能够在编译时忽略空的或微不足道的东西。这可以极大地优化一些操作，因为容器是模板化的，因此每种类型都有自己的性能配置文件。
第 6 点与第 5 点相同，POD 可以从复制构造只是一个 memcpy 的事实中受益。 ，并且一些容器可以针对这些情况有特定的实现，使用部分模板特化，或者 SFINAE 根据 T 的特征选择算法。
关于平面 map
显然，平面 map 是一个排序的 vector 包装器，就像 Loki AssocVector，但是随着 C++11 的一些补充现代化，利用移动语义来 boost 单个元素的插入和删除。
这仍然是一个有序的容器。大多数人通常不需要订购部分，因此存在 unordered.. .
你有没有想过，也许你需要一个 flat_unorderedmap ?这将类似于 google::sparse_map或者类似的东西——一个开放的地址哈希映射。
开放地址hashmap的问题是在 rehash的时候他们必须将周围的所有内容复制到新的扩展平面上，而标准的无序映射只需重新创建哈希索引，而分配的数据则保持原样。缺点当然是内存碎片化如 hell 。
开放地址哈希映射中重新哈希的标准是当容量超过桶 vector 的大小乘以负载因子时。
典型的负载因子是 0.8 ;因此，您需要注意这一点，如果您可以在填充之前预先调整哈希映射的大小，请始终将其预先调整为: intended_filling * (1/0.8) + epsilon这将保证您在填充过程中永远不必虚假地重新散列和重新复制所有内容。
封闭地址映射( std::unordered.. )的优点是您不必关心这些参数。
但是 boost::flat_map是有序 vector ；因此，它将始终具有 log(N) 渐近复杂度，这不如开放地址哈希映射(摊销常数时间)好。你也应该考虑一下。
基准测试结果
这是一个涉及不同映射的测试(使用 int 键和 __int64/ somestruct 作为值)和 std::vector .
测试类型信息:

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

插入
编辑:
我之前的结果包含一个错误:他们实际上测试了有序插入，这对平面 map 表现出非常快的行为。
我稍后将这些结果留在本页下方，因为它们很有趣。
这是正确的测试:


我已经检查了实现，这里的平面 map 中没有实现延迟排序之类的东西。每个插入都在运行中排序，因此这个基准表现出渐近的趋势:
map :O(N * log(N))
哈希映射:O(N)
vector 和平面图:O(N * N)
警告 :此后对 std::map 进行 2 次测试和两者 flat_map s 是 buggy 并实际测试 有序插入 (与其他容器的随机插入相比。是的，这很令人困惑，抱歉):

我们可以看到有序插入会导致反向推送，并且速度非常快。然而，从我的基准测试的非图表结果来看，我也可以说这还没有接近反向插入的绝对最优性。在 10k 个元素上，在预先保留的 vector 上获得了完美的反向插入最优性。这给了我们 300 万个周期；我们在这里观察到 4.8M 用于有序插入 flat_map (因此是最佳值的 160%)。

分析:记住这是 vector 的“随机插入”，因此大量的 10 亿个周期来自每次插入时必须向上移动一半(平均)数据(一个元素一个元素)。
随机搜索 3 个元素(时钟重新归一化为 1)
大小 = 100

大小 = 10000

迭代
超过 100 码(仅限 MediumPod 类型)

超过 10000 号(仅限 MediumPod 类型)

最后一粒盐
最后，我想回到“基准 §3 Pt1”(系统分配器)。在最近的一个实验中，我在做 an open address hash map I developed 的性能，我在一些 std::unordered_map 上测得 Windows 7 和 Windows 8 之间的性能差距超过 3000%用例( discussed here )。
这让我想警告读者上述结果(它们是在 Win7 上制作的):您的里程可能会有所不同。