编译优化技术介绍 #

本文会介绍 循环展开， GCC优化，以及在我们的程序中使用指定GCC进行优化后会有怎样的结果。

循环展开 #

我们有两个函数 sum 和 sum_expanded，它们都用于计算从 1 到 n 的数字之和。下面是它们的代码实现：

long long sum(long long n){
    long long total = 0;
    for (long long i = 1; i<= n; i++){
        total += i;
    }
    return total;
}

long long sum_expanded(long long n ){
    long long total0 = 0, total1 = 0, total2=0, total3=0;
    for ( long long i = 1;i<=n-3;i+=4){
        total0 += i;
        total1 += i+1;
        total2 += i+2; 
        total3 += i+3;
    }
    if(n%4){
        long long num = n%4;
        for(long long i = n;i>n-num;i--){
            total0 += i;
        }
    }
    return total0+total1+total2+total3;
}

虽然它们的实现方式不同，但计算结果是一致的。我们先来比较一下它们的执行时间：

$ time ./sum 1000000000
sum of 1000000000 is: 500000000500000000

real    0m0.747s
user    0m0.747s
sys     0m0.000s

$ time ./sum 1000000000 --expanded
sum of 1000000000 is: 500000000500000000

real    0m0.351s
user    0m0.351s
sys     0m0.000s

单看第二份代码十分冗长，感觉多了三个变量，而且略显笨拙，为什么反而快了大约0.3s呢？我们需要从汇编代码指令的角度去理解。

编译cpp程序得到汇编代码 #

为了得到从我们源文件sum.cpp得到汇编代码，在使用g++编译的时候可以指定生成对应汇编代码，具体命令是

g++ -std=c++17  sum.cpp  -S sum.s

指定-std=c++17是因为该程序用到额外的argparse库用于参数处理，需要c++17的支持。

编译得到的具体汇编代码 #

sum.s中包含了所有汇编代码，其中sum这个函数对应的汇编代码如下，大家可以阅读注释理解汇编代码。为了充分理解汇编代码，请打开 汇编基础知识.md对照着看。

# sum.s
_Z3sumx:
.LFB4955:
.cfi_startproc
endbr64                 ; 使用 Intel CET(Control-flow Enforcement Technology)终止间接分支
pushq %rbp              ; 将帧基址寄存器rbp(base pointer register)压入栈中,函数序言
.cfi_def_cfa_offset 16  ; 定义 Canonical Frame Address 偏移量为16字节
.cfi_offset 6, -16      ; 将rbp寄存器保存在 CFA-16 字节处
movq %rsp, %rbp         ; 将栈顶指针rsp的值赋给rbp,建立函数栈帧
.cfi_def_cfa_register 6 ; 将rbp寄存器定义为 Canonical Frame Address
movq %rdi, -24(%rbp)    ; 将第一个参数n存入rbp-24的位置
movq $0, -16(%rbp)      ; 将变量total初始化为0,存入rbp-16的位置
movq $1, -8(%rbp)       ; 将循环变量i初始化为1,存入rbp-8的位置
jmp .L881               ; 无条件跳转到.L881
.L882:                  ; 循环体
movq -8(%rbp), %rax     ; 将i的值存入rax寄存器
addq %rax, -16(%rbp)    ; 将i的值加到total上
addq $1, -8(%rbp)       ; i自增1
.L881:                  ; 循环条件判断
movq -8(%rbp), %rax     ; 将i的值存入rax寄存器
cmpq -24(%rbp), %rax    ; 比较i和n的值
jle .L882               ; 如果i<=n,跳转到.L882继续循环
movq -16(%rbp), %rax    ; 循环结束,将total的值存入rax作为返回值
popq %rbp               ; 恢复rbp寄存器,函数尾声
.cfi_def_cfa 7, 8       ; 将 Canonical Frame Address 定义在rsp+8处
et                     ; 返回
.cfi_endproc
.LFE4955:
.size _Z3sumx, .-_Z3sumx
.globl _Z12sum_expandedx
.type _Z12sum_expandedx, @function

假设输入规模n = 1e9，实际运行的指令数量估算结果大约是6e9。其中负责循环的i++，i<n，以及跳转指令共三条，他们占了5e8的运算次数。

循环展开优化 #

当我们手动把循环展开，能够减少循环开销(loop overhead)，下面比较两份汇编代码主循环部分：

# 原本的sum函数对应的汇编代码
.L882:
movq -8(%rbp), %rax     # 将循环变量i的值加载到rax寄存器
addq %rax, -16(%rbp)    # 将rax的值加到sum上
addq $1, -8(%rbp)       # 将循环变量i的值增加1

.L881:
movq -8(%rbp), %rax     # 将循环变量i的值加载到rax寄存器
cmpq -24(%rbp), %rax    # 比较i和n的大小
jle .L882               # 如果i <= n,跳转到.L882,继续循环

# 循环展开后对应的汇编代码
.L886:
movq -24(%rbp), %rax    # 将循环变量i的值加载到rax寄存器
addq %rax, -56(%rbp)    # 将rax的值加到sum1上
movq -24(%rbp), %rax    # 将循环变量i的值加载到rax寄存器
addq $1, %rax           # 将rax的值加1,对应i+1
addq %rax, -48(%rbp)    # 将rax的值加到sum2上
movq -24(%rbp), %rax    # 将循环变量i的值加载到rax寄存器
addq $2, %rax           # 将rax的值加2,对应i+2
addq %rax, -40(%rbp)    # 将rax的值加到sum3上
movq -24(%rbp), %rax    # 将循环变量i的值加载到rax寄存器
addq $3, %rax           # 将rax的值加3,对应i+3
addq %rax, -32(%rbp)    # 将rax的值加到sum4上
addq $4, -24(%rbp)      # 将循环变量i的值增加4

