阶乘算法优化

__attribute__((noinline))
int test(int n)
{
        int fact = 1, num = n + 1;
        int i =1;
        for (i = 1; i < num; i++) {
                fact *= i;
        }
        return fact;
}
int main()
{
        printf("%d\n", test(1000000000));
}

为方便分析，函数calc()前面加上__attribute__((noinline))，禁止GCC把calc内联在main()中。此外，calc()中，fact类型是int，main()中调用calc(1000000000)，会导致fact溢出，但不影响测试，不用管它。

编译一下，然后用time命令测量下运行耗时：

[root@localhost ~]# gcc jiecheng.c -o jiecheng
[root@localhost ~]# time ./jiecheng
0
 
real    0m25.159s
user    0m25.160s
sys     0m0.000s

用时25s

#include 
int test(int n)
{
        int fact0 = 1,fact1 = 1,fact2 = 1,fact3 = 1;
        int i =1;
        for (i = 1; i < n; i+=4) {
                fact0 *= i;
                fact1 *= i+1;
                fact2 *= i+2;
                fact3 *= i+3;
        }
        return fact0 * fact1 *fact2 * fact3;
}
int main()
{
        printf("%d\n", test(1000000000));
}

注意：这里为方便讲解，假设n总是4的倍数。如果要处理n不是4的倍数的情况，只需要在主循环体外，增加一个小的循环单独处理最后的n%4个数，也就是最多3个数即可，对整体性能影响几乎为0.

编译一下，然后用time命令测量下运行耗时：

[root@localhost ~]# time ./jiecheng2
0
 
real    0m9.067s
user    0m9.066s
sys     0m0.004s

运行耗时从原来的25秒降到了9秒，性能提升了！你以为这就完了？

这还不是最终的结果，因为我们还有一个优化技巧还没加上，最终优化后的结果是0.3秒！文末会讲！先不着急，咱们一个一个来讲！

关于循环展开：你真的理解吗？

看到这里，有人会说，不就是循环展开嘛，很简单的，没什么好研究的，而且加了优化选项之后，编译器会自动进行循环展开的，没必要手动去展开，也就没有研究的价值了！

真的是这样吗？先尝试回答下面几个问题：

1. 循环展开为什么能提高程序性能，其背后的深层次原理是什么？

2.  循环随便怎么展开都一定可以提高性能吗？

3. 用了优化选项，编译器一定会帮我们自动进行循环展开优化吗？

第一个问题后面会详细讲解，我们先用实例回答下第2个和第3个问题。

先看第2个问题。

循环随便展开都能提高性能吗？

我们把jiecheng_2.c稍微改一下，命名为jiecheng_3.c：

#include 
int test(int n)
{
        int fact=0;
        int i =1;
        for (i = 1; i < n; i+=4) {
                fact *= i;
                fact *= i+1;
                fact *= i+2;
                fact *= i+3;
        }
        return fact;
}
int main()
{
        printf("%d\n", test(1000000000));
}

仍然是循环展开，只不过把循环展开的方式稍微改了一下。再编译一下，用time命令测量下运行耗时：

[root@localhost ~]# time ./jiecheng3
0
 
real    0m17.095s
user    0m17.090s
sys     0m0.004s

和jiecheng.c相比运行耗时只减少了8秒！为什么同样是循环展开，jiecheng_2.c只需要1.6秒，而jiehceng_3.c却要17秒，为什么性能差异这么大呢？别着急，后面细讲。

再看第三个问题，加了优化选项，编译器一定会帮我们自动进行循环展开优化吗？一试便知

O3，编译器一定会循环展开吗？

重新编译下test.c, test_2.c, 和test_3.c，只不过，这次我们加上-O3优化选项，然后分别用time命令再测量下运行时间。

先是test.c：

[root@localhost ~]# gcc jiecheng.c -o jiecheng -O3
[root@localhost ~]# time ./jiecheng
0
 
real    0m3.457s
user    0m3.453s
sys     0m0.004s

加了-O3优化后，程序耗时从原来的25秒降到了3秒，性能提升确实非常明显！是否好奇，-O3选项对test.c做了什么样的优化，能够把程序耗时降到八分之一？这个后面再讲。

现在，我们先试下test_2.c：

[root@localhost ~]# gcc jiecheng_2.c -o jiecheng2 -O3
[root@localhost ~]# time ./jiecheng2
0
 
real    0m1.011s
user    0m1.008s
sys     0m0.004s

同样，加了-O3后，程序耗时从原来的9秒降到了1秒！此外，在同样加了-O3的情况下，使用了循环展开的test_2.c，程序耗时仍然是test.c的八分之一！可见，编译器确实优化了一些东西，但是，无论是否加-O3优化选项，进行手动循环展开的test.c仍然是性能最好的！

最后，再试下test_3.c:

[root@localhost ~]# gcc jiecheng_3.c -o jiecheng3 -O3
[root@localhost ~]# time ./jiecheng3
0
 
real    0m0.004s
user    0m0.000s
sys     0m0.004s

看到了吧？同样加了-O3优化选项的前提下，性能仍然与test_2.c相差甚远！（我这里测试的结果与文章的不一样），也是与CPU有关，这里使用的是龙芯Loongson-3A R3 (Loongson-3B3000) @ 1450MHz

小结一下我们现在得到的几组测试结果：

        jiecheng.c                jiecheng_2.c        jiecheng_3.c

-O0        25.159秒            9.075秒                  17.054秒      

-O3        3.463秒               1.008秒                 0.0003秒

原谅链接

改几行代码，for循环耗时从3.2秒降到0.3秒！真正看懂的都是牛人！