c++ - 如何优化此数组抽取/下采样程序的内存访问模式/缓存未命中？

Question

我最近被问到一段代码可以“就地”对数组进行抽取/下采样。这个“抽取”函数采用一个整数数组，并在索引 i/2 的数组中的偶数索引 i 处存储一个条目。它对数组中的所有条目执行此操作。

这会将原始数组中的所有偶数索引条目移动到数组的前半部分。然后可以将数组的其余部分初始化为 0。总体结果是一个数组，它保留了原始数组中的所有偶数索引条目(通过将它们移动到前半部分)并且数组的后半部分为 0。这显然用于在信号处理中对信号进行下采样。<​​/p>

代码看起来像这样:

void decimate (vector<int>& a) {
   int sz = a.size();
   for (int i =0; i < sz; i++) {
     if (i%2 == 0) {
        a[i/2] = a[i];
     }
    }
    for (int i =(sz-1)/2; i < sz; i++) a[i] = 0;
}

在提出将某些变量保存在寄存器中的基本改进建议后，我找不到任何进一步的优化方法，但不确定是否无法做到。

有没有办法优化循环中的内存访问模式以获得更好的缓存性能？ 或者任何其他方法来优化将数组压缩/下采样到的主要复制操作上半场？ (例如，通过支持它的平台的矢量化)

   for (int i =0; i < sz; i++) {
     if (i%2 == 0) {
        a[i/2] = a[i];
     }
    }

是否有任何循环转换(例如平铺/ strip 挖掘)可以为此类抽取循环生成高效代码？

编辑: 下面的答案中建议了几种不同的方法，它们似乎利用 memset/fill 或指针算法来提高速度效率。这个问题主要集中在是否有明确定义的循环转换，它可以显着改善局部性或缓存未命中(例如，如果它是一个有两个循环的循环嵌套，人们可能会研究循环平铺以优化缓存未命中)

Answer 1

你有一个这样的数组:

0 1 2 3 4 5 6 7 8 9

你想要这样结束:

0 2 4 6 8 0 0 0 0 0

我会这样做:

void decimate (vector<int>& a) {
  size_t slow = 1, fast = 2;

  // read the first half, write the first quarter
  size_t stop = (a.size()+1)/2;
  while (fast < stop) {
    a[slow++] = a[fast];
    fast += 2;
  }

  // read and clear the second half, write the second quarter
  stop = a.size();
  while (fast < stop) {
    a[slow++] = a[fast];
    a[fast++] = 0;
    a[fast++] = 0;
  }

  // clean up (only really needed when length is even)
  a[slow] = 0;
}

在我的系统上，这比您的原始版本快大约 20%。

现在由您来测试并让我们知道它在您的系统上是否更快!