CMU 15-213 CSAPP：程序优化、存储层次与链接器的底层奥秘（Memory System）

写在前面这是系统级编程学习笔记的第三篇。如果我们已经搞懂了汇编指令和内存布局那么接下来的问题就是如何让程序跑得更快现代 CPU 是极其复杂的怪兽仅仅写出“能跑”的代码是不够的。在这篇笔记中我们将从 CPU 的流水线聊到内存的“山峰”最后揭开 C/C 程序员最头疼的黑盒——链接器Linker的神秘面纱。Lec 10 Program OptimizationGeneral 常用优化不要完全指望编译器帮你做所有的事有些算法层面的冗余编译器因为“安全原因”是不敢随便优化的。循环不变式外提 (Code Motion):如果一个计算的结果在每次循环中都不会改变就把它移到循环外面比如for (j 0; j n; j) A[n*ij] B[j];这里的n*i在内层循环里是固定不变的。把它提取成int ni n*i;放到外层就能省下无数次乘法运算。减少计算强度 (Reduction in Strength)用移位取代乘除法:在底层乘法和除法是非常昂贵的指令比如在 Intel Nehalem 架构上整数乘法需要 3 个 CPU 周期。如果乘以或除以 2 的幂一律用或取代。识别乘积序列:如果一个循环中多次使用同一个乘积比如多维数组寻址提前计算并复用或者用加法来替代乘法步进。内存问题与 Cache 友好内存访问模式 (Memory Access Pattern):在高性能的 C 网络编程或是分布式系统架构中内存的连续性几乎决定了系统的吞吐上限。因为 CPU 是按“块Cache Line”从内存读取数据的如果你的访问是连续的空间局部性那么大部分数据都能在极速的 L1 Cache 中命中而不是去慢如蜗牛的内存中取。向量化 (Vectorization):现代 CPU 支持 SIMD单指令多数据流可以一条指令同时处理多个数据比如 4 个 float。编译器有时会自动进行循环向量化前提是你的代码写得足够“规整”。现代 CPU 设计要想榨干 CPU 的性能必须了解它的内部机制流水线 (Pipeline):CPU 就像汽车装配流水线指令被分为取指、解码、执行、访存、写回等多个阶段同时在跑。超标量 (Superscalar) 乱序执行 (Out of order execution):现代 CPU 特别聪明如果后面的指令不依赖前面的结果它可以打乱你的代码顺序并行把它们扔进多个执行单元里算完最后再按顺序拼装回去。分支预测 (Branch prediction):遇到if-elseCPU 会“猜”走哪边猜对了流水线满载猜错了要清空流水线重来性能大打折扣。关联运算 (Reassociation)这招非常神奇改变浮点数加法/乘法的执行顺序能提高并行性比如(a * b) * c变成a * (b * c)。在底层这打破了数据依赖关系让 CPU 的乱序执行引擎可以把两次乘法扔进两条流水线里同时跑从而隐藏计算延迟Latency。获得高性能的铁律选择好的编译器选项如-O2,-O3。避免隐藏的算法低效大O复杂度永远是核心。消除阻止优化的绊脚石函数调用别在循环条件里掉函数不必要的内存引用使用局部变量累加最后再写回内存。Lec 11 The Memory Hierarchy非易失性存储器 (Nonvolatile Memories)DRAM内存断电即丢失而非易失性存储器如 ROM, SSD, 机械磁盘断电依然保命。ROM (Read-Only Memory):现在多指 Flash Memory闪存。主板 BIOS、网卡固件都存在这里。SSD (Solid State Disks):固态硬盘本质上就是成规模的闪存。磁盘访问时间 (Disk Access Time)虽然现在都在用 SSD但理解机械磁盘的延迟构成依然很重要寻道时间 (Seek Time):机械臂移动到正确的磁道所需时间最慢3-9ms。旋转延迟 (Rotational Latency):等待盘片把目标扇区转到磁头下方的时间取决于转速如 7200 RPM。传输时间 (Transfer Time):实际读取数据的时间相对于前两者可以忽略不计。结论磁盘的性能瓶颈几乎全部卡在纯物理运动的“寻道”和“旋转”上。SSD 性能特性顺序访问永远滴神:顺序读写速度极快但随机读写尤其是随机写入性能骤降。为什么随机写入慢SSD 的底层机制决定了它不能直接“覆盖”数据必须先“擦除Erase”整个块Block然后再重新写入。如果要修改块中的一小部分数据就必须把整个块的其他数据都搬到新块去这叫“写放大Write Amplification”。内存层次结构 (Memory Hierarchy)这是一种伟大的架构思想用最昂贵、最快的存储做顶层小容量用最便宜、最慢的存储做底层大容量从而伪装出一个既快又大的存储池。从 L0 (寄存器) - L1/L2/L3 (SRAM 缓存) - L4 (DRAM 内存) - L5/L6 (本地/远程磁盘)。每一层都是下一层的高速缓存。Lec 12 Cache Memories缓存工作的核心基石局部性原理程序天生有一种偏好时间局部性 (Temporal Locality):刚刚访问过的数据很可能马上又要被访问比如循环里的累加器。空间局部性 (Spatial Locality):刚刚访问过的数据附近的内存地址很可能马上被访问比如遍历数组。Miss致命的未命中一旦你需要的数据没在 Cache 里就是一次 Miss未命中。CPU 只能眼巴巴地等数据从下层比如主存慢吞吞地搬上来。这个时候硬件需要决定Placement (放在哪):取上来的数据存到缓存的哪个格子Replacement (替换谁):如果缓存满了要把谁踢出去经典的 LRU 算法登场。几个惊恐的数字99% 与 97% 的天壤之别你以为 99% 命中率只比 97% 好了那么一点点算一笔账命中耗时 1 周期Miss 惩罚 100 周期97% 命中时的平均耗时 1 0.03 * 100 4 周期99% 命中时的平均耗时 1 0.01 * 100 2 周期结论命中率仅提升 2%程序运行速度直接翻倍这就是底层极客痴迷于消灭每一次 Cache Miss 的原因。内存山 (Memory Mountain) 与 矩阵乘法之谜这里迎来了 15-213 课程最经典的篇章之一证明缓存局限性的矩阵乘法实验。深度解析为什么改变循环顺序性能会差这么多在 C/C 中二维数组在内存中是**按行优先Row-major**连续存放的。这意味着当你顺着“行”遍历时比如a[0][0], a[0][1], a[0][2]它们在物理内存里是紧挨着的这完美契合了 CPU Cache 的原理。一旦读取a[0][0]Cache 会顺便把后面几个元素也取进 L1。ijk循环按普通人的直觉写代码内层循环是k。A[i][k]是同行顺延访问极好的空间局部性但是B[k][j]呢随着k递增它在跨行跳跃每次跳跃几百上千个字节。CPU 刚把 Cache 填满你却跳到了完全不相干的地址导致严重的 Cache Miss。kij循环高手的写法把j放到最内层。看看里面在干什么C[i][j] A[i][k] * B[k][j]。此时k和i都是外层循环控制的对于最内层的j来说是个常量。于是C[i][j]同行顺延极好的空间局部性B[k][j]同行顺延极好的空间局部性A[i][k]在内循环中根本不变每次迭代读同一个寄存器即可。所以kij版本几乎完美利用了 Cache性能通常能比ijk快 2 倍以上Lec 13 Linking (链接)为什么需要 Linker (链接器)如果你只写一个main.c就跑程序你不需要感知链接器的存在。但在大型工程中我们需要模块化 (Modularity):把巨大的代码拆分成多个源文件建立通用的函数库比如 C 标准库、或者是你引入的网络库。效率 (Efficiency):如果你改了一个小模块的 Bug不必把整个工程几百万行代码重新编译只需要重新编译这一个文件生成.o然后让链接器把它们重新缝合在一起Relink即可。对象文件 (Object files) 的种类.o(可重定位对象文件):编译器把你的.c/.cpp变成的半成品代码块。里面的地址都还是从 0 开始的假地址。a.out(可执行对象文件):经过链接器整合所有符号函数、变量的地址都被填上了真正的内存偏移地址可以直接运行。.so(共享对象文件):就是常说的动态链接库。它在程序运行时才被载入内存。不仅节省磁盘还能让多个进程共享同一份代码。链接器符号 (Linker Symbols)这部分是引发 C/C 经典报错Multiple Definition或是Undefined Reference的万恶之源。链接器眼里没有复杂的语法只有三种符号全局 (Global):你定义的没加static的函数和全局变量大家都能用。外部 (External):你用extern声明的符号告诉链接器“放心这个东西在别的模块里你最后去那里找”。局部 (Local):加了static的函数和全局变量名字只在本文件可见链接器不会把它暴漏给别人。链接器解谜强弱符号 (Strong and Weak Symbols)如果你在两个文件里定义了同名的全局变量会发生什么规则是函数和初始化的全局变量是“强符号”未初始化的全局变量是“弱符号”。两个强同名符号链接器直接报错(最幸运的情况)一强一弱弱的服从强的。两个弱链接器随便挑一个不报错史诗级灾难Puzzle 3 4如果在文件 A 里写了int x;(弱)在文件 B 里写了double x 3.14;(强)。链接器会把它们指到同一个内存地址而且认为是 8 个字节的 double当 A 里的代码去修改它的int x时它会默默地毁掉 B 里double x内存空间的一半没有任何报错全靠程序员在无数个无眠之夜里去 debug。这就是为什么现在业界强烈要求尽量避免全局变量或者必须使用命名空间Namespace隔离。加载可执行文件 (Loading)当你在终端敲下./a.out回车操作系统会为你创建虚拟内存。最底下存放只读的.text(代码段)然后是.data和.bss(读写数据段)接着是往上生长的 Heap(堆)再往上是操作系统用来映射共享库的内存最顶端往下生长的则是 Stack (栈)。这一切精密得像一座建筑。Interposition (打桩/拦截技术)这是链接器提供的高级黑魔法。允许你在编译时、链接时甚至运行时把某个标准库的函数比如malloc偷偷换成你自己写的包装函数Wrapper。这常常被用来做内存泄漏检测、安全沙箱保护或者是奇葩 Bug 调试比如幻灯片里 Facebook 工程师通过拦截 POSIX 的write函数成功抓到了一个深埋在网络协议栈里的底层越界写 Bug。