为什么遍历修改后的'std::vector'比未修改的"std：：vector"慢？

Question

这是表示std::vector按std::sort()排序时std::vector的访问行为变慢的代码

#include <cstdio>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cstring>
#include <algorithm>
constexpr auto NUM_KEYS(24000000);
constexpr auto CLOCK_MILI(CLOCKS_PER_SEC/1000);
constexpr auto CHARS("ABCDEFGHIJKLMNOPQRSTUVWXYZ");
static int x = 0;
void insert(void* obj) {
std::size_t len = std::strlen((const char*)obj);
for(std::size_t i=0; i<len; ++i)
for(std::size_t j=0; j<len; ++j)
++x;
}
int main(void) {
std::vector<void*> list;
auto seed = std::chrono::system_clock::now().time_since_epoch().count();
std::mt19937_64 rng(seed);
std::uniform_int_distribution<int> rand_ch(0, 25);
std::uniform_int_distribution<std::size_t> rand_len(8, 16);
// Generate random string
for(std::size_t i=0; i<NUM_KEYS; ++i) {
std::size_t len = rand_len(rng);
char* buf = new char[len+1]();
for(std::size_t j=0; j<len; ++j)
buf[j] = CHARS[rand_ch(rng)];
list.push_back(buf);
}
// First traverse the list
std::clock_t cl = std::clock();
for(auto obj : list)
insert(obj);
printf("Time 1 = %ld milisecondsn", (clock()-cl)/CLOCK_MILI);
// Sorting the list
std::sort(list.begin(), list.end(),
[](const void* a, const void* b) {
return std::strcmp((const char*)a, (const char*)b)<0;
});

// Second traverse the list
cl = std::clock();
for(auto obj : list)
insert(obj);
printf("Time 2 = %ld milisecondsn", (clock()-cl)/CLOCK_MILI);
// Destroy the strings
for(auto obj : list)
delete[] (char*)obj;
return EXIT_SUCCESS;
}

在调用insert()时，有2个迭代试图遍历list。insert()函数不修改数据。第一次迭代没有std::sort()，第二次迭代在std::sort()之后。

在GCC 11.1.0中执行-std=c++17 -O3选项时得到的结果:

Time 1 = 101 miliseconds
Time 2 = 909 miliseconds

同样，std::sort()在运行时被省略的结果:

Time 1 = 102 miliseconds
Time 2 = 101 miliseconds

当list被std::sort()修改时，对list的访问速度慢9倍。当std::sort()被std::random_shuffle()或修改list的代码替换时，也会出现类似的结果。

• 那么到底发生了什么?
• 为什么std::vector修改后遍历变慢?

Answer 1

向量名称的选择意外地透露了一些信息。因为vector是指针向量，所以它的行为类似于列表，导致最初以(可能)线性顺序分配的数据在以随机顺序排序后被访问。相反，如果您访问的所有数据都包含在vector中，而没有间接访问，那么我预计每次运行时的运行时间会更接近。

导致这种现象的原因是缓存预测错误，或者下一个要读的数据在最小/最快的数据缓存中不可用。从主存或更深层的缓存中读取数据通常比从顶层缓存中读取数据慢几个数量级，并且排序将使预测下一个要读取的内存地址的所有机会无效。