.L885:
movq -72(%rbp), %rax    # 将n的值加载到rax寄存器
subq $2, %rax           # 将rax的值减2,对应n-2
cmpq %rax, -24(%rbp)    # 比较i和n-2的大小
jl .L886                # 如果i < n-2,跳转到.L886,继续循环

对于优化后的代码，因为每个循环中处理了4个i，总的循环次数为原来代码的$\frac{1}{4}$，循环体中的汇编指令共有16条，所以对于相同的输入规模优化后的代码需要执行大约$16\times\frac{1}{4}\times 10^9 = 4 \times 10^9$次，比原来的代码少了$\frac{1}{3}$。

使用Perf工具查看更详尽的程序运行报告 #

perf是一款Linux性能分析工具，我们可以通过perf查看一个程序具体运行多少次指令，也可以查看最耗时间的指令是哪些。

部分linux版本在apt库里可以直接下载perf工具，如果无法下载perf工具则需要参照 这个博文编译安装。使用这个工具必须要有一个linux系统的root权限，如果是windows用户可以使用 WSL2。

下面用Perf查看程序运行具体开销

$ perf stat ./sum 1000000000 
sum of 1000000000 is: 500000000500000000

 Performance counter stats for './sum 1000000000':

            760.03 msec task-clock:u                     #    0.999 CPUs utilized             
                 0      context-switches:u               #    0.000 /sec                      
                 0      cpu-migrations:u                 #    0.000 /sec                      
               126      page-faults:u                    #  165.782 /sec                      
        3512530178      cycles:u                         #    4.622 GHz                       
            359358      stalled-cycles-frontend:u        #    0.01% frontend cycles idle      
             87579      stalled-cycles-backend:u         #    0.00% backend cycles idle       
        6002401250      instructions:u                   #    1.71  insn per cycle            
                                                  #    0.00  stalled cycles per insn   
        1000376680      branches:u                       #    1.316 G/sec                     
             13188      branch-misses:u                  #    0.00% of all branches           

       0.760501667 seconds time elapsed

       0.760431000 seconds user
       0.000000000 seconds sys

$ perf stat ./sum 1000000000 --expanded
sum of 1000000000 is: 500000000500000000

 Performance counter stats for './sum 1000000000 --expanded':

            352.05 msec task-clock:u                     #    0.999 CPUs utilized             
                 0      context-switches:u               #    0.000 /sec                      
                 0      cpu-migrations:u                 #    0.000 /sec                      
               126      page-faults:u                    #  357.903 /sec                      
        1620682163      cycles:u                         #    4.604 GHz                       
            461033      stalled-cycles-frontend:u        #    0.03% frontend cycles idle      
             77419      stalled-cycles-backend:u         #    0.00% backend cycles idle       
        4002409178      instructions:u                   #    2.47  insn per cycle            
                                                  #    0.00  stalled cycles per insn   
         250377923      branches:u                       #  711.199 M/sec                     
             12970      branch-misses:u                  #    0.01% of all branches           

       0.352576896 seconds time elapsed

       0.352555000 seconds user
       0.000000000 seconds sys

可以看到具体的指令执行次数与估算的次数相近，优化前后分别是6e9和4e9次指令。

# sum
6002401250      instructions:u                   #    1.71  insn per cycle      
# sum_expanded
4002409178      instructions:u                   #    2.47  insn per cycle     

指令级并行 #

超标量技术指的是处理器的内核中一般有多个执行单元（或称功能单元），如算术逻辑单元、位移单元、乘法器等等，像PowerPC 970较先进的设计就内含四组ALU、二组FPU。例如a=b+c ; d=e+f这串指令就能够并发运算，

O3优化比较 #

普通sum函数循环优化前

.L882:
	movq	-8(%rbp), %rax
	addq	%rax, -16(%rbp)
	addq	$1, -8(%rbp)
.L881:
	movq	-8(%rbp), %rax
	cmpq	-24(%rbp), %rax
	jle	.L882

普通sum函数-O3循环优化后

	addq	%rax, %r8
	addq	$1, %rax
	cmpq	%rdi, %rax
	jne	.L1212

显式使用寄存器 #

寄存器有自己的名字，在cheat sheet中有定义，一般为了减少寄存器使用量，会复用同一个寄存器，优化后的代码使用多个寄存器，我们可以认为这里每个寄存器代表了一个代码中变量，这里rax是i，r8是total_sum，rdi是input n

O3优化后，使用了更多的寄存器变量。优化后的版本使用了%rax， %r8和%rdi三个寄存器，而优化前的版本只使用了%rax一个寄存器，其他变量都保存在栈中(%rbp偏移)。

这样的优化大大减少了访问内存的次数，提高程序运行速度。

减少循环代码 #

优化减少了指令数量。优化前的代码按照c++源代码的定义一步步翻译成汇编代码，循环体内有6条汇编指令，优化后的循环体只有4条指令。假设输入规模n = 1e9，优化前后实际运行的指令数量估算结果就是6e9，4e9。