唐山建设集团网站,网站设置为起始页,wordpress 做成app,陕西建设机械股份有限公司网站C 编译器优化与SIMD指令集 1. 汇编语言1.1 通用寄存器#xff1a;32位时代1.2 通用寄存器#xff1a;64位时代1.3 8位#xff0c;16位#xff0c;32位#xff0c;64位版本1.4 ATT 汇编语言1.5 返回值#xff1a;通过 eax 传出1.6 前6个参数#xff1a;分别通过 edi… C 编译器优化与SIMD指令集 1. 汇编语言1.1 通用寄存器32位时代1.2 通用寄存器64位时代1.3 8位16位32位64位版本1.4 ATT 汇编语言1.5 返回值通过 eax 传出1.6 前6个参数分别通过 ediesiedxecxr8dr9d 传入1.7 开启优化-O31.8 32位乘法运算imull1.9 64位乘法运算imulq1.10 整数加法被优化成 leal 了1.11 整数加常数乘整数都可以被优化成 leal1.12 指针访问对象线性访问地址1.13 指针的索引尽量用 size_t1.14 浮点作为参数和返回xmm 系列寄存器1.15 什么是 xmm 系列寄存器1.16 addss 是什么意思1.17 为什么需要 SIMD单个指令处理四个数据 2. 化简2.1 编译器优化代数化简2.2 编译器优化常量折叠2.3 编译器优化举个例子2.4 编译器优化我毕竟不是万能的2.5 造成 new/delete 的容器即内存分配在堆上的容器2.6 那改用 array 试试2.6.1 那改用手写的 reduce2.6.2 那改小到 10成功了 2.7 constexpr强迫编译器在编译期求值 3. 内联3.1 调用外部函数call 指令3.1.1 编译器优化call 变 jmp 3.2 多个函数定义在同一个文件中3.2.1 编译器优化内联化3.2.2 局部可见函数static 3.2.3 inline 关键字不需要 4. 指针4.1 指针别名现象pointer aliasing4.1.1 告诉编译器别怕指针别名__restrict 关键字4.1.2 __restrict 关键字只需加在非 const 的即可4.1.3 禁止优化volatile4.1.4 注意一下区别 4.2 编译器优化合并写入4.2.1 合并写入不能跳跃 5. 矢量化5.1 更宽的合并写入矢量化指令SIMD5.1.1 SIMD 指令敢不敢再宽一点5.1.2 让编译器自动检测当前硬件支持的指令集 5.2 数组清零自动调用标准库的 memset5.3 从 0 到 1024 填充SIMD 加速5.4 如果不是 4 的倍数边界特判法5.4.1 n 总是 4 的倍数避免边界特判 5.5 假定指针是 16 字节对齐的assume_aligned5.9 数组求和reduction 的优化 6. 循环6.1 循环中的矢量化还在伺候指针别名6.1.1 循环中的矢量化解决指针别名 6.2 循环中的矢量化OpenMP 强制矢量化6.3 循环中的矢量化编译器提示忽略指针别名6.4 循环中的 if 语句挪到外面来6.5 循环中的不变量挪到外面来6.5.1 挪到外面来优化失败 6.6 调用不在另一个文件的函数SIMD 优化失败6.6.1 解决方案放在同一个文件里 6.7 循环中的下标6.7.1 随机访问6.7.2 循环中的下标跳跃访问6.7.3 连续访问 6.12 编译器指令循环展开 7. 结构体7.1 字节对齐7.1.1 两个 float对齐到 8 字节7.1.2 三个 float对齐到 12 字节7.1.3 添加一个辅助对齐的变量对齐到 16 字节 7.2 C11 新语法alignas7.5 结构体的内存布局AOS 与 SOA7.5.1 AOS紧凑存储多个属性7.5.2 SOA分离存储多个属性7.5.3 AOSOA中间方案 7.9 测试一下加速了多少倍 8. STL 容器8.1 std::vector也有指针别名问题8.1.1 __restrict能否用于 std::vector8.1.2 解决方案pragma omp simd 或 pragma GCC ivdep 8.4 std::vector也能实现 SOA 9. 数学运算9.1 数学优化除法变乘法9.2 编译器放弃的优化分离公共除数9.2.1 解决方案1手动优化9.2.2 解决方案2-ffast-math 9.3 数学函数请加 std:: 前缀9.4 -ffast-math 的另一优点9.4.1 开启前sqrt 矢量化失败9.4.2 开启后sqrt 矢量化成功 9.5 嵌套循环直接累加有指针别名问题9.5.1 解决方案1先读到局部变量累加完毕后再写入9.5.2 解决方案2先累加到初始为 0 的局部变量再累加到 c 10. 优化手法总结在 CMake 中开启的几个开关 Reference:
【公开课】编译器优化与SIMD指令集#410分钟速览 C20 新增特性
相关文章
C 字节对齐向量化运算 和 EIGEN_MAKE_ALIGNED_OPERATOR_NEW
本次的主题是编译器优化。编译器就是从源代码生成汇编语言。所以这里要从汇编语言的角度来理解编译器是怎么优化的以及我们如何用好它。
1. 汇编语言
首先讲解下什么是汇编语言。
下图为某 x86 的 64 64 64 位架构它有以下寄存器 寄存器在 CPU 内它的速度比内存快。如果读到寄存器里然后再计算就比较高效。所以上图的 x64 就提供了这么多的寄存器其中白色的这些是 32 32 32 位模式下就有的而 64 64 64 位以后不仅把原来 32 32 32 位的这几个扩充到 64 64 64 位它还额外追加了 8 8 8 个寄存器这样我们用起来就更方便了。
图中 RIP 是它当前执行的代码的地址也是扩充到了 64 64 64 位。还有 MMX、TMM、XMM都是用于存储浮点数的寄存器。一个 XMM 有 128 128 128 位宽(YMM 256 256 256 位)而 float 有 32 32 32 位宽所以这里可以塞下四个 float 或者塞两个 double。这样它们在运算加法的时候就可以两个 double 一起来算这样它效率就更高了。
1.1 通用寄存器32位时代
开始说的 x86 架构中 32 32 32 位只有以下 8 8 8 个寄存器
eax, ecx, edx, ebx, esi, edi, esp, ebp
其中
esp 是堆栈指针寄存器和函数的调用与返回相关eax 是用于保存返回值的寄存器。
1.2 通用寄存器64位时代
到了 64 64 64 位以后又新增了 8 8 8 个寄存器。 64 64 64 位 x86 架构中的通用寄存器有
rax, rcx, rdx, rbx, rsi, rdi, rsp, rbp, r8, r9, r10, r11, …, r15
其中
r8 到 r15 是 64 64 64 位 x86 新增的寄存器给了汇编程序员更大的空间降低了编译器处理寄存器翻车(register spill)的压力
寄存器多有什么好处呢比如局部变量有 16 16 16 个那它们就都能够存进寄存器里而不需要存到内存上这样它读写就更快了。因此 64 64 64 位比 32 32 32 位机器除了内存突破 4 4 4GB 的限制外也有一定性能优势。
1.3 8位16位32位64位版本
从前两小节可以看到 32 32 32 位的叫 eax而到了 64 64 64 位就变成了 rax它们之间有什么关系呢它们是共用前 32 32 32 位的关系就是 eax 这个地方的值和 rax 的低 32 32 32 位是共用的。同理还有 16 16 16 位的 ax 和 eax 共用的低 16 16 16 位然后 ah 是 ax 的高 8 8 8 位、al 是低 8 8 8 位。
当然以 r 开头的这些数字编号寄存器也是一样的它们通过 b、w、d、都没有 来区分的。
1.4 ATT 汇编语言
汇编语言大致分为两种
一种是 Intel 模式的汇编它写寄存器就直接写 eax写操作数比如 eax 赋值给 edx就把 edx 写在前面eax 写在后面然后用 mov 指令把 eax 赋给 edx。另一种为 ATT 汇编。它恰恰相反它读的数字写在前面写的数字写在后面也就是说下图内的 movl %eax, %edx 是往右移动的Intel 是往左移动的。 操作数长度Intel 就直接 mov而 ATT 后面要加一个 movl代表是 l(long)也就是 32 32 32 位、b(byte) 代表的是 8 8 8 位、w(word) 代表的是 16 16 16 位。访问地址Intel 是更直观的一个 []然后后面接偏移量 lea ax, [dx 0x10]而 ATT 把偏移量写在 () 前面后面来一个 (%dx) 代表它偏移的寄存器。
总之 ATT 非常复杂但是 GCC 用的就是这一种。
1.5 返回值通过 eax 传出
比如说有一个函数 fun()右图中 ret 是函数的返回指令movl 是赋值指令。所以可以看到函数被编译成了把 42 42 42 复制给 eax 然后返回就可以看出这个返回值是通过 eax 传出去的。
int func() {return 42;
}这里是使用下面指令来编译的一个 cpp 文件变成一个 .S 文件-S 代表生成的不是 .o 文件而是 .S 的汇编语言文件。
-fomit-frame-pointer 可以让生成代码更简洁。作用为如果函数不需要 frame pointer就不要将 frame pointer 保留在寄存器中。当打开优化选项-O, -O2, -O3, -Os 时或者对某些平台不打开任何优化选项时-fomit-frame-pointer 会被默认打开
-fverbose-asm 让上图的每一条汇编前面有一个注释来提示这一条指令代表的是源文件当中的第几行。比如 return 42 就代表了 movl $42 %eax 这一行。
gcc -fomit-frame-pointer -fverbose-asm -S main.cpp -o /tmp/main.S编译器会自动设置寄存器优化不需要手动指定。
1.6 前6个参数分别通过 ediesiedxecxr8dr9d 传入
下面可以看到有一个有很多参数的函数它有 6 6 6 个参数它们通过寄存器传入的
可以看到这里显示把所有传入的寄存器先给存到一个堆栈上面rsp 就代表堆栈而这个 - 就代表是堆栈上的某一个地址。它的返回值不是返回了 a 嘛而 edi 它不是存到了 a 变量吗它现在又取出来设为这个返回值调用它的人一看 eax 就知道它返回了多少。
movl %edi, -4(%rsp) 相当于 *(rsp - 4) edi。
1.7 开启优化-O3
对先前的指令稍加改进通过加一个 -O3 选项加了这个 flag 以后它就比刚才更优化
gcc -fomit-frame-pointer -fverbose-asm -S main.cpp -o /tmp/main.S刚才还把 b、c、d、e、f 都传到栈里了现在直接简单了直接把 a 传过去就给送到 eax。它只需要一行指令就够了这就是编译器的自动优化。它发现这几个存到栈后来没使用过哇所以就直接把这些指令全砍了。然后它又一想欸我这写入了一遍栈又读了一遍栈没意思啊直接把 edi 复制给 eax 不就好了嘛所以它就优化成了这样movl %edi, %eax 相当于 eax edi
int func(int a, int b, int c, int d, int e, int f) {return a;
}所以开启这个选项之后它就能够生成更精炼更高效的代码。
1.8 32位乘法运算imull
除了可以 movl 来复制之外汇编语言还支持乘法、加法之类的指令。比如乘法就是 imul和 movl 是一样的代表它的操作数是 32 32 32 位的。看看下面的这个例子做了些什么
int func(int a, int b, int c, int d, int e, int f) {return a;
}edi 我们知道代表的第一个参数 aesi 代表的第二个参数 b。x86 汇编就是这样它就是就地乘没有写入到另一个寄存器它是一种 CISC 指令的设计。这里首先把 edi 赋值给 eax所以它就相当于先把 eax 变成了 a再把 b 乘到 a 里面就变成所需的返回值了。
1.9 64位乘法运算imulq
然后就是 64 64 64 位的乘法。之前提到了 l 代表 32 32 32 位而 q 代表 64 64 64 位所以这里的 long long 它是 64 64 64 位的。 64 64 64 位寄存器也从 e 寄存器变成 r 系列寄存器就更宽了能存储 64 64 64 位。
int func(int a, int b, int c, int d, int e, int f) {return a;
}1.10 整数加法被优化成 leal 了
这里的整数加法我们以为它会生成一个 addl也就是 add没想到它却变成了一个 lea 指令。
lea 是什么呢可以看到 (%rdi,%rsi) 是一个地址的操作数也就是这个地址其实相当于 *(rdirsi)而 lea 是加载表达式的地址相当于 不是把表达式的值给取出来。它取的是这个地址所以这个就相当于 eax *(rdi rsi)也就是这两个会抵消也就相当于 eax rdi rsi。所以说这是在妙用加载地址指令把它当作 add 来操作就可以更简练。
1.11 整数加常数乘整数都可以被优化成 leal
leal 除了可以直接执行加法它还可以执行任何一次函数。比如下面的 (%rdi,%rsi,8)就代表把第二个数乘以了 8 8 8。因为这种线性变换经常用于地址访问中所以 x86 把它做进了地址访问的操作符内。同上一节lea 却不读这个地址的值而是将这个地址读出来。所以说这就变成了我们可以把任何一个一次函数写在一条指令里。所以说一次函数在 x86 上都是很高效的。 1.12 指针访问对象线性访问地址
那么线性变换为什么要做成指令呢就是为了针对下面这种情况比如 func(int* a, int*b)a 是一个指针这里要返回 a[b]你可能会想 a 是怎么知道 a[b] 的地址然后读取它的
这里不能简单的 ab因为 a 是一个 int 类型的指针如果直接在汇编里面 ab它会变成一个 char 类型的加。所以说这里要 char 类型的加加上 sizeof(int) 乘以 b。因为 int 类型的大小是 4 4 4所以这个偏移量也要乘以 4 4 4 才能访问到正确的地址。所以这里就用了 x86 提供的这个很方便的线性函数来访问。
这里的 moveslq 语句又是什么意思呢因为我们刚刚使用的 int 是 32 32 32 位的而指针和地址都是 64 64 64 位的所以说要用这个 64 64 64 位的 a 去加上一个 32 32 32 位的 b 之前要把 b 转换成 64 64 64 位的。可以看到这里是把 esi 这个 32 32 32 位变成 rsi 这个 64 64 64 位的了。这样以后才能进行线性访问。
1.13 指针的索引尽量用 size_t
如果要避免上一节的转换呢就可以使用 sdtdint 里提供的 std::size_t。这个 size_t 能够保证在 64 64 64 位系统上就是 int64而 32 32 32 位系统上就是 int32所以就不需要再进行刚才先从 32 32 32 扩展到 64 64 64它直接就是 64 64 64 位的。所以说它有可能更搞笑而且它还有一个好处就比如数组的大小超过 INT_MAX也就是数据大到超过 2 31 2^{31} 231这时候 int 就不仅是效率问题它是会出错的。所以我们就要用 64 64 64 位的 size_t 来表示超过了那个大小的索引。 所以建议如果用于下标的话最好用 size_t或者说循环体的 int i0; ixxx也推荐使用 size_t。
1.14 浮点作为参数和返回xmm 系列寄存器
高性能编程中经常会用到浮点数所以说 CPU 也对它们做了专门的指令。比如 add 指令刚才提到 addl 代表两个 32 32 32 位整数相加。这里的 a d d s s addss addss 的 s 代表 single也就是单精度浮点数所以 a d d s s addss addss 就代表两个数相加。它传参数也不是 edi、esi 了它直接用 xmm 系列就是 xmm0 传 axmm1 传 b然后我们把 xmm1 加到 xmm0因为正好 xmm0 是用于返回值的所以我们这里直接返回了就得到 ab 了。 1.15 什么是 xmm 系列寄存器
刚才提到了 xmm 这个系列的寄存器它们都有 128 128 128 位宽可以容纳 4 4 4 个 float 或者 2 2 2 个 double。
刚才的例子中因为只有一个 float 存在一个 128 128 128 位的寄存器内所以只用到了它最低的 32 32 32 位。但是这样也没问题因为我们刚才说的是addss 它只会加最低位。这就要说到下一节将提到的 addss 了。
1.16 addss 是什么意思
addss 可以拆成三个部分add、s、s
add 表示执行加法操作。第一个 s 表示标量(scalar)只对 xmm 的最低位进行运算也可以是 p 表示矢量(packed)一次对 xmm 中所有位进行运算。第二个 s 表示单精度浮点数(single)即 float 类型也可以是 d 表示双精度浮点数(double)即 double 类型。
举个例子
addss一个 float 加法。addsd一个 double 加法。addps四个 float 加法。addpd两个 double 加法。
比如下图的 xmm0 和 xmm1 addps 像左边这样同时计算四个的加但如果是 addss 的话它只会对最低位进行一个加法而其他位都保留 xmm0 原来的值。
如果你看到编译器生成的汇编里有大量 ss 结尾的指令则说明矢量化失败如果看到大多数都是 ps 结尾则说明矢量化成功这样生成代码就是比较高效的。
1.17 为什么需要 SIMD单个指令处理四个数据
这种单个指令处理多个数据的技术称为 SIMDsingle-instruction multiple-data它可以大大增加计算密集型程序的吞吐量。
为什么我们需要这些指令将四个打包到一起这样速度更快。
因为 SIMD 把 4 4 4 个 float 打包到一个 xmm 寄存器里同时运算很像数学中矢量的逐元素加法。因此 SIMD 又被称为矢量而原始的一次只能处理 1 1 1 个 float 的方式则称为标量。
在一定条件下编译器能够把一个处理标量 float 的代码转换成一个利用 SIMD 指令的处理矢量 float 的代码从而增强你程序的吞吐能力
通常认为利用同时处理 4 4 4 个 float 的 SIMD 指令可以加速 4 4 4 倍。但是如果你的算法不适合 SIMD则可能加速达不到 4 4 4 倍也有因为 SIMD 让访问内存更有规律节约了指令解码和指令缓存的压力等原因出现加速超过 4 4 4 倍的情况。
2. 化简
然后来看一看编译器还有哪些能做的优化。
2.1 编译器优化代数化简
首先一件事是要使它能够执行一些基本代数化。比如看下图左边的例子这里 c c c 是 a b ab ab d d d 是 a − b a-b a−b那么它们相加起来是不是 b b b 就被抵消了所以编译器很聪明它直接把 a a a 作为返回值。
2.2 编译器优化常量折叠
如果我看到 a a a 和 b b b 都是常量然后它们还相加起来。我不是已经知道两个常量了把它们拿过来然后相加变成 42 42 42它就直接优化成 return 42 了。 2.3 编译器优化举个例子
它更疯狂的是甚至可以弄一个 for 循环它看到初始值是一个常数而 i 每次的值也都是常数那么它可以把 1 1 1 加到 100 100 100 给优化成直接返回 5050 5050 5050 都没有问题。
2.4 编译器优化我毕竟不是万能的
当然编译器也没那么聪明就是如果把代码写的很复杂比如用了一些 STL 容器库。当它在看到 arr.push_back() 的时候就停止思考了。这时它就会放弃优化干脆去一个个调用 vector。所以说像 vector 这种会在堆上分配内存的容器编译器通常是不会去进行优化的。所以说尽量把代码写的简单一点编译器能够看得懂它才能帮你优化但如果用的很复杂的话编译器就认为优化很复杂的抽象语法树需要花很长时间编译器就觉得不划算于是放弃优化-----不要把答案藏的太深它的搜索范围是有限度的它不会无限制的搜索。所以要把代码简化从而它的搜索时间就能变短就能找到正确的优化。 结论尽量避免代码复杂化把代码写的简单一点避免使用会造成 new/delete 的容器。简单的代码比什么优化手段都强。
2.5 造成 new/delete 的容器即内存分配在堆上的容器
下表可以看到哪些内存分配在堆上哪些又在栈上
存储在堆上妨碍优化存储在栈上利于优化vector, map, set, string, function, anyarray, bitset, glm::vec, string_viewunique_ptr, shared_ptr, weak_ptrpair, tuple, optional, variant
比如 vector、map、set 这种一般来说这些老的容器都是在堆上的。
为什么要区分堆和栈呢全部存在栈上不好嘛事实是有区别的比如说 array它是固定大小的这是它的一个缺点但是它的优点是它可以存在栈上。那为什么 vector 不能被存在栈上因为它可以动态的 push_back()也就是它的大小是变化的而栈上只能一次性开辟一定的大小而不能动态扩充大小。所以这时候像 map、set、string 这种可以动态扩展的得存储在堆上。像 unique_ptr 这种它肯定是去调用了 new 和 delete 的所以是在堆上。 (vector 这种肯定也是存在堆上的)
2.6 那改用 array 试试
既然 array 存储在堆上那么将之前的示例改写成 array 的是不是就能优化成功了呢 从图中可以看到还是优化失败。
2.6.1 那改用手写的 reduce
这里再改一下改用手写的 reduce它还是优化失败
2.6.2 那改小到 10成功了
那么再修改一下把这里的 100 100 100 改成 10 10 10它优化成功了 这是因为如果代码过于复杂涉及的语句数量过多时编译器会放弃优化
还是那句话如果代码很简单那么其实不需要什么优化手段编译器能够理解你在干什么那么它就能优化了。
2.7 constexpr强迫编译器在编译期求值
当然上面的例子中如果的确想要 100 100 100 这么大的能自动在编译器求值可以考虑使用 constexpr 语法。这时候这个函数强制编译器在运行时求值这会让编译器花费较长的时间即编译变慢。所以说如果想迫使编译器优化即进行常量折叠就使用 constexpr 关键字。
不过constexpr 函数中无法使用非 constexpr 的容器比如前面提到的 vector、map、set、string。因为要让编译器理解全部它必须全部分配在栈上而不能分配在堆上。据说 C20 开始 vector 可以在编译期分配了new 和 delete 也可以 constexpr 了 (10分钟速览 C20 新增特性)。但是 C17 还是不行的C17 的 constexpr 还是只能用 std::array 这些在栈上的容器。 你甚至可以把它作为一个模板即使这个数再大它也会去算但是会让编译变得很慢因为下面示例中的 50000 50000 50000 次迭代实在编译期进行的。
3. 内联
3.1 调用外部函数call 指令
函数分为两种外部的函数、内部的函数。
什么是外部函数就是像下面这种只要一个申明然后实际的实现在另一个文件的这种就叫外部函数。这种编译期没办法优化它只能生成一个 call 指令 来调用这个函数
PLT 是 Procedure Linkage Table 的缩写即函数链接表。链接器会查找其他 .o 文件中是否定义了 _Z5otheri 这个符号如果定义了则把这个 PLT 替换为它的地址。可以看到 PLT 在 call _Z5otheriPLT 出现代表这个函数是外部函数。它会在链接的时候如果另一个文件定义了 _Z5otheri 这个符号它就会把那个符号的地址填充到这里。所以如果别的函数里没有定义 _Z5otheri它这里就没办法填充从而链接器就会报错。
gcc -fomit-frame-pointer -fverbose-asm -S main.cpp -o /tmp/main.S3.1.1 编译器优化call 变 jmp
上面一小节是没开优化的结果开优化以后就没有 call 指令了。它直接跳转到 jmp 的 other 这个地址。在前面一小节调用完 func 一样是要返回的不如让 other 代为返回这样也是可以的
gcc -O3 -fomit-frame-pointer -fverbose-asm -S main.cpp -o /tmp/main.S3.2 多个函数定义在同一个文件中
刚才提到外部函数会让编译器无法优化但如果是内部函数呢内部函数是声明和定义在同一个文件就是它定义在 func 调用它的相同文件。编译器在编译 func 的同时它是看得到 other 的定义的。也就是说它知道 other 里面什么都没做直接返回了 a a a从而它就可以优化了。下图内上面一个红框为 other 的函数下面的是 func 的函数。 也就是说这样的话它本来不优化的话是会直接去调用的而开了优化之后定义在同一个文件里是没有 PLT 的这样链接器也不用到时候把它替换了。
gcc -fomit-frame-pointer -fverbose-asm -S main.cpp -o /tmp/main.S3.2.1 编译器优化内联化
如果在同一个文件里而且开启了 -O3这时候我们发现 func() 根本没有调用 other()它直接返回了 233这是为什么呢 因为编译器看到 other 就是直接返回 a a a所以这里就直接替换成了 return 233 了。
这就是内联当编译器看得到被调用函数other实现的时候会直接把函数实现贴到调用它的函数func里。
没使用关键字 inline 而开启了 -O3 也会内联编译器只要看得到这个函数体就行了它自动帮你 inline不需要去指定。
gcc -O3 -fomit-frame-pointer -fverbose-asm -S main.cpp -o /tmp/main.S注意
只有定义在同一个文件的函数可以被内联否则编译器看不见函数体里的内容是没法内联的。为了效率我们可以尽量把常用函数定义在头文件里然后声明为 static(这里的重点是要声明为 static)。这样调用它们的时候编译器看得到它们的函数体从而有机会内联。
3.2.2 局部可见函数static
如果 other 声明为 static就代表只有这文件可见编译器就干脆不生成 other 函数了这样的话还是可以内联。如果不是 static就像上一小节那样它也是可以内联的不过会将额外生成的 other 暴露出来。 与上一小节相比可以看见编译器内少了 _Z5otheri 的定义。这是因为因为 static 声明表示不会暴露 other 给其他文件而且 func 也已经内联了 other所以编译器干脆不定义 other 了。
gcc -O3 -fomit-frame-pointer -fverbose-asm -S main.cpp -o /tmp/main.S3.2.3 inline 关键字不需要
在现代编译器中它们都足够只智能知道哪些函数要内联不需要去提醒它下图为加与不加 inline 的代码 、 可以看到提醒前和提醒后的代码是完全一样的编译器都帮着内联了。
结论 在现代编译器的高强度优化下加不加 inline 无所谓。编译器不是傻子只要它看得见 other 的函数体定义就会自动内联。 内联与否和 inline 没关系内联与否只取决于是否在同文件且函数体够小。要性能的定义在头文件声明为 static 即可没必要加 inline。static 纯粹是为了避免多个 .cpp 引用同一个头文件造成冲突并不是必须 static 才内联。如果你不确定某修改是否能提升性能那你最好实际测一下不要脑内模拟。 inline 在现代 C 中有其他含义但和内联没有关系它是一个迷惑性的名字。
在线做编译器实验推荐这个网站https://godbolt.org/比如在下面写了一个平方函数可以在右侧看到它自动变成了图上所示的这些指令。 当然也可以在 Compiler options 处加上优化开关可以看到它就优化成下面这个样子了
4. 指针
4.1 指针别名现象pointer aliasing
我们知道 C 语言的历史遗产就是指针。下面弄一个 func 函数可以看到它将 a a a 指向的值取出来然后写入到 c c c再把 b b b 指向的值写入到 c c c。那你肯定想先把 a a a 复制到 c c c再把 b b b 复制到 c c c那第一个语句不就浪费了嘛。我直接将 b b b 复制给 c c c 不就行了因为 a a a 的值被覆盖了。那么为啥编译器明明是开了优化它还是复制了两遍呢 考虑这种调用方式 b b b 和 c c c 指向同一个变量 优化前相当于 b a ; b b ; ba; bb; ba;bb; 最后 b b b 变成了 a a a 如果优化了 b b ; bb; bb; 这样 b b b 就没有发生改变这就是编译器放弃优化的原因。
编译器并不知道 a a a 和 b b b 是否指向了同一个地址所以如果它优化掉的话结果就不对了。
编译器是保守的它宁愿变慢也不要出错。
4.1.1 告诉编译器别怕指针别名__restrict 关键字
如果你想让编译器放心大胆告诉它 b b b 永远不会等于 c c c 的可以这样写
这时 gcc 特有的 __restrict 关键字它在 语言里是标准而在 C 里却没有标准所以需要加上 __ 前缀代表它是当前编译器特定的。__restrict 是一个提示性的关键字是程序员向编译器保证这些指针之间不会发生重叠。所以 __restrict 提示以后它不会再重复两遍了 它只会重复一遍。也就是说向编译器保证 b b b 和 c c c 是不同的值从而它就可以安全的把 *c*a 给优化掉
4.1.2 __restrict 关键字只需加在非 const 的即可
那是不是在程序里每一个出现指针的地方都得加个 __restrict 呢不一定只需要非 const 的加一个就行了。因为只有写入才会造成指针别名的问题而如果只读的话就没有任何影响。即所有非 const 的指针都声明 __restrict。
4.1.3 禁止优化volatile
除此之外还有一个让编译器不要优化的关键字就是 volatile。
可以看到上面示例中先是把 a a a 赋值为 42 42 42然后有返回了 *a。也就是说这时候先把 42 42 42 写入然后这里直接被编译器优化成 return 42 了。因为它想刚刚我写入的 42 42 42 嘛但是万一这个 a a a 指针是指向一个多线程同时在写入的地方也就是比如 *a42 我赋值 42 42 42 了以后又有某个线程进来把 a a a 修改了这时候这个返回值就可能是不一样的。所以这时候可以告诉编译器不要优化这个变量就是 int volatile
这时候它就会硬生生去写一遍再读一遍生怕函数内再插入了什么东西。如果想优化的话就不要加 volatile 了。如果在使用多线程后想要测试这个内存读写有多快就可以使用关键字 volatile它不会优化读写从而可以测试它的性能。
4.1.4 注意一下区别 volatile volatile int *a 或 int volatile *a __restrict int *__restrict a 语法上区别volatile 在 * 前面而 __restrict 在 * 后面。 功能上区别volatile 是禁用优化__restrict 是帮助优化。 是否属于标准上区别volatile 和 const 一样是 C 标准的一部分。restrict 是 C99 标准关键字但不是 C 标准的关键字。__restrict 其实是编译器的“私货”好在大多数主流编译器都支持。 volatile 是可以针对不是指针的而 __restrict 必定是针对指针。
4.2 编译器优化合并写入
说道指针还有一点就是下面示例中有两个写入第一个是针对 a[0]然后是 a[1]这两个分别是 int也就是 32 32 32 位的写入。在编译出来之后就变成了一个 q也就是变成了一个 64 64 64 位的写入。因为这里的两个 32 32 32 位是连续的地址所以它能够自动优化成一个 64 64 64 位的写入
4.2.1 合并写入不能跳跃
刚才说的写入能够变成单独一个 64 64 64 位的但如果地址中间跳了变成了 a[0] 和 a[2]中间 a[1] 空了那它没办法优化了只能变成写入两个 32 32 32 位的了。 所以说我们在设计数据结构的时候尽可能把它设计的紧凑点不要把很多无关的变量交错排列这样它就很难优化了。
5. 矢量化
5.1 更宽的合并写入矢量化指令SIMD
前面说道可以将 2 2 2 个 int 变成一个int64其实还可以把 4 4 4 个 int 优化成一个 __m128也就是 xmm 寄存器。比如下图中有 4 4 4 个 int因为 4 4 4 个 32 32 32 位就是 128 128 128 位所以就可以用 xmm 来实现一次写入 4 4 4 个 int xmm 是 SSE 引入的它是 128 128 128 位的。它本来是用于存储 4 4 4 个 float 的但它也可以存 4 4 4 个 int。
这里还有一个 movupsmove unaligned packed single之前都是没有这个 u 的这个 u 是特有的它代表上面 %rdi 这个地址不一定对齐到 16 16 16 字节。也可以是 movapsmove aligned packed single这时候就是向它保证 %rdi 一定是对齐到 16 16 16 字节的这样可能有微乎其微的提升。
5.1.1 SIMD 指令敢不敢再宽一点
刚才说的是 4 4 4 个可以变成 128 128 128然后 8 8 8 个就可以变成 256 256 256这个是 ymm 寄存器。但我为什么明明像下面这样写它却用了两个 xmm 的寄存器而没有优化成一个 ymm 呢 这是因为编译器不敢保证你的电脑支持 AVX。也就是说编译器它只能生成、只能保证因为所有 64 64 64 位的电脑都支持 xmm所以它只能保证 cmm 是能用的而 256 256 256 位的 ymm 只有一些比较新的电脑上才有它就不敢用了。
5.1.2 让编译器自动检测当前硬件支持的指令集
所以说你要让它敢用可以加以下 flag跟它说你来检测一下我的电脑是否支持 AVX如果我的电脑支持那你就可以用 ymm 优化了 gcc -marchnative -O3 比如上面的示例中写了 8 8 8 个编译器也的确用 ymm 读取了一次然后写入。这样就更加高效了。
-marchnative让编译器自动判断当前硬件支持的指令。不过注意这样编译出的程序可能放到别人不支持 AVX 的电脑上没法运行。
所以如果用于发布到特定平台的话最好还是不要用这个 flag。
5.2 数组清零自动调用标准库的 memset
下面为数组清零的代码可以看到代码内除了清零什么都没做也没有调任何标准库函数而在右边汇编内它缺变成了一个对 memset 的调用这是为什么呢 这是因为编译器是和标准库绑定的。所以说在这里生成一个像是把整个数组清零操作它会识别到然后就能够一个对标准库的调用了。这样就不必为了高效手动改写成对 memcpy/memset 的调用影响可读性。编译器会自动分析是在做拷贝还是清零并优化成对标准库 memcpy/memset 的调用标准库里面的实现通常是更高效的。
5.3 从 0 到 1024 填充SIMD 加速
现在有一个从 0 0 0 到 1024 1024 1024然后填入到数组 a[] 中:
void func(int *a) {for (int i 0; i 1024; i) {a[i] i;}
}它的汇编如下图所示 其中 paddd 表示 4 4 4 个 int 的加法movdqa 表示加载 4 4 4 个 int。
是不是挺难看懂的。实际上它就是把代码优化成下面这个方便理解的伪代码
void func(int *a) {__m128i curr {0, 1, 2, 3};__m128i delta {4, 4, 4, 4};for (int i 0; i 1024; i 4) {a[i : i 4] curr;curr delta;}
}这里 i 变成 i4 了就是一次可以写入 4 4 4 个然后我们这里在 a [ i ] a[i] a[i] 写入 0 , 1 , 2 , 3 {0,1,2,3} 0,1,2,3 这四个数。在下一步的时候把 curr 给全部加上 4 4 4curr 就变成 4 , 5 , 6 , 7 4,5,6,7 4,5,6,7 了这时候再写入就是 4 , 5 , 6 , 7 4,5,6,7 4,5,6,7再加一下就是 8 , 9 , 10 , 11 8,9,10,11 8,9,10,11。这样和原来的运行结果完全一致但却能更加高效因为它是用 SIMD 指令并行去加的。
5.4 如果不是 4 的倍数边界特判法
上面的示例中有一个缺点因为这里是 i4如果上面不是 1024 1024 1024 而是 1023 1023 1023 的话那它这里就会多写入一个 int而这个地址可能是别人的数据就把它覆盖掉这该怎么办呢
void func(int *a, int n) {for (int i 0; i n; i) {a[i] i;}
}可以用边界特判法。刚才是一个固定的 1024 1024 1024编译器看得到它是一个 4 4 4 的倍数可以直接像上一小节那样写。但在边界不是 4 4 4 的倍数的时候它就生成了一个超复杂的代码 它做的事是假如 n 是 1023 1023 1023 的话它会先把 n 编程一个刚才优化过的 1020 1020 1020 个元素的填入这样每次可以处理四个。然后还剩下三个是没办法直接一次写入了它就变成了传统的标量模式来一个处理一个。所以这种思想就是如果 n 不是 4 4 4 的倍数就先取其中和 4 4 4 整除的部分然后剩下不整除的部分再用低效的标量代码去处理。这样大部分 1020 1020 1020 个数据都是矢量化的加而剩下的 3 3 3 个数据才是标量加。所以它既高效又不会犯错这就是边界特判。
编译器做优化时它会自己去判断。但如果要自己手动去写 mm 什么的 SIMD 指令的话需要手动去判断这个边界。
5.4.1 n 总是 4 的倍数避免边界特判
如果能保证 n n n 总归是 4 4 4 的倍数不想让它这么复杂的生成两个版本可以这样写
void func(int *a, int n) {n n / 4 * 4;for (int i 0; i n; i) {a[i] i;}
}用 n 先除以 4 4 4因为除是整除就让 n 会落入 4 4 4 的倍数中这样的话编译器能够发现 n 始终是 4 4 4 的倍数即 n % 4 0 n \% 40 n%40从而它就不会生成边界特判的分支了相当智能
5.5 假定指针是 16 字节对齐的assume_aligned
GCC 内置的函数都是以两个下划线 __然后 builtin 开头的。(int *)__builtin_assume_aligned(a, 16) 是在告诉编译器保证 a a a 是 16 16 16 组合对齐的。
void func(int *a, int n) {n n / 4 * 4;a (int *)__builtin_assume_aligned(a, 16);for (int i 0; i n; i) {a[i] i;}
}来看看这与上面的示例有什么区别 先前这里是 movups这里变成了 movaps。这就让 CPU 知道保证是 16 16 16 字节对齐的传 CPU 可能更快一点也可能不快。但是这样的话就是调用 GCC 才有的函数如果在微软编译器上就不能通过。
所以为了通用C20 在 memory 头文件内引入了这个模板函数 std::assume_aligned然后通过模板参数来制定对齐到 16 16 16 字节
#include memory
void func(int *a, int n) {n n / 4 * 4;a std::assume_aligned16(a);for (int i 0; i n; i) {a[i] i;}
}5.9 数组求和reduction 的优化
float func(float *a) {float ret 0;for (int i 0; i 1024; i) {ret a[i];}return ret;
}优化成了下面这个样子
伪代码如下
#include x86intrin.hfloat func(float *a) {__m128 ret _mm_setzero_ps();for (int i 0; i 1024; i 4) {__m128 a_i _mm_loadu_ps(a[i]);ret _mm_add_ps(ret, a_i);}float r[4];_mm_storeu_ps(r, ret);return r[0] r[1] r[2] r[3];
}总之就是非常高效。
6. 循环
我们的程序中有 热 和 冷 这两个术语这里的热是指经常被访问的代码。比如上面一节中 float ret0它只会调用一次而这个 for 循环里面被调用了 1024 1024 1024 次。这个调用次数多的地方称为热而调用数少的地方称为冷。一般都是在热的地方优化因为热的地方通常它执行很多遍更容易成为瓶颈而往往循环的地方都能执行很多遍。所以说优化通常都是针对循环的优化而循环也往往是优化的重点。
6.1 循环中的矢量化还在伺候指针别名
这里提供了一个用循环的 func 函数它的工作就是把 b[] 里面的数 1 1 1然后复制到 a[]。
void func(float *a, float *b) {for (int i 0; i 1024; i) {a[i] b[i] 1;}
}来看看这会发生什么 按照我们的理解这个代码应该是可以矢量化的但是编译器却生成了两个版本这是为什么编译器还在担心前面章节提到的 a a a 和 b b b 只想的数组是否有重合。考虑 func(a,a1) 的情况那样会产生数据依赖链没法 SIMD 化。
为了优化而不失正确性编译器索性生成两份代码。 一份是 SIMD 的一份是传统标量的 它在运行时检测 a a a, b b b 指针的差是否超过 1024 1024 1024 来判断是否有重叠现象。
如果没有重叠则跳转到 SIMD 版本高效运行。如果重叠则跳转到标量版本低效运行但至少不会错。
6.1.1 循环中的矢量化解决指针别名
所以我们为了让编译器放心会加上之前提到的关键字 __restrict告诉编译器这两个数组保证不会重合打消编译器的顾虑
void func(float *__restrict a, float *__restrict b) {for (int i 0; i 1024; i) {a[i] b[i] 1;}
}这样它就只生成了一个 SIMD 版而不需要在运行时判断是不是有重合了 这样的话因为不需要分支它效率就能提升代码更为合理。
6.2 循环中的矢量化OpenMP 强制矢量化
#pragma 的作用是设定编译器的状态或者是指示编译器完成一些特定的动作 。#pragma 指令对每个编译器给出了一个方法在保持与 C 和 C 语言完全兼容的情况下给出主机或操作系统专有的特征。依据定义编译指示是机器或操作系统专有的且对于每个编译器都是不同的。
除了可以用 GCC 特有的 __restrict 让编译器放心做 SIMD也可以使用比较跨平台的 OpenMP
void func(float *a, float *b) {
#pragma omp simdfor (int i 0; i 1024; i) {a[i] b[i] 1;}
}OpenMP 是高性能计算的一个框架它可以通过 -fopenmp 来打开 gcc -fopenmp -O3 -fomit-frame-pointer -fverbose-asm -S main.cpp -o /tmp/main.S 使用起来只需要用 #pragma omp simd 语句就行了。它会告诉你下面代码有可能出现数据依赖但是不要担心。这样编译器就知道这里都显式的说 SIMD 了那应该能默认这两个指针不会打架从而它也是只会生成一份代码
6.3 循环中的矢量化编译器提示忽略指针别名
除了可以用上面的两种方法外如果只用 GCC还可以用 ivdep 这个 pragma它是 ignore vector dependency 的简称即忽略矢量依赖关系表示忽略下方 for 循环内可能的指针别名现象。就是说在下面的代码中它可以忽略 b b b 可能依赖于 a a a 的情况这个是 GCC 特有的
void func(float *a, float *b) {
#pragma GCC ivdepfor (int i 0; i 1024; i) {a[i] b[i] 1;}
}其他编译器这个 pragma 可能不一样需要自己去查这里只是拿 GCC 举例。
6.4 循环中的 if 语句挪到外面来
还有下面这种循环的优化。这里作者的用意很明显在 is_mul 为真时执行 a*b否则执行 ab
void func(float *__restrict a, float *__restrict b, bool is_mul) {for (int i 0; i 1024; i) {if (is_mul) {a[i] a[i] * b[i];} else {a[i] a[i] b[i];}}
}然而有 if 分支的循环体是难以 SIMD 矢量化的。所以说编译器会把这 if 语句挪到外面具体是过程如下 可以看到 corl %eax, %eax 内的 eax是参数 is_mul 的寄存器它会先判断这个是 true 还是 false。如果为 true 就跳到 L2可以看到生成 addps 的一个循环反之跳到 L3可以看到 mulps也就是乘法。
它会去提前判断也就是它相当于进行了这么一个优化
void func(float *__restrict a, float *__restrict b, bool is_mul) {if (is_mul) {for (int i 0; i 1024; i) {a[i] a[i] * b[i];}} else {for (int i 0; i 1024; i) {a[i] a[i] b[i];}}
}也就是编译器看到 is_mul 是一个常量把 if 挪到了 for 外面相当于生成了两个版本一个乘法、一个加法。这样就可以里面没有 if 语句从而可以矢量化了。这样写起来比较麻烦所以有时候也像前面那样写。只要编译器知道 is_mul 是循环中不会改变的量它就能够这样优化。
6.5 循环中的不变量挪到外面来
除了上面可以挪到外面的 if还有可以挪到外面的表达式。比如优化之前是长下面这样的
void func(float *__restrict a, float *__restrict b, float dt) {for (int i 0; i 1024; i) {a[i]a[i]b[i]*(dt*dt);}
}优化之后它发现dt*dt 在循环中是不会改变的。那如果先把 dt*dt 计算好之后直接乘就可以了就不要再重新计算 1024 1024 1024 遍了也就是这样写
void func(float *__restrict a, float *__restrict b, float dt) {float dt2 dt * dt;for (int i 0; i 1024; i) {a[i]a[i]b[i]*dt2;}
}所以再汇编中可以看到它先是进行了一个 dt*dt 的运算 mulss %xmm0, %xmm0后面就直接应用这个乘好的 %mm 了就可以节省 1024 1024 1024 次乘法运算 这种思想就是把热的代码尽量移到冷的代码里。
6.5.1 挪到外面来优化失败
如果把上面代码的括号去掉会怎样
void func(float *__restrict a, float *__restrict b, float dt) {for (int i 0; i 1024; i) {a[i]a[i]b[i]*dt*dt;}
}只要去掉 (dt*dt) 的括号就会优化失败因为乘法是左结合的就相当于 (b[i]*dt)*dt。编译器识别不到不变量从而优化失败。由于浮点运算不满足结合律因为浮点不能精确表示实数。 因此要么帮编译器打上括号帮助它识别要么手动提取不变量到循环体外。
6.6 调用不在另一个文件的函数SIMD 优化失败
还有一个会导致 SIMD 优化失败的例子就是调用外部函数。前面提到过外部函数是优化失败的罪魁祸首比如下面代码有一个 for 循环本来这有这个是可以优化成功的而在代码内调用了一个在其他文件的函数声明编译器没办法矢量化这里并不知道 other 是不是会改变 a a a因为编译器并不知道 other 里干了啥哪怕 other 在定义它的文件里是个空函数它也不敢优化。
void other();float func(float *a) {float ret 0;for (int i 0; i 1024; i) {ret a[i];other();}return ret;
}可以看到汇编内全是 ss说明它优化失败了都是标量的。如果全是 ps 的话才说明优化成功。 6.6.1 解决方案放在同一个文件里
所以说尽可能把 other 放在同一个文件里定义这样编译器就能够看到。比如下面的代码
void other() {
}float func(float *a) {float ret 0;for (int i 0; i 1024; i) {ret a[i];other();}return ret;
}这里讲 other 放到了和 func 同一个 .cpp 文件里这样编译器看得到 other 的函数体就可以内联化该代码。(再次提醒是不需要 inline 的) 所以说在热的 for 循环里尽量不要调用外部函数把它们移到同一个文件里或者放在同文件声明为 static 函数。
6.7 循环中的下标
6.7.1 随机访问
像下面这种随机访问也会影响 SIMD使优化失败
void func(float *a, int *b) {for (int i 0; i 1024; i) {a[b[i]] 1;}
}这是因为 b[i] 每次的值是不确定的它可能是跳跃的在访问这时候编译器就没有相应的指令能够生成优化。(理论上这种没什么好的优化方式)
6.7.2 循环中的下标跳跃访问
下面这种情况也比较恶劣就是 i*2也就是说先访问 0 0 0、再访问 2 2 2、 4 4 4…
void func(float *a) {for (int i 0; i 1024; i) {a[i * 2] 1;}
}就如同刚刚说的这种跳跃的访问是不利于 SIMD 的但是编译器就非常自然了它用了一大堆 shufps 指令还是成功的对 a a a 进行了一定的 SIMD 优化。(矢量化部分成功但是非常艰难)
6.7.3 连续访问
所以最好的情况是什么呢也就是直接 a[i]也就是顺序访问。这种情况下编译器能够只用一个指令进行读写。
void func(float *a) {for (int i 0; i 1024; i) {a[i] 1;}
}也就是说不管是编译器还是 CPU都喜欢顺序的连续访问。
6.12 编译器指令循环展开
还有一个优化方式是循环展开。像下面这种循环体非常简单
void func(float *a) {for (int i 0; i 1024; i) {a[i] 1;}
}生成的代码一行是 movups接着的一行是 addq然后是 cmpq。就是说实际执行计算的指令只有一个而进行比较和 i 的指令却用了两个还有一个跳转指令。这样就导致大部分时间都花在跳转和 上了而不是在实际的计算上。 对于 GCC 编译器可以用 #pragma GCC unroll 4表示把循环体展开为四个。添加后的代码为
void func(float *a) {
#pragma GCC unroll 4for (int i 0; i 1024; i) {a[i] 1;}
}比如下面是把四个循环体放在一个循环内然后 i 改成 i4。注意这里不建议手动这样写会妨碍编译器的 SIMD 矢量化
void func(float *a) {for (int i 0; i 1024; i 4) {a[i 0] 1;a[i 1] 1;a[i 2] 1;a[i 3] 1;}
}这样的话它就有 4 4 4 个 movups 和 3 3 3 个其他指令从而实际执行计算的时间就更多了从而就可以避免反复比较的 overhead。(也就是本来是 1 1 1 个 movups 3 3 3 个其他指令优化后变成 4 4 4 个 movups 3 3 3 个其他指令其他指令使用的次数变少了) 注意指令 #pragma GCC unroll 4 是 GCC 特定的笔者目前没有找到什么通用的替代。 4 4 4 这个数字可以改这里代表的是把 4 4 4 个循环体变成了一个可以根据实际的情况决定要用多少。可以根据实际的情况决定要用多少就是小的循环器一般 unroll 一下是划算的但最好不要 unroll 大的循环体否则会造成指令缓存的压力反而变慢。
7. 结构体
这章是重点。
7.1 字节对齐
7.1.1 两个 float对齐到 8 字节
比如我们有一个 MyVec它里面有 x , y x, y x,y 两个值。
struct MyVec {float x;float y;
};MyVec a[1024];void func() {for (int i 0; i 1024; i) {a[i].x * a[i].y;}
}func 内会使用到 x x x 和 y y y 两个成员可以看到非常复杂的代码 里面有 shufps 什么的但最终还是用到了 mulps也就是它的确矢量化成功了。
7.1.2 三个 float对齐到 12 字节
但是如果我们突然想把这个改成三维的了就凭空加一个 z z z然后我们的 func 甚至没有任何变化
struct MyVec {float x;float y;float z;
};MyVec a[1024];void func() {for (int i 0; i 1024; i) {a[i].x * a[i].y;}
}汇编出来的就全部变成了 ss也就是矢量化失败了这是什么原因呢 这是因为刚才之所以能够矢量化是因为它把两个 MyVec 给读出来然后读到一个 SIMD 的 128 128 128 位寄存器里了。而在这里有 3 3 3 个 float 的话它如果要读到一个 SIMD 里 128 128 128 位就是 xyzx剩余的一个 y y y 是没有办法读出来的。所以说这时候编译器就尴尬了它没办法生成一个 SIMD 的读所以说要怎么办呢
7.1.3 添加一个辅助对齐的变量对齐到 16 字节
如果想让它再变回高效甚至可以像下面这样直接加一个 char padding[4]这是一个没有任何用处的空变量
struct MyVec {float x;float y;float z;char padding[4];
};MyVec a[1024];void func() {for (int i 0; i 1024; i) {a[i].x * a[i].y;}
}可以看到这时它又能够优化成功了。可以看到这里生成的 ps 的代码是进行矢量化的 可以发现如果你的 struct 是 2 2 2 的整数幂大小这时候是有利于 SIMD 优化的而如果像刚才那样是三个一组这时候它就没有办法对齐从而导致 SIMD 优化失败。
结论计算机喜欢 2 2 2 的整数幂2, 4, 8, 16, 32, 64, 128…结构体大小若不是 2 的整数幂往往会导致 SIMD 优化失败。
7.2 C11 新语法alignas
除了上面那种直接加一个从来用不到的变量的方法外C11 还新增了 alignas也就是对齐到 16 16 16 字节。这样 MyVec 的起始地址它会对齐到 16 16 16而且它的大小也会变成 16 16 16 的整数倍。(这里的 16 16 16 代表的是字节而不是位)
struct alignas(16) MyVec {float x;float y;float z;
};MyVec a[1024];void func() {for (int i 0; i 1024; i) {a[i].x * a[i].y;}
}可以看到这时候生成的汇编是一样的但是又不需要手动加一个 char padding 那是不是所有结构体打上 alignas(16) 我的程序就会变快 错了有可能不仅不变快反而还变慢SIMD 和缓存行对齐只是性能优化的一个点又不是全部。还要考虑结构体变大会导致内存带宽的占用对缓存的占用等一系列连锁反应比如导致它更容易变成 memory bound从而有可能还会变慢总之要根据实际情况选择优化方案。实际测了以后如果的确变快了那才去加。
7.5 结构体的内存布局AOS 与 SOA
AOSArray of Struct单个对象的属性紧挨着存-----xyzxyzxyzxyzSOAStruct of Array属性分离存储在多个数组-----xxxxyyyyzzzzAOS 必须对齐到 2 2 2 的幂才高效SOA 就不需要AOS 符合直觉不一定要存储在数组这种线性结构而 SOA 可能无法保证多个数组大小一致SOA 不符合直觉但通常是更高效的。
刚才说的结构是不是 x、y、z、padding如下图所示就是先 xyz然后图上的黑框处空一个 padding再 xyz然后空一个 padding。这种结构类型叫 Array of Struct它指的是 x、y、z 单个对象的属性紧紧凑在一起。
与之相对的就是 SOA它会把 1 1 1 个对象拆成 3 3 3 个数组就是一个对象的 x x x 在一个数组里一个对象的 y y y 又在另一个数组里这样的好处就是它不需要去考虑 padding 了。因为这样如果只访问了 x x x 和 y y y 而 z z z 根本就没有用到那这时候就相当于只用到了 x x x、 y y y而如果用 AOS 的话 z z z 和 padding 都相当于没有用的那个属性。所以如果刚才只用 x x x 和 y y y那 CPU 看到就是在不停地跳着两格读从而效率是最低的而如果用 SOA只访问 x x x、 y y y没用 z z z那 CPU 看到的是在访问两个数组从而它能够用 SIMD 优化。所以说 SOA 虽然它好像不符合我们面向对象的思想但它其实对 CPU 更友好。
7.5.1 AOS紧凑存储多个属性
来看看怎么做的。首先是刚才说的比较烂的 AOS这符合一般面向对象编程(OOP)的习惯但常常不利于性能
struct MyVec {float x;float y;float z;
};MyVec a[1024];void func() {for (int i 0; i 1024; i) {a[i].x * a[i].y;}
}我们用上面代码生成的就是一个不能 SIMD 的代码
7.5.2 SOA分离存储多个属性
那要怎么变成 SOA 呢可以将上面代码写成这样
struct MyVec {float x[1024];float y[1024];float z[1024];
};MyVec a;void func() {for (int i 0; i 1024; i) {a.x[i] * a.y[i];}
}之前是 a[1024]现在 a[1024] 不要了把它移动到 MyVec 里就是 x x x 有 1024 1024 1024 个 y y y 有 1024 1024 1024。访问的时候本来是 a[i].x现在变成 a.x[i]就是括号换了下位置。它们分离开来的存储可以看到下面就用到了 ps从而矢量化是成功的 这样不符合面向对象编程(OOP)的习惯但常常有利于性能。又称为面向数据编程(DOP, date-oriented programming)这种在高性能计算中比较常见。
7.5.3 AOSOA中间方案
但是可以发现SOA 有时不利于优化所以说退出了一种中间解决方案就 4 4 4 个对象打包乘以 SOA再用一个 n / 4 n/4 n/4 大小的数组打包成一个 AOS这样既有 AOS 的直观又有 SOA 的高效
struct MyVec {float x[4];float y[4];float z[4];
};MyVec a[1024 / 4];void func() {for (int i 0; i 1024 / 4; i) {for (int j 0; j 4; j) {a[i].x[j] * a[i].y[j];}}
}这里其实就相当于把 4 4 4 个变成一个 m128 了。但是这种其实也不常用最常用的还是上面的 SOA。
AOSOA 优点 SOA 便于 SIMD 优化AOS 便于存储在传统容器AOSOA 两者得兼。AOSOA 缺点 需要两层 for 循环不利于随机访问需要数组大小是 4 4 4 的整数倍不过可以用边界特判法解决。在代码中可以看到前面都只需要一个 for 循环而这里却需要两个就很麻烦了而且这对随机访问也非常不友好。
7.9 测试一下加速了多少倍
这里做个总结测试比如刚才的程序有 x x x、 y y y、 z z z 3 3 3 个属性
struct Point {float x;float y;float z;
};Point ps[N];void compute() {for (int i 0; i N; i) {ps[i].x ps[i].x ps[i].y ps[i].z;}
}第一步将它优化成 SOA也就是把 N 移上去。再加上每个编译器特有的 unroll 语句如 GCC 是 #progma GCC unroll 32MSC 也就是微软的比较霸气直接就是 #progma unroll 32
struct Point {float x[N];float y[N];float z[N];
};Point ps;void compute() {for (int i 0; i N; i) {ps.x[i] ps.x[i] ps.y[i] ps.z[i];}
}下面是测试结果 811620 n s 811620ns 811620ns未经优化的耗时 989485 n s 989485ns 989485ns用了 16 16 16 字节对齐以后的效率它耗时反而更长了 176316 n s 176316ns 176316ns如果把原来代码一点不变只是加上一个 parallel for 的效果 218063 n s 218063ns 218063ns使用 SOA 优化的耗时 187422 n s 187422ns 187422nsSOAgrpgrma omp simd 忽略指针别名后的耗时 186657 n s 186657ns 186657ns使用 size_t 作为下标以后的耗时 158938 n s 158938ns 158938ns用 size_t 以后再去 unroll可以看到它甚至比前面直接加一个 parallel 还要快 59488 n s 59488ns 59488ns如果优化以后再上一个并行这样就比谁都快了 541613 n s 541613ns 541613ns使用 AOSOA 的优化它虽然快一点但还是不如 SOA
下面是我电脑上的测试效果差的有点多首先是对齐后的效率是会更快的再者 AOSOA 甚至比 SOA 还快。
图中可以看到一条绿线是无脑并行的而粉线是我们深度优化可以看到再深度优化之后再低数据量的时候甚至超过了无脑并行因为并行需要创建很多线程这也需要时间所以对于小数据甚至超过了它。 这里的结论是SOA 是针对这个案例最高效的数据排布格式。当然不一定所有的案例都可以用 SOA 就能优化需要看情况。
8. STL 容器
前面都是基于 C 语言的指针有些老了。C 喜欢 RAII 思想那就得用 STL 的 vector 容器。
8.1 std::vector也有指针别名问题
首先是一个经典案例就是第一章说到的指针别名问题它不能保证下面代码内的 c c c 和 b b b 是同一个 vector从而它得生成两遍
#include vectorvoid func(std::vectorint a,std::vectorint b,std::vectorint c) {c[0] a[0];c[0] b[0];
}汇编结果如下
8.1.1 __restrict能否用于 std::vector
那我想把这个引用声明 __restrict 行不行
#include vectorvoid func(std::vectorint __restrict a,std::vectorint __restrict b,std::vectorint __restrict c) {c[0] a[0];c[0] b[0];
}可以从下面汇编看到没有任何效果。因为这里只是把 vector 本身做了一个 __restrict 而这个 vector 里的指针它没有上 __restrict这时候编译器还是不知道 c 和 a 它是不是同一地址的
8.1.2 解决方案pragma omp simd 或 pragma GCC ivdep
所以结论就是要么用 #pragma omp simd 让它忽视可能存在的指针别名或者用 #pragma gcc ivdep 也可以 #pragma omp simd
void func(std::vectorint a,std::vectorint b) {
#pragma omp simdfor (int i 0; i 1024; i) {a[i] b[i] 1;}
}#pragma gcc ivdep
void func(std::vectorint a,std::vectorint b) {
#pragma GCC ivdepfor (int i 0; i 1024; i) {a[i] b[i] 1;}
}C/C 缺点指针自由度过高允许多个 immutable reference 指向同一个对象。
所以我们在适当的时候要加上一些提示来帮助编译器优化。
8.4 std::vector也能实现 SOA
先前不是说 SOA 比较好嘛但是如果使用了 vector 该怎么办可以像下面这样把 vector 移上去 优化前(AOS) struct MyVec {float x;float y;float z;
};
std::vectorMyVec a;
void func() {for (std::size_t i 0; i a.size(); i) {a[i].x * a[i].y;}
}优化后(SOA) struct MyVec {std::vectorfloat x;std::vectorfloat y;std::vectorfloat z;
};
MyVec a;
void func() {for (std::size_t i 0; i a.x.size(); i) {a.x[i] * a.y[i];}
}不过需要保证 x x x、 y y y、 z z z 当中一个被 push 的时候 3 3 3 个都被 push。否则的话下面的 for 循环会出错。
9. 数学运算
9.1 数学优化除法变乘法
下面示例接受 a a a 参数然后变成 a/2
float func(float a) {return a / 2;
}返回 a/2生成的汇编如下所示 这里 mulss 是一个乘.long 1056964608 是浮点数 0.5 0.5 0.5 的意思也就是说它把一个除法优化成了更快的乘法。
9.2 编译器放弃的优化分离公共除数
虽然乘法更快但这个示例中它却没有把除法提取成一个倒数出来
void func(float *a, float b) {for (int i 0; i 1024; i) {a[i] / b;}
}为什么它不能优化呢因为它害怕 b b b 是 0 0 0 的情况b 是 0 0 0 的话公式 a[i]/b 会变成 inf 或者说它会报一个错。
9.2.1 解决方案1手动优化
这时候编译器就不敢优化所以我们可以手动进行优化就把 1/b 预先计算出来 然后在前面公式内除法改成乘法
void func(float *a, float b) {float inv_b 1 / b;for (int i 0; i 1024; i) {a[i] * inv_b;}
}这样就能够把 1024 1024 1024 次除法变成 1024 1024 1024 次乘法加一次除法。这样其实是更快的。 也就是说乘法比除法更快。提前计算好 b 的倒数避免重复求除法。
9.2.2 解决方案2-ffast-math
既然前面放弃优化了这里还有一个解决方案就是加选项 gcc -ffast-math -O3
void func(float *a, float b) {for (int i 0; i 1024; i) {a[i] / b;}
}-ffast-math 选项让 GCC 更大胆地尝试浮点运算的优化有时能带来 2 2 2 倍左右的提升。作为代价它对 NaN 和无穷大的处理可能会和 IEEE 标准规定的不一致。如果能保证程序中永远不会出现 NaN 和无穷大那么可以放心打开 -ffast-math。测试发现有时候加了 -ffast-math 是快但是算出来的值差很多 9.3 数学函数请加 std:: 前缀
还有一个问题在于数学函数 sqrt 只接受 double 的如果使用 float 去调用 sqrt它也会返回一个 double而且计算精度也是基于 double 的计算速度会慢一些。而如果想要调用 float 的开根号其实应该用 sqrtf。所以说最好的解决方案应该是 C 的 sqrt 函数它重载了double 和 float 两个版本就能够自动根据拿什么调用它就自动返回什么类型
#include cmath
#include type_traitsvoid func(float *a) {for (int i 0; i 1024; i) {auto x sqrt(a[i]); // wrong and badstatic_assert(std::is_same_vdecltype(x), double);auto y sqrtf(a[i]); // correct but badstatic_assert(std::is_same_vdecltype(y), float);auto z std::sqrt(a[i]); // correct and goodstatic_assert(std::is_same_vdecltype(z), float);}
}也就是推荐不要再用 C 语言全局的 sqrt多用用 std 里面的。
更坑的是 abs如果使用全局命名空间的 abs会发现 abs(1.4f) 1这是因为 abs 只接受 int所以 1.4 1.4 1.4 被隐式的转换成了 int。要用 fabs 才能调用 double 的fabsf 调用 float 的。而 std::abs 它重载了 int、 float、double 就不会出现上面奇怪的现象了。
9.4 -ffast-math 的另一优点
-ffast-math 还有一个优点比如下面是对 a 的每一个数求根号
void func(float *a) {for (int i 0; i 1024; i) {a[i] std::sqrt(a[i]);}
}9.4.1 开启前sqrt 矢量化失败
开启前可以看到这里是没有矢量化的 为什么这里没有矢量化呢因为它生怕 a[i] 是一个负数那么计算到 a[i] 就会出错然后停止。但是如果矢量化了那就变成 a[i] 出错时它已经写入了这里不能保证写入的顺序 所以它就不敢优化。
9.4.2 开启后sqrt 矢量化成功
在开启 -ffast-math 以后就告诉它不要怕我能保证 a 绝对不会出错它就能优化成下面这个
9.5 嵌套循环直接累加有指针别名问题
下面的嵌套循环在计算卷积或者矩阵乘法都会用到
void func(float *a, float *b, float *c) {for (int i 0; i 1024; i) {for (int j 0; j 1024; j) {c[i] a[i] * b[j];}}
}但直接这样写是有问题的可以看到这里 a a a 和 c c c 是有可能重合的甚至 b b b 和 c c c 是重合的。编译器担心 c c c 和 a a a 可能会指向同一个地址而连续判断三个指针是否有重合又过于复杂所以放弃了矢量化。 从这里的汇编可以看到它与前面的章节不同前面章节还生成了两个版本而这里只生成了一个版本即没有生成 SIMD 版本。这就是因为当编译器碰到问题复杂化时它就直接放弃优化了。所以要么像前面的方式添加 __restrict要么使用下面的方式
9.5.1 解决方案1先读到局部变量累加完毕后再写入
可以先把 c c c 读到 tmp然后对 tmp 进行追加读完之后再写回到 c c c。
void func(float *a, float *b, float *c) {for (int i 0; i 1024; i) {float tmp c[i];for (int j 0; j 1024; j) {tmp a[i] * b[j];}c[i] tmp;}
}这样对寄存器更加友好这时候编译器认为不会存在指针别名的问题矢量化成功
9.5.2 解决方案2先累加到初始为 0 的局部变量再累加到 c
另一种更好的方法是将 tmp 初始化为 0 0 0。这与上面方法是有区别的上面一种加法是在 c[i] 已经有值的情况下去加这与如果 c[i] 是一个比较大的值比如 1000 1000 1000而 a a a 是一个比较小的值比如 0.01 0.01 0.01。浮点数的构造有一个指数有一个底数而指数相差太大的话它们两个之间相加的精度就会受损。就比如 1000 0.000001 10000.000001 10000.000001可能还是 1000 1000 1000就导致加出来的结果可能不对所以我们最好是把 tmp 初始化为 0 0 0然后这样再去 c[i] tmp 的话就会更精确。因为这样的话 tmp 就足够大从而不会出现指数位差太远导致精度误差的问题。
void func(float *a, float *b, float *c) {for (int i 0; i 1024; i) {float tmp 0;for (int j 0; j 1024; j) {tmp a[i] * b[j];}c[i] tmp;}
}这里是精度上的提升而不是性能上的提升。
10. 优化手法总结
函数尽量写在同一个文件内避免在 for 循环内调用外部函数非 const 指针加上 __restrict 修饰试着用 SOA 取代 AOS对齐到 16 或 64 字节( 16 16 16 是 SIMD 宽度 64 64 64 是缓存行宽度)简单的代码不要复杂化(把代码写的简单点让编译器看懂太复杂的看不懂就没法优化)试试看 #pragma omp simd循环中不变的常量挪到外面来对小循环体用 #pragma unroll-ffast-math 和 -marchnative(对于 GCC 编译器可以加上这两个让它快 2 2 2 倍甚至 4 4 4 倍都有可能)。
在 CMake 中开启的几个开关 CMake 中开启 -O3 默认的 set(CMAKE_BUILD_TYPE Release) 是 Debug它会生成一些调试但是它的优化就会被关掉。而 Release 模式它就相当于 -O3 了 CMake 中开启 -fopenmp 因为 fopenmp 是只针对 GCC 的开启方式微软的可能不一样所以可以使用这种通用的方式来开启 find_package(OpenMP REQUIRED)
target_link_libraries(testbench PUBLIC OpenMP::OpenMP_CXX)它是做成了一个库的形式。 CMake 中开启 -ffast-math 和 -marchnative target_compile_options(testbench PUBLIC -ffast-math -marchnative)这个好像没办法变成一个跨平台的只能针对 GCC 开启这两个。
