写出高效程序的三个重点：
1：选择一组适当算法和数据结构。
2：编写出编译器能够有效优化，以转化成高效可执行代码的源代码。
3：运算量特别大时，将任务分成多个部分，在多核处理器的某种组合上并行计算。
//代码必须清晰、简洁。
步骤：
①：消除不必要的工作。
让代码有效执行所需任务，消除不必要的函数调用、条件测试和内存引用。（这些优化不依赖于实现机器的硬件）
②：利用处理器提供的指令级并行（Instruction-Level parallelism）能力，同时执行多条指令。
步骤①：不依赖机型底层的优化
阻碍优化原因：
通常gcc编译器会自动优化代码，分为 0, - O1, -O2, -O3，逐级优化更高。
但是遇到妨碍优化因素（optimization blocker）时，会以安全性优先，不进行优化。
此时需要程序员自己编写适合优化的代码。也就是我们的工作。
因素包含：
- 内存别名使用： //关注指针：两个指针可能指向同一内存
如：void fun1(long long *xp,long long *yp) { *xp += *yp; *xp += *yp; } void fun2(long long *xp,long long *yp) { *xp=2 * (*yp); }函数fun1和fun2，看似好像执行同一功能，可以将fun1优化为fun2,减少访问内存次数。
但当 *xp = *yp 时，fun1中 ： *xp最终等于3 * ( *yp)。
编译器会假设指针指向同一位置，因安全性，不会执行优化，所以需要程序员自己手动进行优化。
- 函数调用： //关注函数调用
如：long long f(); long long fun1() { return f()+f()+f()+f(); } long long fun2() { return 4*f(); }fun1和fun2都调用了f()，看似fun1()可以优化成fun2()，仅进行一次函数调用，但是当f()为如下函数时：
long long counter=0; long long f() { return counter++; }此时每次调用，counter会自增1，导致fun1()和fun2()的返回值也不同。
所以编译器由于不知道函数内部结构，出于安全性，也不会进行优化。
此时若调用函数和被调用函数的定义在同一文件中，编译器会使用内联函数替换(inline substitution)的方式进行优化。若不同，如调用库函数时，则无法进行。
- 循环中的函数调用： //关注循环中的函数调用。
void toLower（char *s） //大写字母变成小写 { long long i; for (int i=0;i<strlen(s);i++) { if('A' <= s[i] && s[i] <= 'Z') s[i] -= ('A' - 'a') ; //养成加括号习惯，避免优先级错误。 } }如上述函数调用的原因，编译器也是会多次调用strlen()函数，会导致极大的性能损失，从O(n)→O(n^2)。
此时需要程序员自行进行代码移动（code motion）。
- 循环内部的内存引用: //关注循环中的指针赋值。
void Accumulate(long long *a, long long *dest) //累乘a中元素，值放到dest { *dest = 0; for (int i = 0; i < 5; i++) //简化起见，直接用规定是5元素数组。 { *dest += a[i]; } } //退出循环时，*dest=20； void Accumulate2(long long *a, long long *dest) //累乘a中元素，值放到dest { long long acc = 0; for (int i = 0; i < 5; i++) //简化起见，直接用规定是5元素数组。 { acc += a[i]; } *dest=acc; } //*dest=15；第一个函数中，每次循环内都要读、写内存，按理说，编译器可以将其优化为第二个函数，在汇编语言中，用一个寄存器就可以实现累加，而只需写入一次内存。
然而，由于内存别名使用，假设：
数组长度为5，dest=&a[4]，则两个函数所得到的结果变会不同。
令a={1,2,3,4,5};
函数体执行完毕时：
第一个函数dest=20，而第二个函数dest=15;
ps：当gcc用-O2优化第一个函数时，得到的汇编语言逆向成c：void Accumulate2(long long *a, long long *dest) //累乘a中元素，值放到dest { long long acc = 0; for (int i = 0; i < 5; i++) //简化起见，直接用规定是5元素数组。 { acc += a[i]; *dest=acc; //只进行一次写入，而减少一次读内存操作。 } }
步骤②：依赖指定机型处理器微体系结构的优化
熟悉机器执行指令的方式：
//暂且重点关注循环内部：
- 优化根据：
1： 了解执行指令时的流水线结构 ；
2：了解流水线中的两个模块：指令控制单元ICU(Instruction Control Unit)、执行单元EU(Execution Unit)
及在执行单元中：不同运算单元的延迟(latency)、发射时间(issue time)、容量(capacity)及加载单元的容量。
3：分析找到关键路径(critical path)，利用循环展开、多个积累变量、重新结合变换等方式并对其进行优化。
4：根据gcc指令中的AVX向量指令提供的向量并行性，更大优化。
总说：
通常标准gcc编译器，在高优化级时，且循环内没有函数调用、内存别名使用等问题时，会执行循环展开、多个积累变量的优化（仅针对整数）、重新结合变换的优化。
所以要注意将函数、多指针的模块，尽量提到函数外，适应编译器的优化。
- 举例：Intel Core i7 Haswell中的功能单元数及不同运算的延迟：
说明：以每元素周期CPE（Cycles Per Element）为单位.
//元素指循环中、要被操作的数。如for(int i=0;i<n;i++) a[i]=i; 元素就是指a[i]。
//不用循环来代替元素，是因为循环次数可变：如for(int i=0;i<n:i+=2) a[i]=i;a[i+1]=i+1；而待处理元素是不变。
i7总共有8个功能单元，有的单元集成多个操作。
CPE 整数加减 整数乘法 浮点数加 浮点数乘 整数除法 浮点数除 延迟 1 3 3 5 3~30 3~15 发射 1 1 1 1 3~30 3~15 容量 4 1 1 2 1 1 此外，内存加载单元有2个，内存存储单元有1个，地址计算有3个，分支有2个。
- 关键路径：
关键路径：执行一组指令（一次循环），所需要时钟周期的下界。
优化的思想，即是最大化减少关键路径所需时间周期。
通过分析循环内c代码及汇编代码，优化代码使关键路径时间最短。
然后可以利用循环展开、多个积累变量、重新结合变换进行下一步优化。
- 循环展开：
方法：通过减少循环次数，增加每次循环的操作量来进行。
可减少次数：索引计算、条件判断、循环跳转等。
且多个运算时，元素增多，但关键路径的时间可以不变，此时便可大大减少CPE。
for( int i=0 ; i<n ; i++ ) { ... }
// 设将循环展开为k位，则循环终止条件，变为n-k（避免数组越界，留出k位），每次增量为k;
// 变为:
for( int i=0 ; i<n-k ; i += k )
{ .../*内部每次处理k个元素*/... }
for( ; i<n ; i++)
{ .../*继续处理后续的0~k位*/... }
- 多个积累变量：
方法：在形如累加、累乘的循环中，将积累变量扩充为多个，循环完后，再进行合并，增加了并行性。如分为i=奇、i=偶。
for( int i=0 ; i < n ; i++)
{ a[i] * = i ; }
//变为：
int e=1,o=1;
for( int i=0 ; i < n ; i++)
{
e *= i ;
o *= i+1;
}
a[i] = e * o ;
for( ; i < n ; i++)
{ a[i] *= i ; }
注意：整数运算具有交换律和结合律，但是浮点运算时，不具备，所以参考到如果奇数全是极大数、偶数全是接近于0时，如果是正常运算，则是正常。但奇、偶分开积累时，可能会导致上溢、和下溢。但通常情况下，一般的数据都不会出现这种情况。是可以应用的。针对实际自行判断。
- 重新结合运算：
方法：重新调整循环内运算的顺序，减少关键路径周期。
如：
for(...)
{ acc = (acc*data[i]) * data[i+1] ; }
//变为：
for(...)
{ acc = acc * (data[i]*data[i+1]) }
这样的变换，会减少acc的关键路径时间。
- 向量拓展：
利用AVX(高级向量拓展)的指令，可以在%ymm寄存器（256位）中，一次可以读8个32位或者4个64位。
大大加快了速度。但AVX指令集不包括64位整数乘法的并行指令。
