CPU只能直接理解机器码。所有的编程语言必须经历下面其中一步：

解释：通过软件执行。编译：通过软件翻译成机器码。

源代码被编译成可执行文件的过程中发生了什么？

预处理器：将源代码的头文件进行展开，并且进行宏替换。生成.i文件。

编译器：将.i文件编译成汇编文件.s

汇编器：将汇编文件编译为目标机器码(.o,.obj)

链接器：链接动态库/静态库和目标文件，组成可执行文件.exe

基础的编译器优化

目标

最小化指令条数

  • 不要多次执行计算
  • 不进行不必要的计算
  • 避免使用开销较大的指令

避免访问内存

  • 尽可能使用寄存器
  • 以缓存友好的方式访问内存
  • 尽早且一次从内存加载数据

避免分支

  • 在任何时候，不做不必要的判断
  • 使CPU更容易预测分支目的
  • 循环展开

局限性

通常不能提升算法的复杂度

  • 只能改善常数因子，但是也能提升10倍甚至更多

不能引起程序行为的任何改变

  • 程序员可能不关心边界情况，但是编译器不知道
  • 例外：编程语言可能声明某些改变是可以接受的

通常只分析一个函数

  • 分析整个程序的成本太高

不能预测运行时输入

  • “最坏情况“的性能和“正常”性能一样重要
  • 特别是对暴露于恶意输入的代码（例如网络服务器）

常见的优化策略

pipeline

img

两种级别的优化

局部优化：

  • 在单个基本块内部进行优化
  • 包括常量折叠，运算减少，（局部）公共子表达式消除等

全局优化：

  • 对整个函数的控制流图进行处理
  • 包括循环嵌套优化，代码移动，（全局）公共子表达式消除，死代码消除等。

Constant Folding

在编译时完成计算。

1
long mask = 0xFF << 8; -> long mask = 0xFF00;

任何输入为常量的表达式都可以被折叠。

甚至可以删除库函数调用

1
size_t namelen = strlen("Xie ShaoFeng") -> size_t namelen = 12;

Strength reduction

用开销更小的操作替换开销大的。

1
long a = b*5; -> long a = (b<<2)+b;

乘法和除法是主要优化目标。

Dead code elimination

不要提交永远不会执行的代码

1
2
if(0) {puts("kilroy was here");}
if(1) {puts("Only bozos on this bus");}

不要提交结果立马被覆盖的代码

1
2
x = 0;
x = 23;

这些可能看起来很蠢，但是时有发生。

Common Subexpression Elimination

分解重复计算，只做一次

1
2
3
4
5
6
norm[i] = v[i].x*v[i].x + v[i].y*v[i].y;
->
elt = &v[i];
x = elt->x;
y = elt->y;
norm[i] = x*x + y*y;

Inlining

将函数体的代码复制到调用处。

  • 可以为其他优化创造机会
  • 可能使代码量更大，变得更慢
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int pred(int x) {
    if (x == 0)
        return 0;
    else
        return x - 1;
}

int func(int y) {
    return pred(y)
         + pred(0)
         + pred(y+1);
}
// inline
int func(int y) {
    int tmp;
    if(y == 0) tmp = 0; else tmp = y - 1;
    if(0 == 0) tmp += 0; else tmp += 0 - 1;
    if(y + 1 == 0) tmp += 0; else tmp += (y + 1) - 1;
    return tmp;
}
总是为真    无意义    常量折叠
// good
int func(int y) {
    int tmp = 0;
    if(y != 0) tmp = y - 1;
    if(y != -1) tmp += y;
    return tmp;
}

Code Motion

将计算移出循环，仅当每次迭代都产生相同结果时才有效。

1
2
3
4
5
6
7
8
long j;
for (j = 0; j < n; j ++)
    a[n*i+j] = b[j];
->
long j;
int ni = n*i;
for (j = 0; j < n; j ++)
    a[ni+j] = b[j];

Loop Unrolling

  • 减少循环条件判断的成本
  • 为CSE，code motion, scheduling等优化创造机会
  • 为向量化作准备
  • 增加代码大小，可能导致性能降低
1
2
3
4
5
6
7
8
9
10
for(size_t i = 0; i < nelts; i ++) {
    A[i] = B[i]*k + C[i];
}
// assume nelts % 4 == 0
for(size_t i = 0; i < nelts - 4; i += 4) {
    A[i] = B[i]*k + C[i];
    A[i+1] = B[i+1]*k + C[i+1];
    A[i+2] = B[i+2]*k + C[i+2];
    A[i+3] = B[i+3]*k + C[i+3];
}

