问题标签 [loop-unrolling]

我正在制作一个 XNA 游戏，我想知道是否有优化某些循环的方法。例如：

我有一个 Map 类，其中包含一组图块，因此，在 Map Update() 中，我只调用每个图块 Update()

这可以正常工作，但是对于一些较大的填充对象可能会变得最糟糕，例如 Particle 类，其中每个粒子都由 ParticleManager 类（包含粒子集合）管理，因此：

ParticleManager 为每个粒子循环，每个粒子检查每个 Tile 的碰撞。所以，如果你有 20 个粒子和 100 个 Tiles，它将进行大量计算：

这就是为什么我在考虑一些优化，比如循环展开但是，我不知道它是否适用于未定义长度的循环（我认为不是）（因为编译器在编译时不知道这些循环的长度）

总结一下：

1. 可以使用循环展开来优化这些循环吗？
2. 您能建议我进行任何其他类型的优化吗？

谢谢

我有一个 CUDA 内核，里面有一堆我想展开的循环。现在我做：

等等。我想告诉（提示）我的 C/C++ 编译器展开所有这些循环，而不需要为每个循环单独提示。但是，我不想展开文件中所有代码中的所有循环，只是在这个函数中。

如果这是 GCC，我可以这样做：

或使用选项推送和弹出。我可以用 CUDA 做一些等效的事情吗？

我假设每个人都知道“展开循环的含义”。以防万一我稍后会给出一个具体的例子。我要问的问题是...... x86-64 汇编语言中的展开循环真的可以让代码更快吗？我将解释为什么我开始质疑这个概念。

对于那些不熟悉“展开循环”一词的人，这里是我现在正在编写的代码中的一个循环示例：

这是该循环展开的样子：

我应该注意到，上面的例子是有代表性的，但可能不是这个讨论的最佳选择。原因是大量的条件分支。虽然我相信“未采用分支”与其他指令类似，但在某些情况下该假设可能不正确（这可能是模糊的）。因此，如果这方面是相关的，我们可以假设这两个条件分支只是简单的指令，如movq或addq用于此讨论（尽管如果不同，则分别处理这两种情况是可取的）。

哦，最后两个条件：

#1：这个问题只适用于在单线程上运行的代码。

#2：这个问题仅适用于快速的现代 ~4GHz CPU（FX-8350 等）。

好的，现在让我质疑展开循环是否真的明智的想法。

这些新处理器的运行频率为 4GHz，有时每个周期可以执行两到三条指令。在我上面的代码中，前 2 条指令不能并行执行，可能最后 3 条指令也不能。但是带有可以并行执行的指令的循环只会使我的问题更加相关。

因此，每条指令可以在 0.25 纳秒内执行（或者对于并行执行的指令来说更短）。这意味着执行 4 条指令需要 1 纳秒。每组 4 条指令大致消耗 16 字节，我假设它是高速缓存行的 1/4。因此，4 组 4 行应该需要 4ns 来执行，此时它已经退出缓存行并需要另一个。

这就是问题变得更加复杂的地方。

因此，在 16 条指令和整个展开循环的 1/4 之后，CPU 需要执行更多指令。如果 CPU 正在运行代码的循环版本，它将再次执行完全相同的指令，这些指令肯定仍然在 L1 缓存中，因此继续执行全口径 CPU 速度。

但是，我们是否可以合理地期望 CPU 仅在 4ns 内加载下一个缓存行？或者在可以并行执行的指令的情况下，我们是否可以合理地期望 CPU 仅在 2ns 内加载下一个缓存行？

根据我对动态 RAM 的了解，这似乎……很紧。我知道当 CPU 访问连续地址时，它可以使 RAS（高地址位）保持锁定状态，并使用 CAS 更快地输出连续的 64 位或 128 位内存块。但是，我们真的可以期望 CPU 在 2ns 或 4ns 内读取 64 字节吗？即 4 或 8 个从 DRAM 读取周期，具体取决于 CPU 每次读取操作是读取 64 位（8 字节）还是 128 位（16 字节）。

我的具体代码可能会进一步解决这个问题。根据该算法的性质，我的代码需要首先比较分子和分母的最重要部分，然后在每次访问时向下处理较低的地址。这是否会使自动预取不太可能起作用？

我见过很多人测试循环与展开循环。但是我看到的每一个实例都有一个致命的设计缺陷。它一遍又一遍地调用相同的例程......通常是数百万次......为了获得足够大的计时器值来理解。可是等等！像大多数应用程序一样，代码可能只是偶尔调用我的 1024 位除法函数。这与我看到的这些测试完全不同，它们本质上确保指令都保留在 L1 指令高速缓存中，并且访问的数据保留在 L1 数据高速缓存中。

当然，如果您确保代码和数据已经在 L1 缓存中，展开循环会更快！呸！

这些不是具有代表性的测试——甚至没有接近！

这些测试确实测量了“最佳情况下的性能”，但根本无法代表正常的程序执行。但是要决定如何最好地编写 64 位汇编语言代码（或编译器的代码发射器部分），我们需要在我们的前提下更加现实。或者至少我是这么认为的，这就是我问这个问题的原因。

有没有人以彻底和现实的方式解决过这些问题？

如果我调用函数

使用静态数组，D 会foreach在发布模式下自动为我展开吗？

如果不能

用于实现展开而不是foreach？

