c++ - 优化此代码块

Question

for (int i = 0; i < 5000; i++)
   for (int j = 0; j < 5000; j++)
   {
      for (int ii = 0; ii < 20; ii++)
          for (int jj = 0; jj < 20; jj++)
           {
               int num = matBigger[i+ii][j+jj];
               // Extract range from this.
               int low = num & 0xff;
               int high = num >> 8;
               if (low < matSmaller[ii][jj] && matSmaller[ii][jj] > high)
                  // match found
           }
   }

机器是x86_64, 32kb L1 cahce, 256 Kb L2 cache.

关于如何优化此代码的任何指示？

编辑 原始问题的一些背景:Fastest way to Find a m x n submatrix in M X N matrix

Answer 1

我要尝试的第一件事是移动 ii和 jj在 i 外循环和 j循环。这样您就可以使用 matSmaller 的相同元素。 i 的 2500 万次迭代和 j循环，这意味着您(或编译器，如果幸运的话)可以将对它们的访问提升到这些循环之外:

for (int ii = 0; ii < 20; ii++)
  for (int jj = 0; jj < 20; jj++)
    int smaller = matSmaller[ii][jj];
    for (int i = 0; i < 5000; i++)
      for (int j = 0; j < 5000; j++) {
        int num = matBigger[i+ii][j+jj];
        int low = num & 0xff;
        if (low < smaller && smaller > (num >> 8)) {
          // match found
        }
      }

这可能会更快(由于对 matSmaller 数组的访问较少)，也可能会更慢(因为我已经更改了对 matBigger 数组的访问模式，而且我可能已经它不太缓存友好)。类似的替代方法是移动 ii外循环 i和 j和提升matSmaller[ii] , 但保留 jj在里面循环。经验法则是在内部循环中递增多维数组的 last 索引比之前的索引对缓存更友好。所以我们“更高兴”修改jj和 j比我们修改 ii和 i .

我会尝试的第二件事 - matBigger 的类型是什么？看起来其中的值只有 16 位，所以尝试将其作为 int和 (u)int16_t .前者可能更快，因为对齐 int访问速度很快。后者可能更快，因为在任何时候都有更多的数组适合缓存。

通过对 smaller 的一些早期分析，您可以考虑一些更高层次的事情:例如，如果它是 0那么你不需要检查 matBigger对于 ii 的值和 jj ，因为 num & 0xff < 0总是假的。

为了比“猜测事物并查看它们是否更快”做得更好，您首先需要知道哪条线路 HitTest ，这意味着您需要一个分析器。