十一、具体优化策略

跳过了anger手册中关于cpu dispatch的一章，还是感觉太遥远了，等需要的时候再去了解吧

1.查找表（lookup tables）

如果list在缓存中，从list中读值是非常快的，要快过函数计算，所以可以将函数计算替换成从查找表取值。

使用查找表的tips

  1. 查找表应该声明为const，以便启用常量传播和其他优化。
  2. 在函数内部声明查找表时不要声明为静态的static，因为静态数据可能分散在不同的内存地址，可能会导致缓存问题。可以声明为const，例如：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Example 14.1c
void CriticalInnerFunction ()
{
    // Table of factorials:
    const int FactorialTable[13] = {1, 1, 2, 6, 24, 120, 720,
        5040, 40320, 362880, 3628800, 39916800, 479001600};
    ...
    int i, a, b;
    // Critical innermost loop:
    for (i = 0; i < 1000; i++)
    {
        ...
        a = FactorialTable[b];
        ...
    }
}

例 14.1c中的 FactorialTable 在调用 CriticalInnerFunction 时从静态内存中复制到栈上。编译器将表存储在静态内存中，并在函数开始的地方插入代码，将表复制到栈内存中。当然，复制表需要额外的时间，但是当它位于关键的最内层循环之外时，这是被允许的。循环将使用存储在栈内存中的表的副本，这与其它本地变量相邻，因此缓存效率可能比静态内存更高。

  1. 可以使用查找表替代简单的分支，避免分支的预测出错
1
2
3
4
// Example 14.2a

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

如果我们假设 b 总是 0 或 1，并且它的值可预测性很差，那么使用查找表来代替分支是有利的：

1
2
3
4
// Example 14.2b
float a; int b;
const float OneOrTwo5[2] = {1.0f, 2.5f};
a = OneOrTwo5[b & 1];

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

1
2
3
4
5
6
7
8
9
10
11
12
13
// Example 14.3a
int n;
switch (n)
{
    case 0:
        printf("Alpha"); break;
    case 1:
        printf("Beta"); break;
    case 2:
        printf("Gamma"); break;
    case 3:
        printf("Delta"); break;
}

这可以使用查找表来提升效率：

1
2
3
4
5
6
7
8
9
10
// Example 14.3b
int n;
char const * const Greek[4] = {
    "Alpha", "Beta", "Gamma", "Delta"
    };
if ((unsigned int)n < 4)
{
    // Check that index is not out of range
    printf(Greek[n]);
}

表的声明有两个 const，因为它们指向的指针和文本都是常量。

2.边界检查优化

在C++ 中，通常有必要检查数组索引是否超出范围。这常常看起来是这样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
// Example 14.4a

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

i < 0 和 i >= size 这两个比较可以使用一个比较替换：

1
2
3
4
5
6
7
8
9
// Example 14.4b
if ((unsigned int)i >= (unsigned int)size)
{
    cout << "Error: Index out of range";
}
else
{
    list[i] += 1.0f;
}

当 i 被解释为无符号整数时，i 可能的负值将以一个较大的正数出现，这将触发错误条件。用一个比较替换两个比较可以加快代码的速度，因为测试一个条件相对比较昂贵，而类型转换根本不会生成额外的代码。

这个方法可以扩展到一般情况下：你想要检查一个整数是否在一个特定的区间之内：

1
2
3
4
5
// Example 14.5a

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

可以修改成：

1
2
3
// Example 14.5b

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

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

1
2
3
4
5
// Example 14.6

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

这需要略微解释一下。i&15 的值肯定在 0 到 15 的区间内。如果 i 在这个区间之外，例如 i = 18 ，那么 & 运算符（按位与）将 i 的二进制值截断为 4 位，结果将是 2。结果与 i 除上 16 的余数相同。如果我们不需要错误消息的话，这种方法在数组索引超出范围时可以防止程序出错。需要注意的是，这种方法只适用于2的幂（即2、4、8、16、32、64、……）。通过按位与上$2^{n -1}$，我们可以确保一个数的值小于 $2^n$，并且不是负的。按位与操作隔离数字中有效的低 n 位，并将所有其他位设为零。

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

