有时关联性可用于松散数据依赖关系，我很好奇它有多大帮助。我很惊讶地发现，通过手动展开一个简单的循环，我几乎可以获得4 倍的加速因子，无论是在 Java（构建 1.7.0_51-b13）中还是在 C（gcc 4.4.3）中。
所以要么我在做一些非常愚蠢的事情，要么编译器忽略了一个强大的工具。我开始了
int a = 0;
for (int i=0; i<N; ++i) a = M1 * a + t[i];
它计算接近于String.hashCode()（设置M1=31并使用 a char[]）的东西。计算非常简单，t.length=1000在我的 i5-2400 @ 3.10GHz（Java 和 C）上大约需要 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所示）。
所以我的问题1是：是什么阻止了这种优化？
谷歌搜索没有用，我只有“关联数组”和“关联运算符”。
更新
我稍微改进了我的基准测试，现在可以提供一些结果。除了展开 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即使在溢出或其他情况下也可以为s工作，但不适用于浮点数）。
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
以下是我对您的两种情况的理解：在第一种情况下，您有一个需要 N 步的循环；在第二种情况下，您手动将第一种情况的两个连续迭代合并为一个，因此在第二种情况下您只需要执行 N/2 步。您的第二个案例运行得更快，您想知道为什么愚蠢的编译器不能自动完成。
没有什么可以阻止编译器进行这样的优化。但请注意，原始循环的这种重写会导致更大的可执行文件大小：
for循环内有更多指令，循环if后有更多指令。如果 N=1 或 N=3，原始循环可能会更快（更少的分支和更好的缓存/预取/分支预测）。在您的情况下，它使事情变得更快，但在其他情况下可能会使事情变得更慢。是否值得进行这种优化并不清楚，在编译器中实现这种优化非常重要。
顺便说一下，您所做的与循环矢量化非常相似，但在您的情况下，您手动执行了并行步骤并插入了结果。Eric Brumer 的Compiler Confidential talk 将让您深入了解为什么重写循环通常很棘手以及存在哪些缺点/缺点（更大的可执行文件大小，在某些情况下可能更慢）。因此，编译器编写者非常清楚这种优化的可能性，并且正在积极致力于它，但总的来说它非常重要，并且也会使事情变慢。
请为我尝试一些东西：
int a = 0; for (int i=0; i<N; ++i) a = ((a<<5) - a) + t[i];假设
M1=31. 原则上，编译器应该是足够聪明改写31*a成(a<<5)-a，但我很好奇，如果它确实是。