std :: vector比普通数组更快？

Question

我刚尝试std::sort对两者std::vector<std::pair<float, unsigned int>>(填充push_back操作)和普通std::pair<float, unsigned int>> *数组(使用new分配然后逐个填充)进行基准测试.比较函数只比较了对的浮动部分.

令人惊讶的是,当在16M值上使用时,在std :: vector上它只需要大约1940毫秒,但在阵列上它大约是2190毫秒.谁能解释一下矢量怎么能更快？是由于缓存,还是只是std :: sort的数组版本实现不好？

gcc (GCC) 4.4.5 20110214 (Red Hat 4.4.5-6)

Intel(R) Core(TM) i7 CPU 870 @ 2.93GHz - cache size 8192 KB (计算机有两个四核CPU,但我认为排序只是单线程)

编辑:现在你可以叫我dumbass,但是当我试图重现我用于测量的代码时(我已经删除了原始代码)我无法重现结果 - 现在数组版本需要大约1915 + - 5ms(测量时间) 32次运行).我只能发誓我已经对10次测量进行了三次测试(手动)并得到了类似的结果,但这并不是一个严格的证据.

原始代码中可能存在一些错误,后台进程似乎无法进行,因为我已经交替测量了向量和数组版本,并且向量结果保持并且没有用户登录.

请将此问题视为已结束.谢谢你的努力.

Answer 1

std::vector<std::pair<float, unsigned int>> (填充push_back操作)

这可以保存所有数据,因此内存位置非常好

std::pair<float, unsigned int>> * 数组(使用new分配然后逐个填充)

这会将数据分散到整个内存中.

你vector和一个简单的数组之间建立了一个非常不公平的比较.数组中涉及的额外间接性会受到损害,缺少局部性会破坏缓存性能.我很惊讶你没有看到更大的胜利支持连续存储.

Answer 2

他们将使用相同版本的sort. 这很可能是随机的 CPU 影响，例如缓存或线程上下文切换。