位运算符 &， |， ^， ~， <<， >> 可以在一次操作中测试或操作整数的所有位。例如，如果 32 位整数的每个位都有特定的含义，那么可以使用 | 运算符在一个操作中设置多个位；你用 & 运算符清除或遮掩掉多个位。你可以用 ^ 运算符转换多个位。

& 运算符对于测试单个操作中的多个条件也很有用。例如：

1
2
3
4
5
6
7
8
9
10
// Example 14.7a. Testing multiple conditions

enum Weekdays {
    Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday
};
Weekdays Day;
if (Day == Tuesday || Day == Wednesday || Day == Friday)
{
    DoThisThreeTimesAWeek();
}

本例中的 if 语句有三个条件，它们被实现为三个分支。如果将 Sunday、Monday 等常量定义为 2的幂，则可以将它们合并为一个分支：

1
2
3
4
5
6
7
8
9
10
// Example 14.7b. Testing multiple conditions using &
enum Weekdays {
    Sunday = 1, Monday = 2, Tuesday = 4, Wednesday = 8,
    Thursday = 0x10, Friday = 0x20, Saturday = 0x40
};
Weekdays Day;
if (Day & (Tuesday | Wednesday | Friday))
{
    DoThisThreeTimesAWeek();
}

通过在例14.7b中给每个常数的值设置成 一个 2的幂，我们实际上是在使用 Day 中的每一位来表示星期几。我们可以用这种方法定义的常量的最大数量等于整数中的位的数量，通常是 32。在 64 位系统中，我们可以使用 64 位整数，这几乎没有任何性能上的损失。

在例 14.7b中的表达式 (Tuesday | Wednesday | Friday) 被编译器转换成 0x2C，这样的话 if 条件就可以通过一个 & 操作来计算，而这是很快的。如果变量 Day 中设置了 Tuesday、Wednesday 或 Friday 中的的任何位，& 操作的结果将是非零的，因此将被视为真。

注意布尔运算符 &&， ||， ! 以及对应的位运算符 &， |， ~。布尔运算符产生一个结果，true（1）或 false （0），且第二个操作数只在需要时计算。位运算符在应用于 32位整数时，会产生 32个结果，它们总是对两个操作数进行求值。然而，位运算符的计算速度比布尔运算符快得多，因为只要操作数是整数表达式而不是布尔表达式，它们就不需要使用分支。

当使用整数作为布尔向量时，位运算符可以做很多事情，而且这些操作非常快。这在包含许多布尔表达式的程序中很有用。无论常量是用 enum、const 还是 #define 定义的，都不会影响性能。

4.整数乘法

编译器优化常常会使用移位代替乘法，当然这意味着乘数是2的幂，这在计算地址时会比较有用。

举个栗子：

1
2
3
4
5
6
7
8
9
10
11
12
// Example 14.8

const int rows = 10, columns = 8;
float matrix[rows][columns];
int i, j;
int order(int x);
...
for (i = 0; i < rows; i++)
{
    j = order(i);
    matrix[j][0] = i;
}

这里，matrix[j][0] 的地址在内部使用下面的式子计算：

(int)&matrix[0][0] + j * (columns * sizeof(float))。

现在，要乘以 j 的因子是 (cloumns * sizeof(float)) = 8 * 4 = 32。这是 2的幂，所以编译器可以用 j << 5 替换 j * 32。如果列的大小不是 2的幂，那么乘法会花费更长的时间。因此，如果以无序方式访问矩阵中的行，则将矩阵中的列数设置为 2的幂是有利的。

这同样适用于结构体或类元素的数组。如果以无序方式访问对象，则每个对象的大小最好是 2的幂。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Example 14.9

struct S1
{
    int a;
    int b;
    int c;
    int UnusedFiller;
};
int order(int x);
const int size = 100;
S1 list[size]; int i, j;
...
for (i = 0; i < size; i++)
{
    j = order(i);
    list[j].a = list[j].b + list[j].c;
}

在这里，我们在结构体中插入了 UnusedFiller，以确保其大小是的 2的幂，以使地址计算的更快。

5.整数除法

除法的耗时要长的多，优化策略有：

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

例如：

1
2
3
4
5
6
7
8
// Example 14.10

int a, b, c;
a = b / c; // This is slow
a = b / 10; // Division by a constant is faster
a = (unsigned int)b / 10; // Still faster if unsigned
a = b / 16; // Faster if divisor is a power of 2
a = (unsigned int)b / 16; // Still faster if unsigned

