问题标签 [loop-unrolling]

triangle我想对应用在对象上的展开循环和 for 循环之间的执行速度差异进行基准测试。整个示例可在此处获得。

这是完整的代码：

该示例由 Point 类型和 Triangle 类型组成。基准计算是三角形重心的计算。可以通过 for 循环来完成：

或者它可以展开，因为三角形具有三个点：

所以我想测试对于一组三角形来说，计算重心的函数会更快。为了充分利用测试，我通过执行带有整数指数参数的主程序来使正在操作的三角形的数量可变：

产生 10^6 个三角形。三角形的数量范围从 100 到 1e06。主程序创建“results.dat”文件。为了分析结果，我编写了一个小的 Python 脚本：

并利用您计算机上的所有内容，复制示例代码，编译它：

要绘制不同重心函数的测量 CPU 时间，请执行 python 脚本（我称之为plotResults.py）：

我期望看到的是展开循环和for循环之间的相对加速（for循环时间/展开循环时间）将随着三角形集的大小而增加。这个结论可以从一个逻辑得出：如果展开的循环比 for 循环快，则执行大量展开的循环应该比执行大量的 for 循环更快。这是由上述 python 脚本生成的结果图：

循环展开的影响很快就消失了。一旦我使用超过 100 个三角形，似乎没有区别。查看 python 脚本计算的加速比：

使用 100 个三角形（列表中的 3d 位置对应于 10^2）时的加速比为 1.15。

我来这里是为了找出我做错了什么，因为这里一定有问题，恕我直言。：） 提前致谢。

编辑：绘制 cachegrind 缓存未命中率

如果程序是这样运行的：

cachegrind生成一堆输出文件，可以用grepfor解析PROGRAM TOTALS，代表以下数据的数字列表，取自cachegrind 手册：

Cachegrind 收集以下统计信息（用于每个统计信息的缩写在括号中给出）：

未命中 (ILmr)。

并且“组合”缓存未命中率定义为：(ILmr + DLmr + DLmw) / (Ir + Dr + Dw)

输出文件可以这样解析：

然后可以使用以下 python 脚本可视化生成的数据：

因此，在展开三角形访问循环时，绘制组合的 LL 未命中率与程序加速比，得到下图：

并且似乎对 LL 错误率存在依赖性：随着它的上升，程序的加速下降。但是，我仍然看不到瓶颈的明确原因。

综合 LL 未命中率是否适合分析？看看 valgrind 的输出，据报道所有的未命中率都低于 5%，这应该还不错吧？

我正在尝试在以下程序中选择性地展开第二个循环：

当我使用以下选项运行 clang (3.5) 时，它会将两个循环展开 4 次。

我究竟做错了什么？此外，如果我添加-fno-unroll-loops或跳过-unroll-count=4标志，它不会展开任何循环。

另外，关于如何调试编译错误的任何提示？

我有一个小程序，它是一个相当无意义的简单数字运算练习，让我陷入了循环。

该程序产生了一堆执行简单数学运算的工作线程。最近我改变了一种工人变体的内部循环：

类似于：

数组由值不高于 1025 的随机整数填充，并且数组值不会改变。

最终结果是程序运行得更快，尽管仔细检查似乎表明 CPU 在运行较新版本的代码时实际上并没有做任何事情。似乎 JVM 已经发现它可以安全地忽略在一次外循环迭代后替换内循环的代码，因为它只是一遍又一遍地对同一组数据进行相同的计算。

为了说明我的观点，旧代码运行大约需要 27000 毫秒，并且显着提高了 CPU 的运行温度（它还显示所有内核的利用率为 100%）。新代码运行可能需要 5 毫秒（有时更短），并且不会导致 CPU 利用率或温度出现峰值。增加外循环迭代次数不会改变新代码的行为，即使迭代次数增加了一百倍或更多。

我有另一个版本的worker，它与上面的相同，除了它有一个除法运算以及加法和乘法运算。在其新的展开形式中，启用除法的版本也比以前的形式快得多，但实际上需要一点时间（第一次运行约 300 毫秒，后续运行约 200 毫秒，尽管有预热，这有点奇怪的）并在其短暂的运行中产生 CPU 温度的严重峰值。增加外循环迭代次数似乎会导致温度现象在运行程序时经过一定时间后基本停止，尽管所有内核的利用率仍然显示为 100%。我的猜测是 JVM 需要更长的时间才能确定在处理除法操作时可以安全忽略哪些操作，

没有向我的所有代码添加除法操作（超出一定数量的外部循环迭代，这实际上并不是一个修复），有什么方法可以让 JVM 停止将我的代码减少到明显的 NOOP？我已经尝试了几种解决该问题的方法，例如每次外循环迭代生成新的随机值、返回具有增量的简单整数变量以及其他一些废话，但这些解决方案都没有产生理想的结果。要么它继续忽略一系列指令，要么修改对性能的影响非常糟糕，以至于我的除法重变体实际上比没有除法操作的代码执行得更好。

编辑：提供一些上下文：

i：此变量是一个整数，用于 do/while 循环中的循环计数器。它在包含工作代码的类文件中定义。它的初始值为0。在较新版本的worker中不再使用它。

int1/int2：这些是在包含工作代码的类文件中定义的整数。它们的初始值都是 0。它们在旧版本的代码中用于为内部循环的每次迭代提供变化的值。我所要做的就是在每次循环迭代中将它们向上增加一个，然后 JVM 将被迫忠实地执行每个操作。不幸的是，这个循环显然阻止了 SIMD 的使用。每次外部循环迭代时，int1 和 int2 都会重置它们的值以防止 int1、int2 或 int3 溢出（我发现整数溢出会不必要地减慢代码速度，就像允许浮点数达到无穷大一样）。

