这个C/C++循环能够被优化到什么程度？

Question

我是一个优化方面的新手。我一直在阅读一些有关如何优化c++代码的参考资料，但我很难将其应用到实际代码中。因此，我只想收集一些现实世界的优化技巧，以从下面的循环中尽可能地挤出CPU /内存的最大效益。

double sum = 0, *array;
array = (double*) malloc(T * sizeof(double));
for(int t = 0; t < T; ++t){
sum += fun(a,b,c,d,e,f,sum);
*(array+t) = sum;
}

其中a,b,c,d,e,f都是double类型，T是int类型。欢迎使用任何与内存对齐、并行性、OpenMP/MPI以及SSE指令有关的方法。编译器为标准gcc、Microsoft或常见的编译器。如果解决方案是特定于编译器的，请指定编译器及与解决方案相关的任何选项标志。

谢谢！

PS：忘记提到属性fun。请假定它是一个没有循环且只由基本算术运算组成的简单函数。请把它看作是一个内联函数。

EDIT2：由于fun的细节很重要，请忘记参数c、d、e、f，并假设fun被定义为

inline double fun(a,b, sum){
return sum + a* ( b - sum);
}

- leon

---

要进行优化，通常需要知道哪些代码值得优化。如果不知道fun(...)的作用或者T在实际情况下可能有多大，那么这个问题实际上没有什么用处。 - Joe

函数调用开销将超过任何循环优化（除非进行内联）。在测试之前进行微小优化是不明智的。 - Mitch Wheat

为什么要使用*(array+t)而不是更清晰的等效表达式array[t]？ - kennytm

编写难以阅读的代码应该会让你被解雇。叹气 - Michael Kristofik

这段代码进行过性能分析吗？你知道循环是问题所在吗？你知道 fun() 不是问题所在吗？一旦你对代码进行了性能分析，你就能更好地进行优化。如果你不进行性能分析，那么你的“优化”只是瞎猜。 - Liz Albin

Answer 1

由于sum以一种非常复杂的方式依赖于其先前的值，因此无法并行化代码（因此OpenMP和MPI不适用）。

内存对齐和SSE应该在适当的编译器设置下自动执行/使用。

除了通过编译-O3来内联fun和展开循环之外，如果fun是完全通用的，则没有太多可做的。

---

由于fun(a,b,sum) = sum + a*(b-sum)，我们有闭式形式

            ab             t+1
array[t] = ———— ( 1 - (2-a)    )
            a-1 

这段代码可以进行向量化和并行化，但是除法和乘方的计算代价很高。

尽管如此，通过以上的封闭形式，我们可以从任意索引开始循环，例如创建两个线程，一个从t=0到T/2-1，另一个从t=T/2到T-1，执行原始的循环，但初始的sum使用以上的封闭式解决方案来计算。此外，如果只需要数组中的少数值，则可以进行惰性计算。

对于SSE，您可以首先使用(2-a)^(t+1)将数组填充，然后对整个数组应用x :-> x - 1，然后对整个数组应用x :-> x * c，其中c = a*b/(1-a)，但可能已经有自动向量化。

- kennytm

---

当他没有告诉我们fun(a,b,sum)的功能时，你如何在代数上操作它？ - phkahler

最好能够对“非常昂贵”进行一些量化——通常情况下，我发现除法的开销大约是乘法的5倍，而指数运算的开销则大约是50倍。 - Rex Kerr

请注意，a-1是一个常数，也是一个双精度浮点数。因此，1/(a-1)可以预先计算。指数是t的幂，其中t是常数，因此需要O(log t)的时间。尽管如此，整个计算仍然需要O(T log T)的时间。 - MSalters

Answer 2

您上面的代码已经是尽可能快的了。

• 内存对齐通常由malloc处理得足够好。
• 该代码无法并行化，因为f是先前总和的函数（因此您无法将计算分成块）。
• 未指定计算方式，因此不清楚是否适用于SSE、CUDA等技术。
• 同样，不能根据f的属性执行任何有用的循环展开，因为我们不知道它具体执行什么操作。

（从风格上来看，我会使用array[t]，因为这样能更清楚地表达意义并且速度不会更慢。）

---

编辑：既然有了f(a,b,sum) = sum + a*(b-sum)，我们可以手动尝试循环展开，看看是否存在某种模式。就像这样（其中我使用 ** 表示“次方”）：

sum(n) = sum(n-1) + sum(n-1) + a*(b-sum(n-1)) = (2-a)*sum(n-1) + a*b
sum(n) = (2-a)*( (2-a)*sum(n-2) + a*b ) + a*b
. . .
sum(n) = a*b*(2-a)**n + a*b*(2-a)**(n-1) + ... + a*b
sum(n) = a*b*( (2-a)**0 + (2-a)**1 + ... + (2-a)**n )

哇，现在这很有趣！我们已经从递归公式转换为几何级数了！你可能还记得，几何级数

SUM( x^n , n = 0..N ) = (x**(n+1) - 1) / (x - 1)

为了让...

sum(n) = a*b*( (pow(2-a,n+1) - 1) / (1-a) )

现在你已经完成了这个数学问题，你可以从任何地方开始计算总和（使用稍微昂贵的pow计算）。如果你有M个空闲处理器，并且你的数组很长，你可以将它分成M个相等的部分，使用上述计算来找到第一个总和，然后使用你之前使用的递归公式（带有函数）填充其余内容。

至少，你可以分别计算a*b和2-a，然后使用它们代替现有的函数。

sum = ab + twonega*sum

这将使你内部循环中的计算量减半，大约。

- Rex Kerr

Answer 3

可以进行一个非常小的优化：

