c++嵌套循环性能

Question

我基本上有两个向量，一个用于大量元素，另一个用于采样元素数据的少量探针。我无意中发现了实现这两个循环的顺序的问题。当然，我认为在更大的向量上加上外循环是有益的。

实现1:

for(auto& elem: elements) {
    for(auto& probe: probes) {
        probe.insertParticleData(elem);
    }
}

然而，第二个实现似乎只需要一半的时间。

实现2:

for(auto& probe: probes) {
    for(auto& elem: elements) {
        probe.insertParticleData(elem);
    }
}

那是什么原因呢？

编辑：

时间由以下代码生成

clock_t t_begin_ps = std::clock();
... // timed code
clock_t t_end_ps = std::clock();
double elapsed_secs_ps = double(t_end_ps - t_begin_ps) / CLOCKS_PER_SEC;

在插入元素数据时，我主要做两件事，测试到探针的距离是否小于一个极限，以及计算的平均值。

probe::insertParticleData (const elem& pP) {
   if (!isInside(pP.position())) {return false;}
   ... // compute alpha and beta
   avg_vel = alpha*avg_vel + beta*pP.getVel();
   return true;
}

为了了解内存的使用情况，我有大约。10k元素，它们是具有30个双数据成员的对象。在测试中，我使用了包含15个双倍的10个探针。

Answer 1

今天的CPU对内存的线性访问进行了很大的优化。因此，几个长循环将击败许多短循环。您希望内部循环在长向量上迭代。

Answer 2

我的猜测是:如果insertParticleData是虚拟的，编译器将把函数的地址作为内循环中的常量，并将vtable提取移到内环之外。即有效地生成如下代码：

   for (auto& probe: probes) {
      funcPtr p = probe.insertParticleData;
      for (auto& elem: elements) {
        (*p)(elem);
      }
   }

而在第一个版本中，每一个内部迭代都要计算p。