1 
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 缓存。

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

编辑原始问题的一些背景：Fastest way to Find amxn submatrix in MXN matrix

4

6 回答 6

4

我要尝试的第一件事是将and循环移到iiandjj循环之外。这样，您将使用相同的元素for 2500 万次循环迭代，这意味着您（或编译器，如果幸运的话）可以在这些循环之外提升对它们的访问：ijmatSmallerij

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循环留在里面。经验法则是，在内部循环中增加多维数组的最后一个索引比之前的索引更便于缓存。所以我们修改jjandj比修改iiand更“快乐” i。

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

通过对 的一些早期分析，您可以考虑一些更高级别的事情smaller：例如，如果是，0那么您不需要检查andmatBigger的值，因为总是错误的。iijjnum & 0xff < 0

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

于 2012-05-16T13:22:55.443 回答
2

一些基本建议：

  1. 对其进行分析，以便您了解热点在哪里。
  2. 考虑缓存位置，以及循环顺序产生的地址。
  3. 在最内部的范围内使用 more const，向编译器提示更多信息。
  4. 尝试将其分解，这样您就不会计算测试high是否low失败。
  5. 尝试将偏移量matBigger显式地保持matSmaller到最内层，进入一个简单的增量。
于 2012-05-16T12:27:01.643 回答
1

最好的办法是了解代码应该做什么，然后检查是否存在针对此问题的另一种算法。

除此之外：

  • 如果您只是对是否存在匹配条目感兴趣，请确保在// match found.
  • 确保数据以最佳方式存储。这完全取决于您的问题，但即只有一个大小为 5000*5000*20 的数组和operator()(int,int,int)访问元素的重载可能会更有效。
于 2012-05-16T12:27:36.883 回答
0

matSmaller和是什么matBigger？尝试将它们更改为matBigger[i+ii * COL_COUNT + j+jj]

于 2012-05-16T13:42:39.397 回答
0

我同意史蒂夫关于重新安排你的循环以将更高的计数作为内部循环。由于您的代码仅进行加载和比较，因此我相信很大一部分时间用于指针运算。尝试一个实验来改变史蒂夫的答案：

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++)
      {
      int *pI = &matBigger[i+ii][jj];
      for (int j = 0; j < 5000; j++)
        {
        int num = *pI++;
        int low = num & 0xff;
        if (low < smaller && smaller > (num >> 8)) {
          // match found
        } // for j
      } // for i
    } // for jj
  } // for ii

即使在 64 位模式下，C 编译器也不一定能很好地将所有内容保存在寄存器中。通过将数组访问更改为简单的指针增量，您将使编译器的工作更容易生成高效的代码。

编辑：我刚刚注意到@unwind 提出了基本相同的建议。另一个需要考虑的问题是比较的统计数据。低或高比较更有可能吗？安排条件语句，使不太可能的测试首先出现。

于 2012-05-16T16:37:15.307 回答
0

看来这里有很多重复。一种优化是减少重复工作量。使用笔和纸，我将matBigger“i”索引迭代为：

[0 + 0], [0 + 1], [0 + 2], ..., [0 + 19],
         [1 + 0], [1 + 1], ..., [1 + 18], [1 + 19]
                  [2 + 0], ..., [2 + 17], [2 + 18], [2 + 19]

如您所见，有些位置被多次访问。此外，乘以迭代计数表示访问内部内容：20 * 20 * 5000 * 5000，或 10000000000 (10E+9) 次。好多啊！

所以与其试图加快 10E9 指令的执行速度（如执行（管道）缓存或数据缓存优化），不如尝试减少迭代次数。

该代码正在矩阵中搜索一个范围内的数字：大于最小值且小于最大范围值。

基于此，尝试不同的方法：

  1. 查找并记住搜索值大于低值的所有坐标。让我们称这些锚点。
  2. 对于每个锚点，找到范围之外的锚点之后的第一个值的坐标。

目的是减少重复访问的数量。锚点允许一次性扫描并允许其他决策，例如查找范围或确定包含锚值的 MxN 矩阵。

另一个想法是创建包含matBigger和的新数据结构，matSmaller这些结构更适合搜索。

例如，为 中的每个唯一值创建一个 {value, coordinate list} 条目matSmaller：

  Value    coordinate list
    26 -> (2,3), (6,5), ..., (1007, 75)
    31 -> (4,7), (2634, 5), ...

现在您可以使用此数据结构在其中查找值matSmaller并立即知道它们的位置。因此，您可以搜索matBigger此数据结构中的每个唯一值。这再次减少了访问矩阵的次数。

于 2012-05-16T18:32:21.260 回答