performance - 有效的循环崩溃

Question

在某些应用程序中，我需要将嵌套循环合并为一个，同时保留单独的索引信息。

for j in N:
  for i in M:
    ... A(i,j) ...

// Collapse the loops
for ij in MN:
  ... A(i,j) ...

所以已经研究了使用除法/模（昂贵的运算）和使用 if 语句（中断矢量化，分支预测问题）从 ij 恢复 i,j 的明显方法。最后我想出了以下内容（使用 C 风格的比较):

j += (i == m)
i *= (i != m)
++i, ++ij

是否有更好的方法来做到这一点？谢谢

Answer 1

一般来说，如前所述折叠循环不会提供任何性能优势。

编译器有时确实会破坏这样的循环，但通常是以意想不到的方式。

在特定语言或特定平台上，您通常可以通过以下方式加速循环：

• 倒数
• 使函数在主体“内联”中调用，或者将代码放在循环主体中而不是单独的函数中
• 配置编译器（通常通过命令行选项）以“展开”循环并删除帧指针等

但是在所有情况下，您都必须对您的代码进行概要分析，才能看到这样的努力是有道理的。

一般来说，根据我的经验，像这样的嵌套循环主要由：

1. 容器；尽可能避免拳击和边界检查，你知道你是安全的
2. 在其中调用其他方法的成本；如果可用，请使用“内联”
3. 管道因参考位置错误而停止；如果可能的话，重新安排你的记忆
4. 管道因第二个条件而停止；更少的 if 和间接引用更好

但这可能不适用于您的问题域和平台。 简介！

Answer 2

走其他路可能会更便宜。

for j in N:
  for i in M:
    ij=j*i+j

Answer 3

我不确定你为什么要折叠循环。确保最内部的循环具有较高的行程计数（通过循环反转）并确保您的数据在内存中是连续的。当满足这两个条件时，我已经看到算法的运行速度提高了 10 倍。