loop optimize

背景问题

如果要进行1-10000的累乘，该如何实现？
最常见的做法就是使用for循环，那么for循环是否能进行优化呢，提升到极致的性能会是什么样子呢。

实现

为了避免编译器过度，我们使用Debug模式进行性能分析。

• 方法一

1
2
3
4
5

int sum = 1;
for (int i = 1; i <= 10000; i++)
{
	sum *= i;
}

这是最基础的for循环执行10次的性能。接下来我们开始对其进行优化。

• 方法二

方法一中每次计算需要进行一次循环判断，总的指令数量为10000次循环控制指令+10000次计算指令。
通常对for循环进行性能优化的办法是循环展开，即在一次循环中进行多次计算，减少循环控制相关指令的数量，使有效的计算指令的占比提升。因此在 方法二中我们减少循环指令的占比，在一次循环中进行4次计算。

1
2
3
4
5
6
7
8

int sum = 1;
for(int i = 1; i <= 10000; i+=4)
{
	sum *= i;
	sum *= i+1;
	sum *= i+2;
	sum *= i+3;
}

这次的循环指令数量为2500次，10000次计算。
可以看到，这次的for循环性能相比于 方法一有了一定的提升，但是总体来说提升并不大，我们先不进行过度深入的理解，就当作循环指令的开销比较小，所以单纯减少循环指令对性能的提升并不明显。

这里首先理解一下循环展开是为了什么，单纯的减少本身就开销比较小的控制指令，以此来优化性能？也许并不是！

这里就需要了解下现在处理器的一个特性，就是能够在一个始终周期内执行多条指令，本文中不做详细展开，可以先通过这篇文章了解一下这一特性 <<指令流水线>>.

• 方法三

现在我们来实现一个可以利用处理器指令流水线特性的for循环代码。

1
2
3
4
5
6
7
8
9

int sum0=1, sum1=1, sum2=1, sum3=1;
for (int i = 1; i <= 10000; i+=4)
{
	sum0 *= i;
	sum1 *= i+1;
	sum2 *= i+2;
	sum3 *= i+3;
}
return sum0*sum1*sum2*sum3;

可以看到，利用了指令流水线后，程序的性能是大幅度提升的，并且这是没有进行编译器优化的代码。

总结

所有软件都是在硬件的基础上运行的，所以，如果想要写出非常高效的代码，那么就必须得熟悉或者说对计算机体系结构有所了解，否则就没法使代码达到极致的性能。

同样利用硬件特性的程序，在多线程程序中也有体现，可以看看下一篇 多线程程序性能优化.