Scheduling

让CPU时刻保持忙碌，特别是在其等待IO操作时。

Memory Aliasing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void sum_rows(double *a, double *b, long n) {
    for (long i = 0; i < n; ++i) {
        b[i] = 0.0;
        for (long j = 0; j < n; ++j) {
            b[i] += a[i * n + j];
        }
    }
}
.L4:
    movsd   (%rsi,%rax,8), %xmm0    # FP load a double-precision value from memory
    addsd   (%rdi), %xmm0            # FP add the value at the address pointed by %rdi
    movsd   %xmm0, (%rsi,%rax,8)    # FP store the result back to memory
    addq    $8, %rdi                 # Increment %rdi by 8 bytes
    cmpq    %rcx, %rdi                # Compare %rdi with %rcx
    jne     .L4                      # Jump to .L4 if not equal, continuing the loop

最内部的循环每次都会进行了两次内存读取。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void sum_rows2(double *a, double *b, long n) {
    long i, j;
    for (i = 0; i < n; ++i) {
        double val = 0; // Initialize sum for the current row
        for (j = 0; j < n; ++j) {
            val += a[i * n + j]; // Accumulate the sum of the current row
        }
        b[i] = val; // Store the sum of the current row in vector 'b'
    }
}
.L10:
    addsd (%rdi), %xmm0    # FP load and add
    addq   $8, %rdi        # Increment the data pointer by 8 bytes
    cmpq   %rax, %rdi      # Compare the data pointer with the row count
    jne    .L10            # If not equal, jump back to .L10 to continue the loop

最内层循环没有内存读取。

我们也可以使用restrict关键字来让编译器自己进行优化，不过没有使用局部变量可靠。

编译器可能无法进行某些优化，比如：

1
2
3
4
5
6
7
8
9
void lower1(char* s)
{
    size_t i;
    for (int i = 0; i < strlen(s); i ++) {
        if (s[i] >= 'A' && s[i] <= 'Z') {
            s[i] -= ('A'-'a');
        }
    }
}

编译器不知道strlen的实现到底如何，所以在不敢保证代码效果不改变时，编译器无法做出优化。这将导致这段代码的时间复杂度退化成O(n^2)。

链接：将.obj文件组合成程序

例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int sum(int *a, int n);
int array[2] = {1, 2};
int main(int argc, char** argv) {
    int val = sum(array, 2);
    return val;
}

int sum(int *a, int n) {
    int i, s = 0;
    for (int i = 0; i < n; i ++) {
        s += a[i];
    }
    return s;
}
gcc -Og -o prog main.c sum.c
./prog

img

链接器做了什么？

Symbol resolution

定义

程序定义并且引用symbol。链接器将每个符号引用和一个符号定义对应起来。

1
2
3
void swap() {} // swap is a symbol
swap(); // reference symbol swap
int *xp = &x; // define symbol xp, reference x

symbol的定义被存储在.obj文件的符号表中。

  • 符号表是一个实体数组
  • 每一个实体包含名字，大小和位置

每一个.obj文件m都有一个包含了它定义或者它需要的符号表。

链接器符号有三种类型：

  • Global definitions：由m定义，且能被其他文件引用。在C语言中，非静态函数和全局变量默认为该类型。
  • Local definitions：由m定义，但是不能被其他文件引用。在C语言中，被static修饰的全局变量或静态函数。
  • External reference：被m使用，但是不被m定义。必须在其他文件中能找到其定义。

请勿混淆链接器符号与程序中的变量。

例子

1
2
3
4
5
6
7
8
9
int incr = 1;
static int foo(int a) {
    int b = a + incr;  // 计算 a 加上 incr 的和
    return b;          // 返回计算结果
}
int main(int argc, char* argv[]) {
    printf("%d\n", foo(5));
    return 0;  // 返回主函数的退出状态码
}

里面包含了哪些符号？我们可以借助readelf命令查看。

1
2
3
4
5
6
7
8
9
10
11
12
gemini@gemini:~/code/test$ readelf -s symbol.o

Symbol table '.symtab' contains 8 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND 
     1: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS symbol.c
     2: 0000000000000000     0 SECTION LOCAL  DEFAULT    1 .text
     3: 0000000000000000    30 FUNC    LOCAL  DEFAULT    1 foo
     4: 0000000000000000     0 SECTION LOCAL  DEFAULT    5 .rodata
     5: 0000000000000000     4 OBJECT  GLOBAL DEFAULT    3 incr
     6: 000000000000001e    58 FUNC    GLOBAL DEFAULT    1 main
     7: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND printf

Local Symbols