tempint4/tempint5：这些是对在程序的主类文件中定义的一对整数数组的引用（Mathtester。是的，我知道这很缺乏想象力）。当程序第一次启动时，有一个短的 do/while 循环，用 1-1025 的随机整数填充每个数组。数组大小为 128 个整数。每个数组都是静态的，尽管引用变量不是。事实上，我没有特别的理由使用参考变量。它们是我尝试进行数组引用交换时的剩余部分，因此，在外循环的每次迭代之后，tempint4 和 tempint5 将被引用到相反的数组。我希望 JVM 不再忽略我的代码块。对于支持除法的代码版本，这似乎有效（有点），因为它从根本上改变了要计算的值。

编辑：使 tempint4 和 tempint5 （因为它们只是参考变量，我实际上指的是主数组，Mathtester.int4 和 Mathtester.int5） volatile 在没有显着降低 CPU 活动量或级别或 CPU 温度的情况下工作。它确实使代码变慢了一点，但这可能表明 JVM 的 NOOPing 比我所知道的要多。

我目前正在做一个项目，每个周期都很重要。在分析我的应用程序时，我发现一些内部循环的开销非常高，因为它们只包含一些机器指令。此外，这些循环中的迭代次数在编译时是已知的。

因此，我认为与其使用复制和粘贴手动展开循环，不如使用宏在编译时展开循环，以便以后轻松修改。

我的形象是这样的：

这样我就可以替换for (int i = 0; i < N, ++i) { do_stuff(); }为：

它会自行展开：

由于 C 预处理器在大多数时候对我来说仍然是一个谜，我不知道如何实现这一点，但我知道这一定是可能的，因为 Boost 似乎有一个BOOST_PP_REPEAT宏。不幸的是，我不能在这个项目中使用 Boost。

我在搜索时找到的介绍性链接：

1. 6.59.14 循环特定的编译指示
2. 2.100 Pragma Loop_Optimize
3. 如何向 gcc 提供有关循环计数的提示
4. 告诉 gcc 专门展开一个循环
5. 如何在 C++ 中强制向量化

正如您所看到的，它们中的大多数都是用于 C 的，但我认为它们也可能适用于 C++。这是我的代码：

我使用了上面可以看到的所有提示，但我没有得到任何加速，如示例输出所示（第一次运行未注释此#pragma GCC ivdep Unroll Vector：

有希望吗？或者优化标志O3就可以了？欢迎任何加速此代码（foo函数）的建议！

我的 g++ 版本：

请注意，循环的主体是随机的。我对以其他形式重写它并不感兴趣。

编辑

回答说无能为力也是可以接受的！

一年前我参加了计算机组织课程，现在我将其作为“计算机体系结构”进行跟进，我正在使用 John Hennessy 的《计算机体系结构的定量方法》一书的第三版，我通过了 MIPS ISA但仍需要一些帮助，你能更详细地解释一下这行代码吗？

源代码：

汇编代码：

这是作为循环展开以利用 ILP 的示例给出的，我有一些疑问。我确实知道数组从 Mem[0+R1] 开始并向后直到 Mem[R+8](如文中给出) ，这是什么原因，或者他们只是随机取了这个位置？

另外，当我们添加有符号数 (-8) 时，为什么要使用 DADDUI (unsigned ) ？

请对此进行详细概述，以便我可以关注其余主题。谢谢

是否可以在三角形区域上展开循环，例如：

其中 ROW_LENGTH 是在编译时定义的常量？就目前而言，我认为这是不可能的，因为 i 在程序执行时会发生变化（更重要的是，它在编译时不是一个常数）。我想您可以将 2D 数组视为 1D 数组，从 0 迭代到 (ROW_LENGTH^2)/2，然后尝试一些数学技巧来获取索引，但是额外的操作会破坏循环展开的目的第一名。

我在展开嵌套for循环时遇到问题。我理解这个概念，我正在尝试将其付诸实践，但是我在编辑for循环中的语句以匹配展开时遇到了麻烦。

如果有人可以向我展示一个有效的展开并引导我完成它，那将是一个巨大的帮助。

这是我要展开的循环部分：

更新：这是正确的吗？

当我找到选项时，我正在阅读GCC 的优化-funroll-all-loops选项。

它的描述如下：

展开所有循环，即使在进入循环时它们的迭代次数不确定。这通常会使程序运行得更慢。“-funroll-all-loops”暗示与“-funroll-loops”相同的选项

如果在编译时它的迭代次数未知，编译器如何展开循环？编译器不需要这些信息来展开它吗？它会生成哪些相应的 C 代码，如果它通常会使程序运行得更慢，这在什么情况下会有用？

我对编译时循环展开的一般解决方案感兴趣（我在 SIMD 设置中使用它，其中每个函数调用需要特定数量的时钟周期，并且可以并行执行多个调用，所以我需要调整数字累加器以最大程度地减少浪费的周期——添加额外的累加器和手动展开会产生显着的改进，但很费力）。

理想情况下，我希望能够写出类似的东西

并生成以下内容：

到目前为止，我有三种不同的模板元程序解决方案，我想知道不同方法的优缺点是什么，特别是关于编译器如何内联函数调用。

方法1（递归函数）

调用语法示例：

方法 2（递归构造函数）

调用语法非常难看：

如果使用匿名 lambda，则必须显式指定函数的类型，这很尴尬。

方法3（递归静态成员函数）

调用语法示例：

就语法而言，这第三种方法似乎是最干净和最清晰的，但我想知道编译器如何处理这三种方法是否可能存在差异。