logo标签列表

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

c++
3

以下代码展示了当使用std::sort()对std::vector进行排序时，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 miliseconds\n", (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 miliseconds\n", (clock()-cl)/CLOCK_MILI);

  // Destroy the strings
  for(auto obj : list)
    delete[] (char*)obj;
  return EXIT_SUCCESS;
}

遍历 list 并调用 insert() 的过程中尝试了 2 次迭代。函数 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

使用std::sort（）修改list时，访问list会慢9倍。 当std::sort（）被std :: random_shuffle（）或一些修改list的代码替换时，会出现类似的结果。

  • 那么到底发生了什么？
  • 为什么在修改后遍历std :: vector会变慢？
2
不确定是否相关，但GCC似乎将insert（obj）优化为等效的len = strlen（obj）; x + = len * len;。https://godbolt.org/z/8WeG9fYrT - Nate Eldredge
1个回答
6

向量名称的选择无意间透露了很多信息。因为向量是指针的向量，它表现得类似于列表，导致原本按(可能)线性顺序分配的数据在排序后以随机顺序访问。

相比之下，如果您访问的所有数据都包含在向量中而没有间接引用，我期望每次运行时的运行时间会更接近。

这种现象的原因是缓存错误预测或将要读取的数据不可用于最小/最快的数据缓存中。从主内存或较深层次的缓存中读取数据通常比从顶层缓存中读取数据慢数个数量级，并且排序将使得预测下一个要读取的内存地址的机会全部失效。

我没有意识到new会分配连续的内存，而std::sort会使向量元素随机分散。谢谢您的答案。 - Renol P. H.
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接