高性能编程:序

硬件环境和技术趋势

带宽胜于延迟

带宽是指的给定时间内能完成的总工作量, 延迟是一个事件从开始到结束所经历的时间.
在过去的20~40年里, CPU, 内存, 网络, 硬盘等, 其带宽的改进为300~25000倍, 而延迟的改进仅为6~8倍

处理器性能和存储器性能差距越来越大

在过去的20~40年里, 处理器性能提升(05年后变化较小)带来的单位时间内的存储请求提高了约10000倍, 但是存储器的访问性能改进仅为6~8倍

充分利用并行
在带宽胜于延迟的硬件发展和技术趋势下, 要充分发挥硬件的性能, 并行是其最重要的方法之一.
位级并行
- Processing Unit处理位宽, 寄存器位宽, 数据总线位宽等
- 例如64位机相对32位机增加了一倍的处理位宽, 也就意味着一个CPU周期内能处理的信息量提升了两倍.
指令级并行
- (单指令流多数据流)SIMD指令集(向量处理器) (数据并行)
  - MMX: 可以将64位的寄存器作为2*32或者8*8 进行整数的并行计算, 但其寄存器为借用的FPU的寄存器.
  - SSE: 有1,2,3,4代, 相对MMX主要区别是有了自己专属的128位长的寄存器, 并且支持浮点数的并行计算.
  - AVX: 除了进一步增加位宽(AVX2为256位,AVX-512为512位)外还支持三指令, 但有可能触发降频
- 指令流水线(顺序)
  - 通常一条指令有多个过程, 例如取址, 译码, 执行, 访存, 回写, 如果没有流水线技术则一般一个CPU周期内只能完成一个过程, 即多个CPU周期才能执行完一个指令, 而通过重叠执行多个指令, 理想情况下可以达到每个CPU周期完成一条指令. 但因指令之间的资源冲突问题, 可能导致更多的延迟, 以及长流水线被打断带来的冲洗(清空)操作会带来响应的性能惩罚(bypass/forwarding和分支预测会缓解问题).
- 指令多发射(超标量处理器)
  - 超标量处理器可以通过将多个指令同时分派到处理器上的不同执行单元，从而在一个时钟周期内执行多个指令.
- 同时多线程(SMT 超标量)
  - 在一个CPU核心上同时执行多个线程, 见intel的超线程实现方案.
- 乱序执行
  - 不同的指令其运算周期不同, 特别是指令管道和内存访问的速度差, 乱序执行会对发送的指令请求进行重排序, 以达到在等待的过程中插入更多指令的执行而不是总是空等
任务并行
- 线程, 进程等

局部性原理

在计算机科学的发展过程中贯穿软件和硬件, 几乎无差别覆盖所有对性能和延迟有要求的应用领域, 一次又一次拯救了性能瓶颈危机, 各类优化的基石. 或许很少提及但却一直在使用和遵循的原理, 即局部性原理:
程序常常重复使用他们最近用过的数据和指令, 一条广泛适用的经验规律是: 一个程序90%的执行时间花费在仅10%的代码中; 局部性类型分为三种基本形式:

空间局部性(Spatial locality)
- 地址临近的项目很可能会在短时间内再次访问
- 内存/数据局部性
  - 连续定义的多个局部变量, 函数调用参数, 结构体内的成员数据等
- 顺序局部性
  - 当线性排列和访问相关数据元素时会发生顺序局部性, 例如: 指令的顺序读取, 数组的连续读取
时间局部性(Temporal locality)
- 最近时间内访问过的内容(指令,内存等)会在短时间内被再次访问
- 例如: 调用一个函数时, 传入的参数会很快再次被使用到
分支局部性(Branch locality)
- 几乎所有处理器都采用的条件分支动态预测方案, 其根据分支指令发生转移的历史来进行预测, 准确率90%以上.

举例场景

硬件的发展, CPU性能的提升和存储硬件的性能提升差异
CPU的分支预测, Memory Hierarchy,
数据库的实质
游戏中的同步模型
视频的压缩技术
内存分配器和meta设计

计算机的定量设计原理: Amdahl定律和性能提升的表示方法

在计算机体系结构中，阿姆达尔定律（或阿姆达尔论点[1]）是一个公式，该公式给出了在固定工作负载下任务执行的延迟的理论上的加速，这可以预期其资源得到了改善的系统。它以计算机科学家Gene Amdahl的名字命名，并于1967年在AFIPS春季联合计算机会议上发表。

其定律可以用以下公式描述:
$$S = \frac{1} {(1-p) + \frac{p}{s} } $$

$S$ 延迟是整个任务执行的理论上的加速
$s$ 是任务的一部分得益于改进的系统资源
$p$ 是受益于最初占用改进资源的部分的执行时间比例

该定律的主要思想是: 当我们对系统的某个部分加速时, 其对整体性能的影响取决于该部分的重要性和加速程度.

例如:
系统某部分的初始耗时比例为60%(s=0.6);
我们对该部分做了重大改进并获得了巨大的性能提升, 获得加速比为3(s=3);
但是获得的系统加速比最终为1.67(倍);

notes:

性能提升最好的表示方法是用比例的形式$T_{old}/T_{new}$, 如果有所改进, 则比值大于1. 一般用后缀”X”表示比例, 例如1.67X, 读作’1.67倍’ ;
该表示相对传统百分比方法而言更为清晰:

通常百分比适用于变化小的情况, 并且存在以下模糊的定义部分:
例如这种变化是用$100(T_{old}-T_{new})/T_{new}$还是$100(T_{old}-T_{new})/T_{old}$ ?
以及与简单的说性能提升为2.2倍, 百分比的120%的性能提升更难理解.

编写高效程序和性能优化

首先, 写程序最主要的目标是使它在所有可能的情况下都能正确工作, 一个运行的很快但是会给出错误结果的程序没有任何用处.

但是另外一方面, 很多情景下让程序跑得很快(包括响应速度甚至性能功耗比)也是一个重要的考虑因素, 这在游戏中的gameplay部分体现的更为淋漓尽致.

编写高效程序需要做到以下几点(局部性原理贯穿所有层级):

高级设计: 选择合适的算法和数据结构
编码原则: 编写编译器能识别并优化成高效可执行代码的源代码;(隐含:需要理解编译器优化的的原理和其局限性)
低级优化: 充分利用硬件的功能并充分发挥硬件的性能.

程序优化的步骤:

确认并分析性能瓶颈
理解工作的目标, 并重新审视工作代码是否遵循’编写高效程序’的几个基本要点.
选择合适的算法和数据结构, 必要时根据时间和人力成本是否需要重构设计.
消除不必要的工作, 包括不必要的设计和流程, 不必要的代码和调用
对热点代码进行针对硬件特性的低级优化, 减少对硬件不友好的代码, 尽可能的发挥硬件的性能.

代码优化基本原则:优化不应带来可见的副作用改变

如非必要, 尽可能进行局部的替换和改善, 减少优化带来的修改规模.
如非必要, 尽可能的使用简洁的代码, 避免优化带来的可读性损失
如非必要, 尽可能保持代码的通用性, 避免过度牺牲可扩展性和灵活性.