相同的准则同样适用于取模运算：

1
2
3
4
5
6
7
8
// Example 14.11

int a, b, c;
a = b % c; // This is slow
a = b % 10; // Modulo by a constant is faster
a = (unsigned int)b % 10; // Still faster if unsigned
a = b % 16; // Faster if divisor is a power of 2
a = (unsigned int)b % 16; // Still faster if unsigned

可以利用这些指导原则，如果可能的话，可以使用一个 2的幂的常数做为除数，如果确定被除数不为负数，可以将被除数更改为无符号。

6.浮点数除法

浮点数除法的耗时比加法、减法和乘法（20 - 45个时钟周期）耗时要长得多。尽量减少除法出现的次数。

1.可以将除法替换为乘法

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

1
2
3
4
// Example 14.14a

double a, b;
a = b / 1.2345;

可以把这个改成：

1
2
3
4
// Example 14.14b

double a, b;
a = b * (1. / 1.2345);//这个常数倒数的值会在编译时计算出

再比如：

1
2
3
// Example 14.15a

if (a > b / c)

有时会被替换成：

1
2
3
// Example 14.15b

if (a * c > b)

但是要注意这里的陷阱：如果 c < 0，不等式符号必须反转。如果 b 和 c 是整数，除法是不精确的，而乘法是精确的

2.合并除法

乘法和除法可以结合在一起，例如：

1
2
3
4
// Example 14.16a

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

这里我们可以通过公分母来消去一个除法：

1
2
3
4
// Example 14.16b

double y, a1, a2, b1, b2;
y = (a1*b2 + a2*b1) / (b1*b2);

3.使用公分母消去除法

使用公分母的技巧甚至可以用于完全独立的除法。例如：

1
2
3
4
5
// Example 14.17a

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

这可以这样变化：

1
2
3
4
5
6
// Example 14.17b

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

7.避免混合使用float和double

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

1
2
3
4
// Example 14.18a

float a, b;
a = b * 1.2; // Mixing float and double is bad

C/C++ 标准规定所有浮点数常量在默认情况下都是双精度的。 所以在这个例子中， 1.2 是一个双精度的常量。因此，在将 b 与双精度常数相乘之前，需要将 b 从单精度转换为双精度，然后再将结果转换回单精度。这些转换需要很长的时间。你可以通过避免转换，来使代码达到 5倍的效率，无论是通过使常数变成单精度或 使 a 和 b 变成双精度的：

1
2
3
4
5
6
7
// Example 14.18b

float a, b;
a = b * 1.2f; // everything is float
// Example 14.18c
double a, b;
a = b * 1.2; // everything is double

当为没有SSE2 指令集的旧处理器编译代码时，混合不同的浮点精度不会带来任何损失，但是最好在所有操作数中保持相同的精度，以防代码被移植到另一个平台。

8.用整数来操作浮点数

我们只需要反转一个符号位就可以改变浮点数的符号：

1
2
3
4
5
6
7
8
// Example 14.23

union
{
    float f;
    int i;
} u;
u.i ^= 0x80000000; // flip sign bit of u.f

我们可以将符号位设置成 0以得到绝对值：

1
2
3
4
5
6
7
8
// Example 14.24

union
{
    float f;
    int i;
} u;
u.i &= 0x7FFFFFFF; // set sign bit to zero

我们可以通过测试除符号位以外的所有位来检查浮点数是否为零：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Example 14.25

union
{
    float f;
    int i;
} u;
if (u.i & 0x7FFFFFFF)
{
    // test bits 0 - 30
    // f is nonzero
}
else
{
    // f is zero
}

我们对指数部分加上 $n$ 就可以将一个非零浮点数乘上 $2^n$：

1
2
3
4
5
6
7
8
9
10
11
12
13
// Example 14.26

union
{
    float f;
    int i;
} u;
int n;
if (u.i & 0x7FFFFFFF)
{
    // check if nonzero
    u.i += n << 23; // add n to exponent
}

例 14.26不会检查溢出，而且只有$n$是整数时才能有用。当没有下溢风险时，你可以对指数部分减去 $n$ 以达到除以 $2^n$的目的。

1
2
3
4
5
6
7
8
9
10
11
// Example 14.27

