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

Question

有时可以使用关联性来消除数据依赖性,我很好奇它可以提供多少帮助.我很惊讶地发现,通过手动展开一个简单的循环,我几乎可以获得4的加速因子,无论是在Java(build 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所示).

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

^{谷歌搜索不起作用,我只有"关联数组"和"关联运算符".}

更新

我稍微改进了我的基准,现在可以提供一些结果.除了展开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 步骤的循环；在第二种情况下，您手动将第一种情况的两个连续迭代合并为一个，因此在第二种情况下您只需要执行 N/2 步骤。你的第二种情况运行得更快，你想知道为什么愚蠢的编译器不能自动执行它。

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

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

请为我尝试一些事情：

int a = 0;
for (int i=0; i<N; ++i) 
  a = ((a<<5) - a) + t[i];

假设M1=31。原则上，编译器应该足够聪明，可以重写，31*a但(a<<5)-a我很好奇它是否真的做到了这一点。