具体的优化主题

使用查找表

即：打表
由于从缓存在一级缓存的列表读取操作只需要花费几个时钟周期，若函数只有有限数量的可能输入，可以用打表来代替函数调用。
例如阶乘函数，由于阶乘只有那么几个数，因此可以直接替换成下面的样子：

int fac(int n) {
    const int table[13] = {1, 1, 2, 6, 24, 120, 720,
        5040, 40320, 362880, 3628800, 39916800, 479001600};
    //转unsigned无任何额外花费，省去一次比较
    if((unsigned int)n < 13) return table[n];
    return 0;
}

表应该被声明为const，以便于启用常量传播和其它优化，还可以将函数声明为内联

使用查找表替换函数，在可能的输入数量有限而且没有缓存问题的大多数情况下有利，如果缓存存在问题，可以将表声明为静态，如果函数计算时间本来就很短，小于加载缓存的时间，就没啥用。

查找表无法使用当前指令集进行向量化，如果这影响使用更快的向量化代码，就不要用查找表。

查找表的原理还可以用于程序在两个或者多个变量之间进行选择的的情况。例如在两常量之间进行选择的分支可以被一个包含两个条目的表替换，如果分支的可预测性很差，这样可以提高性能。

float a; int b;
a = (b == 0) ? 1.0f: 2.5f;

如果b总是0或1，并且可预测性能很差，那么就可以用查找表来代替分支

float a; int b;
const float OneOrTwo5[2] = {1.0f, 2.5f};
a = OneOrTwo5[b & 1];

上面中，b&1只有0or1两种可能， 同时a = OneOrTwo5[b != 0]也可以正确运行，但是这种方法，效率稍低，若b是浮点数，则这种效率实现效率很低，因为编译器中的实际实现还是OneOrTwo[(b != 0)? 1 : 0]，没有拜托分支。若b为浮点数且总是0or1 更好的办法是a = 1.0f + b * 1.5f 但是这不适用于b是整数的情况，因为整数到浮点数的转换很费时间。

将查找表作为switch语句的替代尤其有利，因为switch语句的可预测性很差，例如：

int n;
switch(n) {
    case 0:
        printf("Alpha");
        break;
    case 1:
        printf("Beta");
        break;
    case 2:
        printf("Gamma");
        break;
    case 3:
        printf("Delta");
        break;
}

这种情况就适合用查找表来提高效率：

