4

这是一小段经常被调用的代码，也是我正在尝试优化的卷积算法的一部分（从技术上讲，这是我的第一次优化，我已经将速度提高了 2 倍，但现在我被卡住了） ：

inline int corner_rank( int max_ranks, int *shape, int pos ) {
  int i;
  int corners = 0;
  for ( i = 0; i < max_ranks; i++ ) {
    if ( pos % shape[i] ) break;
    pos /= shape[i];
    corners++;
  }
  return corners;
}

该代码用于计算posN 维数组中某个位置的属性（已展平为指针，加上算术）。max_ranks是维度，并且shape是每个维度中的大小数组。

一个示例 3 维数组可能有max_ranks = 3, 和shape = { 3, 4, 5 }。前几个元素的示意图布局可能如下所示：

 0       1       2       3       4       5       6       7       8
 [0,0,0] [1,0,0] [2,0,0] [0,1,0] [1,1,0] [2,1,0] [0,2,0] [1,2,0] [2,2,0]

 Returned by function:
 3       0       0       1       0       0       1       0       0

其中第一行 0..8 显示由 给出的索引偏移量pos，下面的数字给出多维索引。编辑：下面我放了函数返回的值（2 的值在位置 12、24 和 36 返回）。

该函数有效地返回多维索引中“前导”零的数量，并且旨在避免在每次增量时都需要完全转换为数组索引。

我可以用这个功能做些什么来让它天生更快？有没有一种巧妙的避免方法%，或者另一种计算“角落排名”的方法 - 如果它有一个我不知道的更正式的名称，请道歉。. .

4

1 回答 1

2

您应该返回的唯一时间max_ranks是如果pos等于零。检查这一点允许您从 for 循环中删除条件检查。这应该会改善最坏情况的完成时间，以及 max_ranks 值较大的循环速度。

这是我的补充，以及避免除法操作的另一种方法。我相信这div和@twalberg 所建议的手写一样快，除非有某种方法可以在没有第二次乘法的情况下产生余数。

恐怕因为最常见的答案是 0（甚至没有通过第一个 mod 调用），所以你不会看到太大的改进。我的猜测是您的平均运行时间非常接近模数函数本身的运行时间。您可以尝试寻找一种更快的方法来确定一个数字是否是 的一个因数pos。您实际上不需要计算余数；你只需要知道是否有余数。

抱歉，如果我通过重组您的代码使事情变得混乱。我相信这会稍微快一些，除非您的编译器已经在进行这些优化。

inline int corner_rank( int max_ranks, int *shape, int pos ) {
  // Most calls will not get farther than this.
  if (pos % shape[0] != 0) return 0;

  // One check here, guarantees that while loop below always returns.
  if (pos == 0) return max_ranks;

  int divisor = shape[0] * shape[1];
  int i = 1;
  while (true) {
    if (pos % divisor != 0) return i;
    divisor *= shape[++i];
  }
}

还可以尝试将posand声明divisor为尽可能小的类型。如果它们永远不会大于 255，您可以使用unsigned char. 我知道有些处理器可以比较大的数字更快地执行较小数字的除法，但您必须适当地设置变量类型。

于 2013-10-18T12:13:26.950 回答