Local non-static C variables：在栈中存储

Local static C variables：存储在 .bss 或 .data

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static int x = 15;
int f() {
    static int x = 17;
    return x ++;
}

int g() {
    static int x = 19;
    return x += 14;
}

int h() {
    return x += 27;
}

编译器为每个定义的x变量在.data段上分配空间。

每个local symbols在符号表中有着唯一的名字，在本例中为x，x.0，x.1。

1
2
3
4
5
6
7
8
9
10
11
12
Symbol table '.symtab' contains 10 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND 
     1: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS symbol.c
     2: 0000000000000000     0 SECTION LOCAL  DEFAULT    1 .text
     3: 0000000000000000     0 SECTION LOCAL  DEFAULT    3 .data
     4: 0000000000000004     4 OBJECT  LOCAL  DEFAULT    3 x.1
     5: 0000000000000000     4 OBJECT  LOCAL  DEFAULT    3 x.0
     6: 0000000000000008     4 OBJECT  LOCAL  DEFAULT    3 x
     7: 0000000000000000    20 FUNC    GLOBAL DEFAULT    1 f
     8: 0000000000000014    20 FUNC    GLOBAL DEFAULT    1 g
     9: 0000000000000028    20 FUNC    GLOBAL DEFAULT    1 h

注意事项

下面这些代码片段链接器是否会报错？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
A:
int x = 7;
p1() {}

int x = 0;
p1() {}

B:
int x = 7;
int y = 5;
p1() {}

extern double x;
p2() {}

C:
char p1[] = 0xC3;

extern void p1();
p2() {p1();}

这三个代码片段只有A会报错。因为链接器只检查一个符号是否被定义了两次，而不会检查引用的类型是否匹配。

所以，为了防止类型不匹配，我们应当注意以下几点：

  • 尽量避免使用全局变量
  • 尽可能使用static关键字
  • 在头文件中声明所有非静态内容。
  • 总是用extern修饰头文件中的声明

Relocation

  • 将单独的代码和数据块合并到同一个部分
  • 重定位标识符，将它们在.o文件中的相对位置转换成他们在可执行文件的内存中的绝对位置。
  • 更新所有对标识符的引用，替换成他们的新地址

例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
main.c:
int sum(int *a, int n);
int array[2] = {1, 2};
int main(int argc, char **argv) {
    int val = sum(array, 2);
    return val;
}

sum.c:
int sum(int *a, int n) {
    int i, s = 0;
    for (int i = 0; i < n; i++) {
        s += a[i];
    }
    return s;
}

img

Libraries

如何打包程序员经常使用的函数？

math,I/O,memory management, string, etc.

有两个选择：

  1. 将所有函数放到一个源文件中。问题：目标文件很大。
  2. 把每个函数放到单独的源文件中，程序员显示地链接这些库到他们的程序。问题：编程更麻烦。

Static Libraries

  • 将相关的可重定位目标文件合并成一个带有索引的单一文件
  • 增强链接器，使其能通过在一个或多个归档中查找符号来尝试解决未解决的外部引用
  • 如果一个归档内某个文件实现了引用，则将其链接到可执行文件中。
1
ar rs libc.a atoi.o printf.o ... random.o

img

链接器解决外部引用的算法流程：

  1. 按命令行的顺序，扫描.o文件和.a文件。
  2. 在扫描期间，维护一个保存了未被解决的引用列表。
  3. 每遇到一个新的.o或.a文件时，尝试根据obj中定义的符号表去寻找是否有未被解决的引用的实现，
  4. 如果扫描结束时，列表非空则产生错误。

所以，命令行的顺序很重要！我们应该把库放到命令行末尾。

Shared Libraries

Static libraries的缺点：

  • 每一份可执行文件中都会保存一个静态库
  • 包含同一个静态库的多个可执行文件会载入这个静态库多次
  • 如果库函数出现了小错误，每个应用程序必须全部显式地重新链接。

动态库：包含代码和数据的目标文件，只有在载或者运行时，被载入内存，动态地与应用程序链接。

  • 首次加载并运行可执行文件时，可能会发生动态链接。
    • 在Linux中，由动态链接器自动处理
    • 标准C库libc.so经常使用动态链接
  • 动态链接也可能发生在程序执行之后
    • 在linux中，可以调用dlopen()来做到。
      • 分布式软件
      • 高性能服务器
      • 运行时库打洞
  • 共享库程序可以由多个进程共享，也就是只需要被载入内存一次。

动态库需要使用的字段

  • .interp section：指定使用哪个动态链接器
  • .dynamic section：指定需要链接的动态库名字