作为一个性能癖，关于程序优化的奥秘怎能错过？

咱们可以将优化分为三个层次：

　　 1、High-level design：即选择适当的数据结构和算法。

　　2、Basic code principles：注意避免两个optimization blockers，使编译器可以顺利优化。还要注意尽量不要使用连续的函数调用和不必要的内存访问。中间值就不要写入内存了，求得最终值再来写入。

　　3、Low-level optimizations:unroll loops即通过增加每次循环中处理的元素个数以减少迭代次数；通过multiple accumulators（比如说将奇数项和偶数项分开算）或reassociation（类似结合律）来提高instruction-level parallelism。这需要对存储器的微结构有所了解。除此之外，还可以将conditional jump用conditional move代替。

一些概念：

　　 这里衡量性能的标准主要是CPE（cycles per element),即增加一个元素需要相应增加的时钟周期，自然是越小越好。 性能的制约主要有两个：latency bound 和throughput bound，前者是指指令必须按严格顺序执行，这样就限制了处理器对instruction-level parallelism的利用；而后者就关乎你处理器的硬实力了，除了投入更多的人民币以外，我们对它也无能为力 =。=

　　有了parallelism后，多条pipeline可以同时执行。决定性能的关键在于那一条critical path，即在该路径上每一次的迭代必须等前一次迭代执行完才可继续。若要优化自然要抓住這个主要矛盾！ conditional move的好处: 高级语言中类似于if, while, for等语句，对应于汇编中的conditional jump，即jb, jne之类的分支结构。cpu一般会进行branches predictions来发挥其pipeline的作用，而预测都是分支会被执行。一般情况下，比如说 while ( i < n ) 这种，就只有最后一次错误，所以总的来说分支预测能起到不错的优化效果。但是如果使预测正确的可能性不高的情况下，比如说有个数组a[i]，它的元素是任意整数，那么判断条件为if ( a[i] > 0 )时，只有一半的几率正确。这样每次misprediction都要将已经并发执行的指令回退，这些penalities累积起来，后果不堪设想。

　　 解决办法使使用conditional move取代conditional branch。具体如下

优化前代码片段：

void max( int a, int b){　　 int i;　　if ( a > b)　　　i = a;　　else　    　i = b;}

改成：

void max ( int a, int b){　　int i = a > b ? a : b;}

后面这种情况下，处理器会计算出a, b 的值，然后再根据判断条件是否为真来赋给i。虽然要多计算一个值，但是这里的额外开销远小于分支预测错误的额外开销。

write/read dependency:

　　书上写the load unit can only initiate one load operation every clock cycle，所以有内存写入的操作一定要等到前一次内存写入完成。在内存写入后接着进行内存读取自然不是明智的选择。应尽量避免内存的读写依赖。将中间值存在临时变量中，最终值才写入内存。

 

Program Profiling:

　　如果是一个大的程序，我们需要借助一些工具来进行分析，找出可以优化的部分。GPROF可以分析函数调用，我们就可以针对调用次数多或调用周期长的函数进行优化。在linux下可以使用valgrind来分析。

 

　　 最后介绍一个有意思的定律叫Amdahl's Law，这里包含一个计算整体优化度的公式。它主要使说如果我们要提高整体的优化度，必须对大部分都进行优化。对小局部即使进行优化度很高的优化，它能给整体带来的性能提升也非常局限。