使用编译器的关联性有什么问题？

有时可以使用关联性来消除数据依赖性，我很好奇它可以提供多少帮助。 我很惊讶地发现，通过手动展开一个简单的循环，我在Java（build 1.7.0_51-b13）和C（gcc 4.4.3）中几乎可以获得4的加速因子 。

所以我要么做一些非常愚蠢的事情，要么编译器忽略了一个强大的工具。 我开始了

int a = 0; for (int i=0; i<N; ++i) a = M1 * a + t[i]; 

它计算接近String.hashCode()东西（设置M1=31并使用char[] ）。 计算非常简单，对于我的i5-2400 @ 3.10GHz（在Java和C中）， t.length=1000大约需要1.2微秒。

观察到每两个步骤a乘以M2 = M1*M1并添加一些东西。 这导致了这段代码

 int a = 0; for (int i=0; i<N; i+=2) { a = M2 * a + (M1 * t[i] + t[i+1]); // <-- note the parentheses! } if (i < len) a = M1 * a + t[i]; // Handle odd length. 

这恰好是第一个代码段的两倍。 奇怪的是，省略括号可以节省20％的加速时间。 有趣的是，这可以重复，可以达到3.8倍。

与java不同， gcc -O3选择不展开循环。 这是明智的选择，因为它无论如何都无济于事（如-funroll-all-loops显示）。

所以我的问题¹是：什么阻止了这样的优化？

^{谷歌搜索不起作用，我只有“关联数组”和“关联运算符”。}

更新

我稍微改进了我的基准测试 ，现在可以提供一些结果 。 除了展开4次之外没有加速，可能是因为乘法和加法一起需要4个周期。

更新2

由于Java已经展开循环，所有的努力工作都已完成。 我们得到的是类似的东西

 ...pre-loop for (int i=0; i<N; i+=2) { a2 = M1 * a + t[i]; a = M1 * a2 + t[i+1]; } ...post-loop 

有趣的部分可以重写的地方

  a = M1 * ((M1 * a) + t[i]) + t[i+1]; // latency 2mul + 2add 

这表明有2次乘法和2次加法，所有这些都是顺序执行的，因此在现代x86 CPU上需要8个周期。 我们现在需要的只是一些小学数学（即使在溢出或其他情况下也适用于int ，但不适用于浮点数）。

  a = ((M1 * (M1 * a)) + (M1 * t[i])) + t[i+1]; // latency 2mul + 2add 

到目前为止，我们没有获得任何东西，但它允许我们折叠常数

  a = ((M2 * a) + (M1 * t[i])) + t[i+1]; // latency 1mul + 2add 

并通过重新组合总和获得更多

  a = (M2 * a) + ((M1 * t[i]) + t[i+1]); // latency 1mul + 1add 

Answer 1

以下是我理解你的两种情况：在第一种情况下，你有一个循环，需要N步; 在第二种情况下，您手动将第一个案例的两个连续迭代合并为一个，因此在第二种情况下您只需要执行N / 2步骤。 你的第二种情况运行得更快，你想知道为什么哑编译器不能自动执行。

没有什么能阻止编译器进行这样的优化。 但是请注意，重新编写原始循环会导致更大的可执行文件大小 ：在for循环中有更多指令，而for循环之后有更多指令。
如果N = 1或N = 3，则原始循环可能更快 （更少分支和更好的高速缓存/预取/分支预测）。 它使你的情况更快，但在其他情况下它可能会使事情变得更慢。 是否值得进行此优化并不明确，在编译器中实现这样的优化可能非常重要 。

顺便说一下， 你所做的与循环矢量化非常相似，但在你的情况下，你手动完成并行步骤并插入结果。 Eric Brumer的编译器机密演讲将让您深入了解为什么重写循环通常很棘手，有什么缺点/缺点（更大的可执行文件大小，在某些情况下可能更慢）。 因此编译器编写者非常清楚这种优化的可能性，并且正在积极地研究它，但它通常非常重要，也可能使事情变得更慢。

---

请为我尝试一下：

 int a = 0; for (int i=0; i 

假设M1=31 。 原则上，编译器应该足够聪明，可以将31*a重写为(a<<5)-a但我很好奇它是否确实如此。