与map和unordered_map相比,boost :: flat_map及其性能

Question

编程中的常识是,由于缓存命中,内存局部性会大大提高性能.我最近发现了boost::flat_map哪个是基于矢量的地图实现.它似乎并不像你的典型那样受欢迎map/ unordered_map因此我无法找到任何性能比较.它是如何比较的,它的最佳用例是什么？

谢谢!

Answer 1

我最近在公司运行了不同数据结构的基准测试,所以我觉得我需要说一句话.正确地对事物进行基准测试非常复杂.

标杆

在网络上,我们很少发现(如果有的话)一个精心设计的基准.直到今天,我才发现以记者的方式完成的基准测试(非常快速并且在地毯下扫描了几十个变量).

1)您需要考虑缓存变暖

大多数运行基准测试的人都害怕计时器差异,因此他们运行他们的东西数千次并且花费了整个时间,他们只是小心地为每次操作花费相同的数千次,然后考虑可比较.

事实上,在现实世界中它没有多大意义,因为你的缓存不会很温暖,你的操作可能只会调用一次.因此,您需要使用RDTSC进行基准测试,并且只需要调用一次.英特尔已经发表了一篇论文,描述了如何使用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 = 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位第一个负值).

注意使用内在函数而不是内联汇编.现在编译器很少支持第一个内联汇编,但更糟糕的是,编译器围绕内联汇编创建了一个完整的排序障碍,因为它无法对内部进行静态分析,因此这对于测试现实世界的东西是一个问题,特别是在调用东西时一旦.所以内在函数适用于此,因为它不会破坏编译器对指令的自由重新排序.

3)参数

最后一个问题是人们通常会测试场景的变化太少.容器性能受以下因素影响:

1. 分配器
2. 包含类型的大小
3. 所包含类型的复制操作,分配操作,移动操作,构造操作的实现成本.
4. 容器中的元素数量(问题的大小)
5. 类型有简单的3.操作
6. 类型是POD

第1点很重要,因为容器会不时地进行分配,如果它们使用CRT"新"或某些用户定义的操作(如池分配或空闲列表或其他)进行分配,则很重要...

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

第2点是因为一些容器(比如说A)会浪费时间复制周围的东西,类型越大,开销就越大.问题是,当与另一个容器B进行比较时,对于小型类型,A可能胜过B,对于较大类型,A可能会松散.

第3点与第2点相同,只是它将成本乘以某个加权因子.

第4点是大O混合缓存问题的问题.一些不良的复杂的容器可以大大强于大盘低复杂度的集装箱数量少的类型(如map对比vector,因为它们的缓存位置是不错的,但map片段内存).然后在某个交叉点,它们将会丢失,因为包含的总体大小开始"泄漏"到主存储器并导致高速缓存未命中,加上可以开始感觉到渐近复杂性的事实.

第5点是关于编译器能够在编译时避开空的或微不足道的东西.这可以极大地优化某些操作,因为容器是模板,因此每种类型都有自己的性能配置文件.

第6点与第5点相同,PODS可以受益于复制构造只是一个memcpy的事实,并且一些容器可以针对这些情况使用特定的实现,使用部分模板特化,或者SFINAE根据T的特征选择算法.

关于平面地图

显然,平面地图是一个有序的矢量包装器,如Loki AssocVector,但是随着C++ 11的一些补充现代化,利用移动语义来加速单个元素的插入和删除.

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

您是否认为可能需要flat_unorderedmap？这将是类似的google::sparse_map东西 - 一个开放的地址哈希映射.

开放地址哈希映射的问题是,当rehash它们必须全部复制到新的扩展平坦区域时.当标准的无序映射只需重新创建哈希索引时,分配的数据就会保持原样.当然,缺点是内存像地狱一样碎片化.

在开放地址哈希映射中重新散列的标准是当容量超过桶矢量的大小乘以负载因子时.

典型的负载系数是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

插入

编辑:

我之前的结果包括一个错误:它们实际上测试了有序插入,这对于平面地图表现出非常快的行为.
我稍后将这些结果留在此页面,因为它们很有趣.
这是正确的测试:

我已经检查了实现,这里没有在平面地图中实现的延迟排序.每个插入在运行中进行排序,因此该基准显示渐近趋势:

map:N*log(N)
hashmaps:摊销的N
向量和平面图:N*N.

警告:此后2个测试int和两个测试__int64都是错误的,实际上测试了有序插入(与其他容器的随机插入相比.是的,这让人感到困惑):

我们可以看到有序插入,导致反推,并且非常快.但是,根据我的基准测试的非图表结果,我还可以说这不是接近插入的绝对最优性.在10k个元素处,在预保留矢量上获得完美的反向插入最优性.这给了我们3Million周期; 我们在这里观察到4.8M的有序插入somestruct(因此是最优的160%).

分析:记住这是向量的"随机插入",因此大量的10亿个周期来自于每次插入时必须向上移动一半(平均值)(一个元素一个元素).

随机搜索3个元素(时钟重新归一化为1)

大小= 100

大小= 10000

迭代

超过100(仅适用于MediumPod类型)

超过10000(仅适用于MediumPod类型)

最后一粒盐

最后,我想回到"Benchmarking§3Pt1"(系统分配器).在最近的一个实验中,我正在研究我开发的开放地址哈希映射的性能,我测量了Windows 7和Windows 8之间在某些std::vector用例上的性能差距超过3000%(这里讨论).
这让我想向读者警告上述结果(它们是在Win7上制作的); 所以,你的里程可能会有所不同

最好的祝福

Answer 2

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

• 每当size超出时,迭代器都会失效capacity.
• 当它增长超过capacity它需要重新分配和移动对象,即插入不保证恒定的时间,除了插入end时的特殊情况capacity > size
• 查找比std::map缓存局部性更快,二进制搜索具有与std::map其他方面相同的性能特征
• 使用较少的内存,因为它不是链接的二叉树
• 它永远不会缩小,除非你强行告诉它(因为它会触发重新分配)

最好的用法是事先知道元素的数量(因此可以reserve预先),或者插入/删除很少但查找频繁.迭代器失效使得它在某些用例中有点麻烦,因此它们在程序正确性方面不可互换.