union
{
    float f;
    int i;
} u, v;
if (u.i > v.i)
{
    // u.f > v.f if both positive
}

在 例 14.27假设我们知道 u.f，v.f 都是正的。如果两者都是负数，或者其中一个为 0，另一个为 -0（符号位为0），则会失败。

我们可以将符号位移出来比较绝对值：

1
2
3
4
5
6
7
8
9
10
11
// Example 14.28

union
{
    float f;
    unsigned int i;
} u, v;
if (u.i * 2 > v.i * 2)
{
    // abs(u.f) > abs(v.f)
}

例 14.28中乘以 2 将移出符号位，使其余位表示浮点数绝对值的单调递增函数。

我们可以通过设置分数部分的位将在区间 $0 <= n < 2^{23}$的整数转换成在区间 $[1.0, 2.0)$的浮点数：

1
2
3
4
5
6
7
8
9
// Example 14.29

union
{
    float f;
    int i;
} u;
int n;
u.i = (n & 0x7FFFFF) | 0x3F800000; // Now 1.0 <= u.f < 2.0

该方法对随机数生成器非常有用。

通常，如果浮点变量存储在内存中，那么以整数的形式访问它会更快，但如果它是寄存器变量，则不会更快。union 强制变量存储在内存中，至少是临时的。因此，如果相同变量使用寄存器可以使其它临近代码获益时，那么使用上述示例中的方法将没有好处。

在这些例子中，我们使用 union 而不是指针的类型转换，是因为这种方法更安全。指针的类型转换可能不适用于遵循标准 C 严格的别名规则的编译器，该规则指定不同类型的指针不能指向同一对象，char 指针除外。

上面的例子都使用单精度。在 32位系统中使用双精度浮点数会变得更复杂。双精度浮点数用 64个位表示，但是 32 位系统不支持 64位整数。许多 32位系统允许你定义 64位整数，但是它们实际上用两个32位整数来表示，效率较低。你可以使用双精度浮点数的高 32位，它允许你访问符号位、指数和分数中的高几位。例如，可以这样测试双精度浮点数的符号：

1
2
3
4
5
6
7
8
9
10
11
12
// Example 14.23b

union
{
    double d;
    int i[2];
} u;
if (u.i[1] < 0)
{
    // test sign bit
    // u.d is negative or -0
}

不建议通过修改 double 类型的一半二进制位来修改它，比如，如果你想要通过 u.i[1] ^= 0x80000000 来反转上述示例中的符号位的话，但这很在 CPU 中产生存储转发延迟（参见手册3：“The microarchitecture of Intel, AMD and VIA CPUs”）。在64 位系统中，可以通过使用 64位整数而不是两个 32位整数表示 double 来避免这种情况。

访问双精度浮点数中的 32位的另一个问题是，它不能移植到大端存储的系统中。因此，如果要具有大端存储的其他平台上实现，例 14.23b 和 例 14.30 将需要修改。所有x86 平台（Windows、Linux、BSD、基于Intel CPU 的Mac OS 等）都使用小端存储，但其他系统可能使用大端存储（如PowerPC）。

我们可以通过比较 32 - 62 位来近似比较双精度浮点数。这在高斯消元法中求矩阵中值最大的主元是很有用的。例 14.28 中的方法在主元搜寻中可以这么使用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Example 14.30

const int size = 100;
// Array of 100 doubles:
union {double d; unsigned int u[2]} a[size];
unsigned int absvalue, largest_abs = 0;
int i, largest_index = 0;
for (i = 0; i < size; i++)
{
    // Get upper 32 bits of a[i] and shift out sign bit:
    absvalue = a[i].u[1] * 2;
    // Find numerically largest element (approximately):
    if (absvalue > largest_abs)
    {
        largest_abs = absvalue;
        largest_index = i;
    }
}

例 14.30 找到数组中 数字（除去符号位）最大（或差不多最大的）的元素。它可能无法区分相对差小于$2^{-20}$的元素，但这对于寻找合适的主元来说是足够准确的。整数比较可能比浮点比较更快。在大的端系统中，你必须用 u[0] 替换 u[1]。

9.静态库和动态库

先比较一下静态库和动态库

静态链接相对于动态链接的优点是：

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

使用动态链接的优点是：

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

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