double sum = 0, *array;   
array = (double*) malloc(T * sizeof(double));
double* pStart = array;
double* pEnd = array + T;
while(pStart < pEnd)
{
    sum += fun(a,b,c,d,e,f,sum); 
    *pStart++ = sum; 
}

这将消除循环的每次迭代中将t添加到数组中的步骤，将t的增量替换为pStart的增量。对于小规模的迭代（少于3个），没有真正的收益，此时应该展开循环。编译器应该会自动完成这一点，但有时需要一些鼓励。

此外，根据T的大小范围，可能可以通过使用变量大小的数组（它将被堆栈分配）或对齐的_alloca来提高性能。

- Necrolis

---

许多处理器实际上在存储之前不添加T，它们使用寄存器间接寻址，在时钟周期内执行指令中的加法，例如str r1，[r2，r3]。所以效果相当。有些处理器中，销毁移动指针是更快的。 - old_timer

当然，你可以使用ARM作为示例，执行“str r1，[r2]，＃8”并在一条指令中完成破坏的指针及其增量，而寄存器间接需要两个。通常情况下，指针解决方案和索引数组解决方案在性能上相当，除非你针对特定处理器，对于大多数人来说，索引数组解决方案更易于阅读和维护。我们所做的只是在这里节省了一个或两个指令，“fun()”加上调用设置将占用消耗时间的主导地位。 - old_timer

Answer 4

除非fun()非常简单 - 在这种情况下，请考虑使用内联，否则它很可能会支配您在循环中所做的任何其他操作。

您可能希望查看fun()内部的算法。

- user280760

Answer 5

接受 @KennyTM 的答案。他错误地声称计算不可并行化，但随后证明了这一点。通过展示你可以将递归关系式重写为封闭形式，他阐述了一个非常普遍的优化程序原则——选择最好的算法并实现它。其他答案提出的微观优化都无法接近计算封闭形式并将计算分布到许多处理器上的水平。

还有，如果有人建议这只是学习并行化的示例，我认为 @KennyTM 的答案仍然正确——不要只学习优化代码片段，而是学习优化计算过程。选择最适合您目的的最佳算法，良好实现它，然后再考虑性能问题。

- High Performance Mark

---

我认为“为你的目的选择最佳算法，实现它并且只有在那之后才担心性能”这句话是误导性的。毕竟，我们选择最佳算法的整个原因就是因为我们担心性能。 - John Dibling

考虑到指数计算的成本，如果你采用朴素的方式将其分解，则需要100多个处理器才能超过一个处理器的吞吐量。你不需要闭合形式——你需要使用闭合形式进行初始化，然后使用更新速度快50倍以上的递归公式。 - Rex Kerr

@Rex - 的确，我认为许多人都会借口“过早优化是万恶之源”来批评所有的优化尝试，而不仅仅是微观优化。 @Mark - 通过简单地移植到CUDA，可以轻松利用数百个核心。 - John Dibling

@HPM：是的；我在回答问题时暗示了这一点，而且我也可以访问100多个处理器。但我可能想要将我的100多个处理器用于需要100多个处理器的任务，而不是不需要的任务。@John：确实，人们也经常隐藏在“走开，使用分析器”的答案后面。好建议，没错，但这不是唯一的好建议。 - Rex Kerr

@HFM 这篇文章的目的是让我学习低级别优化。我的问题中经常出现的递归函数关系比这个更复杂，作为一个有数学背景的人，我总是试图找到更好的公式。这个问题被设计成通用的，以便人们可以讨论低级别优化技术，这些技术可能会有所帮助。我不是在寻求解决这个特定问题的解决方案，而是一组技术，可以在分析后用来改进我的代码。谢谢 :) - leon

Answer 6

看看valgrind工具集中的callgrind。通过它运行你的代码，看看是否有任何需要花费异常长时间的地方。然后你就会知道需要优化什么。否则，你只是在猜测，而且你（以及我们其他人）很可能猜错。

- Michael Kristofik

Answer 7

我会在编译器上启用向量处理。你可以重写代码以打开循环，但编译器会为你完成。如果是较新的版本。

你可以使用 t+array 作为 for 循环增量...再次优化器可能会这样做。 这意味着你的数组索引不会再使用乘法，优化器可能会这样做。

你可以使用 switch 来转储生成的汇编代码，然后看看你可以改变什么来使代码运行更快。

- AnthonyLambert

---

但是fun是sum的一个函数，因此它不能移出循环。 - leon

我忍不住觉得，如果我们知道它是做什么的，这就是可以优化的地方。 - AnthonyLambert

Answer 8

这里有几个建议，可能还没有被提到。我对现代PC处理器有点过时了，所以它们可能没有什么显著的区别。

• 如果您可以容忍较低的精度，则使用float可能比double更快。基于整数的定点可能会更快，具体取决于浮点运算的流水线程度。
• 从T倒数到零（并在每次迭代中递增array）可能会稍微快一些-在ARM处理器上，这肯定会节省一个循环周期。

- Mike Seymour

---

在当今的FP ALU中，float和double操作通常同样快...节省通常体现在更高的缓存命中率上 :-) - fortran

我从事的领域不接受浮点数 :( - leon

Answer 9

另一个非常小的优化是将for()转换为

while (--T)

因为与零比较通常比与两个随机整数比较更快。

- ggiroux

Answer 10

在@KennyTM的出色回答之后，我认为按顺序执行它的最快方法应该是：

double acc = 1, *array;
array = (double*) malloc(T * sizeof(double));
// the compiler should be able to derive those constant expressions, but let's do it explicitly anyway
const double k = a*b/(a-1);
const double twominusa = 2 - a;
for(int t = 0; t < T; ++t){
    acc *= twominusa;
    array[t] = k*(1-acc);
}

- fortran