此外，DMD 是否有一个生成汇编代码的标志，以便我自己将来可以调查 DMD 生成的代码？

更新：到目前为止，这是我的解决方案。

它看起来好吗？

我是 CUDA 的新手，我无法理解循环展开。我写了一段代码来理解这项技术

以上是我的核函数。在main我这样称呼它

这是否意味着我有size* size=10000 个线程正在运行来执行程序？展开循环时是否创建了 100 个？

我有一个 O(N^4) 图像处理循环，在对其进行分析后（使用 Intel Vtune 2013），我发现退役指令的数量大大减少了。我需要帮助来理解多核架构上的这种行为。（我使用的是 Intel Xeon x5365- 有 8 个内核，每 2 个内核共享 L2 缓存）。并且分支错误预测的数量也急剧增加！/////////////EDITS/////////// 我的非展开代码示例如下所示：

我通过 4 次迭代展开最里面的循环。（你将有一个一般的理想我如何剥离循环。基本上我创建了一个 Array[4] 数组并在其中填充了相应的值。）做数学，我将总迭代次数减少 75%。假设每个循环有 4 个循环处理指令（加载 i、inc i、cmp i、jle 循环），展开后的指令总数应减少 (256-64)*4*256*256*496=24.96G . 分析结果如下：

no instr 退休减少了 518.06G 。我不知道这是怎么发生的。我将不胜感激有关此的任何帮助（即使它发生的可能性很小）。另外，我想知道为什么分支错误预测会增加。提前致谢！

我有一个 496*O(N^3) 循环。我正在执行一种阻塞优化技术，我一次操作 2 个图像而不是 1 个。在原始术语中，我正在展开外循环。（代码的非展开版本如下所示：）顺便说一句，我使用的是 Intel Xeon X5365 机器，它有 8 个核心，它有 3GHz 时钟，1333MHz 总线频率，共享 8MB L2（每 2 个核心共享 4MB） ，L1-I 32KB，L1-D 32KB。

我使用 Intel Vtune-2013（使用从 gcc-4.1 创建的二进制文件）分析了结果，我可以看到内存带宽使用量减少了 40%，这是预期的，因为每次迭代都会处理 2 个图像。（f_L 存储操作导致每个体素 8 字节的流量）。这占总线周期减少 11.7%！此外，由于在内部循环中增加了块大小，资源停顿减少了 25.5%。这两个占响应时间减少 18%。神秘的问题是，为什么退休的指令增加了 7.9%？（这导致响应时间增加了 6.51%） - 我可以这样做的可能原因是： 1. 由于块内的分支指令数量增加（并且核心架构具有 8 位全局历史）退休的分支指令增加了 2.5% （ 虽然，错误预测保持不变！我知道，闻起来很腥对吧？！！）。但我仍然缺少其余 5.4% 的答案！任何人都可以向我阐明任何方向吗？我完全没有选择，也没有办法思考。非常感谢！！

我正在尝试熟悉汇编程序中的编程。一开始我选择了随机代码并尝试更新它。我还阅读了一些关于循环展开的内容，但我真的不知道从哪里开始。

这是我已经修改了一下的代码：

如何说服 GCC 展开一个迭代次数已知但很大的循环？

我正在用-O3.

当然，有问题的实际代码更复杂，但这里有一个具有相同行为的简化示例：

...如果CONSTANT_COUNT定义为 8（或更少），则 GCC 将展开循环，传播常量，并将整个函数简化为简单的return <value>;. 另一方面，如果CONSTANT_COUNT是 9（或更大），则循环不会展开，并且 GCC 会生成一个二进制文件，该二进制文件会循环、读取常量并在运行时添加它们——尽管理论上该函数仍然可以优化到只返回一个常数。（是的，我查看了反编译的二进制文件。）

如果我手动展开循环，如下所示：

或这个：

...然后函数被优化为返回一个常数。因此，一旦展开，GCC 似乎能够处理较大循环的持续传播；挂断似乎只是让 GCC 考虑首先展开更长的循环。

但是，手动展开也不BOOST_PP_REPEAT是可行的选项，因为在某些情况下CONSTANT_COUNT是运行时表达式，并且相同的代码仍然需要在这些情况下正常工作。（在这些情况下，性能并不那么重要。）

我正在使用 C（不是 C++），所以模板元编程也不constexpr可用。

我已经尝试过-funroll-loops, -funroll-all-loops, , 并为, , , , , ,-fpeel-loops和 设置较大的值，但似乎没有任何区别。max-unrolled-insnsmax-average-unrolled-insnsmax-unroll-timesmax-peeled-insnsmax-peel-timesmax-completely-peeled-insnsmax-completely-peel-times

我在 Linux x86_64 上使用 GCC 4.8.2。

有任何想法吗？是否有我缺少的标志或参数......？

I am trying to see how unrolling is done in GCC. I have written a C code to add elements of an array to do this.

I have compiled it with -o2 flag and -funroll-all-loops.

The object file for the above program has the following assembly code.

In each iteration it is a doing only one addition (7th line in the L3 section) and incrementing the content of rbp register by 1 (as in the last line of L3 section). This indicates that compiler is not unrolling the loop. I was expecting more additions to happen in one loop. My question is, why it is not unrolling the loop even after using the funroll flag?. Is there a possibility that compiler is not optimizing because it thinks that unrolling is not useful in this case ?. If that is true, then what should I do in order to make the compiler unroll the loops ?.