c++ - 同时遍历两个容器时的缓存位置

Question

我明白了，当对容器的每个元素进行一些计算时，如果内存是连续的，则可以获得最佳性能。但是，如果必须同时使用两个或更多大容器(这样它们就无法完全容纳缓存)怎么办？

int main()
{
    const std::size_t BIG_SIZE = 2000000;  // A number such that both ivec and fvec won't fit the cache

    std::vector<int> ivec(BIG_SIZE, 0);
    int start = 0;
    for (auto& i : ivec)
        i = start++;


    std::vector<float> fvec(BIG_SIZE, 0.f);


    auto iit = ivec.cbegin();
    auto fit = fvec.begin();
    for (; iit != ivec.cend() && fit != fvec.end(); ++iit, ++fit) 
        *fit = *iit * 3.14;  // What happens here?
}

在最后一个循环中，缓存是否会同时加载*iit附近的内存块和*fit附近的内存块，或者我每次访问时都会错过缓存*iit 然后 *fit?

如果是后者，我是否应该使用交错模式自定义分配 ivec 和 fvec 以防止这些遗漏？

Answer 1

查看速度更快的最简单方法是进行基准测试。答案将取决于:硬件、输入大小和其他内容(编译器、标志等)。但是，出于本示例的目的，我将使用带有 clang-6.0、C+ 的网站 quick-bench.com +17、-O3 和 libstdc++。下面是比较代码:

static void One(benchmark::State& state) {
  for (auto _ : state) {
    const std::size_t BIG_SIZE = 20000000;

    std::vector<int> ivec(BIG_SIZE, 0);
    benchmark::DoNotOptimize(ivec);
    int start = 0;
    for (auto& i : ivec)
        i = start++;

    std::vector<float> fvec(BIG_SIZE, 0.f);
    benchmark::DoNotOptimize(fvec);

    auto iit = ivec.cbegin();
    auto fit = fvec.begin();
    for (; iit != ivec.cend() && fit != fvec.end(); ++iit, ++fit) 
        *fit = *iit * 3.14;
  }
}
BENCHMARK(One);

static void Two(benchmark::State& state) {
  for (auto _ : state) {
    const std::size_t BIG_SIZE = 20000000;

    std::vector<int> ivec(BIG_SIZE, 0);
    std::vector<float> fvec(BIG_SIZE, 0.f);
    benchmark::DoNotOptimize(ivec);
    benchmark::DoNotOptimize(fvec);
    int start = 0;
    auto fit = fvec.begin();
    for (auto& i : ivec) {
        i = start++;
        *fit = i * 3.14;
        ++fit;
    }
  }
}
BENCHMARK(Two);

第一个函数是您的原始代码，而第二个函数是修改后的版本。 benchmark::DoNotOptimize 只是防止两个 vector 被优化掉。 N 为 2000 的结果:

N 为 20000000 的结果:

如您所见，对于较大的 N，第二个示例会受到影响。您需要仔细编写代码并进行基准测试，而不是做出假设(Google 基准测试是 quick-bench.com 的基础技术)

---

您实际上可以通过使用标准库函数来提高性能。据推测，这是因为他们针对不同的场景进行了优化，并委托(delegate)给比您手动优化的代码更好的代码。这是一个例子:

static void Three(benchmark::State& state) {
  for (auto _ : state) {
    const std::size_t BIG_SIZE = 20000000;

    std::vector<int> ivec(BIG_SIZE, 0);
    std::vector<float> fvec(BIG_SIZE, 0.f);
    benchmark::DoNotOptimize(ivec);
    benchmark::DoNotOptimize(fvec);
    int start = 0;
    auto fit = fvec.begin();
    std::iota(ivec.begin(), ivec.end(), 0);
    std::transform(ivec.begin(), ivec.end(), 
      fvec.begin(),
      [] (const auto a) {
        return a * 3.14;
      });
  }
}
BENCHMARK(Three);

我们用 std::iota 和 std::transform 替换了您的手动循环。大 N 的结果:

如您所见，版本 3 比 #1 和 #2 快(尽管速度稍快)。所以首先使用标准库函数，只有在它太慢时才手动滚动它。