```cpp
int n;
char const * const Greek[4] = {
    "Alpha", "Beta", "Gamma", "Delta"
}; 
if((unsigned int) n < 4) {
    printf(Greek[n]);
}

表的声明中有两个const，说明指针和指向的内容都是常量。

边界检查

在C++中，通常有必要检查数组索引是否超出范围，一般如下：

const int size = 16; 
float list[size];
if(i < 0 ||  i >= size) {
    cout << "Error: Index out of range";
}
else 
{
    list[i] += 1.0f;
}

上面中，涉及到两个比较，然而可以用一个简单的方法优化掉一个比较：

if((unsigned int) i >= (unsigned int)size) {
    cout <<  "Error: Index out of range";
}

当i被解释为无符号整数时，i可能的负值会变成一个很大的整数，所以可以省去一个比较，因为比较的代价比较大，而从有符号到无符号的转换只是改变了解释方法，不消耗时钟周期也不会产生额外的代码。

这个方法还可以扩展到一般情况：

const int min = 100, max = 110;
int i;
if(i >= min && i <= max) { ... }

可以修改成：

if((unsigned int)(i - min) <= (unsigned int)(max - min)) {...}

如果所需要的的区间长度是2的幂，那么还有一种更快捷的方法来限制整数的范围，例如：

float list[16]; int i;
list[i & 15] += 1.0f;

i&15的值域[0， 15]如果在区间外，例如i = 18，&运算符将i的二进制截断为四位，结果是2，这种情况下与i % 16相同，类似的运算仅适用于区间长度是2的幂的情况

使用位运算一次检查多个值

位运算&, |, ^, ~, <<, >>等可以在一次操作中测试或者操作整数的所有位，算法里面常用的操作了。|运算符可以在一个操作中设置多个为；&操作符可以清楚或者遮掩多个位，^操作符可以一下转换多个位

&操作符还可以用于多个条件的简化，例如：

enum Weekdays {
    Sunday, Monday, TuesDay, Wednesday, ThursDay, Friday, Saturday
};
Weekdays day;
if(day == Tuesday || day == Wednesday || day == Friday) {
    ...;
}

这个if语句就有三个条件，将被实现为三个分支，可以用位运算合并

enum WeekDays {
    Sunday = 1, Monday = 1 << 1, Tuesday = 1 << 2, Wednesday = 1 << 3, 
    Thursday = 1 << 4, Friday = 1 << 5, Saturday = 1 << 6;
}
WeekDays day;
if(day & (Tuesday | Wednesday | Friday)) {
    ....
}

位运算的计算要比布尔运算&&快很多，因为不会产生分支

整数乘法

整数乘法比加法和减法需要更长的时间（3 ~ 10个时钟周期，取决预处理器），编译器优化通常会用一个常量来代替整数乘法，并结合加法和移位操作，乘2的幂要比其它常数快，因为可以通过移位操作完成。例如a * 16可以使用a << 4计算， a * 17可以使用(a << 4) + a计算。 当与常数相乘的时候可以利用和2的幂相乘这个又是，编译器也有快速乘以3、5、9的方法

计算数组的地址时，会有隐式的乘法，无序方式访问二维数数组时，将矩阵列数设置为2的幂有方便计算。
同样的适用于类或结构体的数组，将单对象大小为2的幂对无序访问来说有利
但是顺序访问的时候，这一点并不是很关键，因为可以使用归纳变量优化，这一点对于结构体更是有用，当空间无ok的时候，可以将比如是12字节的结构体再添加一个int弄成16个字节，

设置为2的幂并不总是有利，对于很大的数据结构，设置成2的幂就会带来很多的缓存竞争，如前面所解释的一样

整数除法

整数的除法耗时要比加法减法以及乘法长的多（32位整数的除法需要27 - 80个时钟周期，具体是取决于处理器）

整数除法处于2的幂可以用移位运算来做，这样会快得多。

除以一个常数要比除以一个变量快的多，因为编译器可以通过选择合适的$n$使用公式$a * (2 ^ n / b) >> n$来计算$a / b$ 常量$(2 ^ n/ b)$是被预先计算好的，而且当被除数是无符号数的时候，会快很多。

以下准则可用于改进包含整数除法的代码：

1. 整数除以常数比除以变量快，确保在编译时知道除数的值。
2. 如果常数是2的幂的话，会更快
3. 被除数是无符号数时，整数除以常量会更快

例如：

int a, b, c;
a = b / c; //slow
a = b / 10; //faster
a = (unsigned int) b / 10; //faster
a = b / 16; // faster
a = (unsigned int) b / 16; //faster

同理适用于取模运算。

通过将循环按常数展开，可以避免将循环计数器除以一个常数例如：

int list[300];
int i;
for(i = 0; i < 300; i ++) {
    list[i] += i / 3;
}

可以替换为：

for(int i = 0, j = 0; i < 300; i += 3, j ++) {
    list[i] += j;
    list[i + 1] += j;
    list[i + 2] += j;
}

类似的办法也可以适用于取模运算，若循环不是除数的整数倍，那么需要在循环外执行余下的操作。

浮点数除法

浮点数除法耗时比加法、减和乘法（20 - 45个时钟周期）耗时要长得多

浮点数除以一个常数可以用乘以一个常数的倒数来代替。

double a, b;
a = b / 1.2345;

可以改成：

a = b * (1.0 / 1.2345);

编译器会在编译的时候计算1.0/1.2345的值，并将倒数插入到代码中。当某些选项被设置为放宽浮点精度要求时，编译器可能会自动优化，通常来说由于浮点精度的问题，编译器不会执行这样的优化，因此显式的进行这种优化更加安全。

有时候除法可以被完全消除例如：

if(a > b / c)

有时会被替换为：

if(a * c > b)

但是要确保c > 0否则会有不等式符号反转的问题，若b,c是整数可能还存在除法取整的问题。

乘法和除法还可以结合在一起。

double y, a1, a2, b1, b2;
y = a1/b1 + a2/b2;

y = (a1 * b2 + a2 * b1) / (b1 * b2); //消去一个除法

这个技巧甚至可以消去完全独立的除法，例如：

double a1, a2, b1, b2, y1, y2;
y1 = a1 / b1;
y2 = a2 / b2;


double a1, a2, b1, b2, y1, y2, reciprocal_divisor;
reciprocal_divisor = 1. / (b1 * b2);
y1 = a1 * b2 * reciprocal_divisor;
y2 = a2 * b1 * reciprocal_divisor;

不要混合使用float和double

不管使用的是单精度还是双精度，浮点数的计算通常要花费相同的时间，但是在为64位操作系统编译的程序和使用指令集SSE2或更高版本编译的程序中，混合使用单精度和双精度是有代价的，例如：

float a, b;
a = b * 1.2;

c/c++ 标准规定，所有的浮点常量默认都是双精度的，因此1.2是一个双精度的常量。因此乘法时会将b转换为双精度然后再将结果转换成单精度，增加了两次类型转换的消耗，而这个类型转换需要很长的时间。 可以通过避免转换，显著提高效率；
例如改成：

float a, b;
a = b * 1.2f;
//或者
double a, b;
a = b * 1.2;

浮点数和整数的相互转换

将浮点数转为整数

根据C++标准，所有的从浮点数到整数的转换都使用向0的截断，而在没有SSE2指令集的情况下，截断要比舍入花费更长时间（大约三倍）。如果可能，应该使用SSE2指令集，64位模式下，SSE2总是被使用

在没有SSE2的情况下，从浮点数到整数的转换需要40个时钟周期，有SSE的情况下基本没差别。

lrint和lrintf函数可以高效的将双精度或者单精度数四舍五入到整数。

将整数转化为浮点数

整数到浮点数的转换比浮点数到整数的转换快，通常耗费（5 - 20个时钟周期）
无符号整数转化为浮点数的效率要低于有符号整数转化为浮点数。

用整数操作来改变浮点变量

根据IEE 754（1985）标准，浮点数以二进制表示形式存储

其实就是用整数类来模拟规格化浮点数，

数学函数

常见的数学函数例如对数、指数函数和三角函数都是在x86CPU硬件中实现的，然而，当SSE2指令集可用时，软件实现要快于硬件实现，若启用了SSE2指令集（64位默认启用）好的编译器会使用软件实现。

静态库和动态库

函数库可以实现为静态链接库(.ilb, .a)或者动态链接库, 也称为共享对象(.dll, .so);

静态链接的机制是链接器从库文件提取所需的函数并将他们复制到可执行文件中，最终只需要将可执行文件分发给用户。

而动态库的工作方式是动态库中的函数的链接在加载库或运行时解析，因此当程序运行时，可执行文件和一个或者多个动态库都会被加载到内存中。可执行文件和所有动态库都要分发给用户。
静态链接相对于动态链接的优点是：

1. 使用静态链接，应用程序只需要包含库中所需要饭的部分，而使用动态链接则需要将整个库（或者至少大部分）加载到内存中，即使只需要使用库的一个函数
2. 当使用静态链接时，所有的代码都在一个可执行文件中，而动态链接是的程序启动时必须加载多个文件
3. 调用动态库的函数要比调用静态库的函数花费时间长，因为需要通过导入表中的指针急性额外的跳转，还可能需要在过程链接表（PLT）中进行查找
4. 当代码分布在多个动态库中时，内存空间会更加碎片化，动态库加载在可被内存页大小（4096）整除的圆形内存地址中，使得所有的动态库争用相同的缓存线路，降低代码缓存he数据缓存的效率。
5. 动态库在某些系统中效率比较低，因为需要位置无关代码。
6. 如果使用动态链接，安装使用相同动态库更新版本的第二个应用程序就可以改变第一个程序的行为，而静态库则不会。

使用动态库的优点是：

1. 同时运行的多个应用程序可以共享相同的动态库而无需将库的多个实例加载到内存中，这适用于同时运行多个进程的服务器。实际上只有代码节和可读数据可以共享，任何可写数据部分，每个进程都需要单独的一个实例。
2. 无需更新调用程序，动态链接库就可以更新到新的版本
3. 动态链接库可以被不支持静态链接的编程语言调用
4. 使用动态里链接库可以为已有程序制作插件来添加功能。

静态链接适合速度关键型函数，许多函数库都有静态和动态版本，如果速度很重要，则建议使用静态版本。

有些系统允许函数调用的延迟绑定，即程序加载时不解析链接函数的地址，而是等到第一次调用函数时才解析。延迟绑定对于大型库非常有用，因为大型库中，单个会话中实际调用的函数很少。 延迟绑定会降低所调用函数的性能，当函数第一次调用时，会有相当大的延迟，因为需要链接动态库。

位置无关代码

Linux、BSD和Mac系统中的共享对象通常使用位置无关代码，具有以下特性：

1. 代码部分不包含需要重新定位的绝对地址，只包含自相对地址。因此代码段可以在任意内存地址加载，并在多个进程间共享。
2. 数据部分不会在多个进程共享，因为他通常包含可写数据。因此数据部分可能包含需要重新定位的指针或者地址。
3. Linux和BSD中，所有的公共函数和公共数据都可以被覆盖。如果主可执行文件中的函数和共享对象中的函数具有相同的名称，那么不仅在主可执行文件调用时而且从共享对象调用时，主可执行文件中的版本都是优先的。为了实现这个覆盖特性，共享对象有一个指向其函数的指针表，称为是过程链接表（PLT）和一个指向其变量的指针表。称为全局偏移表（GOT）吗。所有对函数和公共变量的访问都要经过PLT和GOT

PLT和GOT代价很高昂，而且在大多数库中都从来不会使用。

另外一个位置无关代码的高昂代价是32位模式下计算自相关引用。32位的x86指令集没有用于数据自相对寻址的指令，因此代码需要通过以下步骤访问公共数据对象：

1. 通过函数调用获得自身地址
2. 通过一个自相对地址查找GOT
3. 在GOT中查找数据对象的地址
4. 通过地址访问数据对象

64位模式不需要步骤1，因为64位模式只支持自相对寻址

位置无关代码会带来性能下降，因此最佳的方法是使用静态链接
在无法避免动态链接的情况下，有一些依赖于系统的避免时间消耗的方法，如下：

32位Linux中的共享对象

根据gnu编译手册，共享对象都是使用-fpic选项编译的，该选项使代码是位置无关的，同时为所有的函数生成PLT为所有的公共和静态数据生成GOT

不使用-fpic也可以编译共享对象，避免了上面说的问题，但同时也失去了覆盖的特性，但是我们一般也用不着。

64位共享对象

64位模式下，计算自相对地址的过程更快，但是依旧有PLT和GOT带来的时间消耗。
而64位模式下，直接取消-fpic也会带来一些问题，最好的解决办法是用-fpie来代替，这将会在代码部分生成相对地址，但是对于内部引用它不会使用PLT和GOT，相对的，使用了-fpie选项，应该避免使用任何公共变量，所有全局变量应该使用生命static 或者 _attribute__((visibility("hidden"))来隐藏。

32 位MacOS

使用-fno-pic编译器选项来关闭与位置无关代码标志

64位MacOS

啥都不用做，已经非常有效了

系统编程

设备驱动程序，中断服务路由、系统核心和高优先级线程是速度特别关键的地方，在系统代码或者高优先级线程中特别耗时的函数可能会阻塞其它所有内容的执行。

系统代码必须遵守寄存器使用的某些原则。

在系统代码中节约资源的使用非常重要。动态内存分配风险比较大，因为可能会涉及到触发垃圾回收，非常耗费时间。队列应该实现为固定大小的循环缓冲区，而不是链表，也不要用stl容器。