1. 程序员的“时-空”取舍
众所周知，开发一个在生产环境中使用的软件，必须满足三个目标，第一个目标是功能目标，这是最基本的目标，否则就是没有满足用户的需求，算是开发失败，比如开发一个邮件系统，功能就是能收、发邮件；第二个目标是性能目标，就是满足合同要求的并发用户数并且不损害用户体验，比如一千人能同时使用邮件系统，并且用户并不觉得卡顿；第三个目标是产能目标，主要表现于可靠性和安全性，比如能过滤垃圾邮件，能防止病毒通过邮件扩散，邮件不被泄露或丢失等等。
经常崩溃的程序属于没有满足第一个目标，正常的功能都没有保证，对吧？我在华为工作期间，负责过一家深圳公司开发的合同管理系统的运维，这个应用软件本来就不大业务逻辑也不复杂，可是隔三岔五出幺蛾子，每次出问题就得把乙方经理叫过来，这样差不多折腾了大半年，依然问题多多，最后华为干脆弃之不用了。后来华为明确规定不再使用国内公司开发的软件，原因倒不是仅仅因为这个合同系统，还有其他众多的国产软件，问题真他妈的多！再比如我们学校使用的教学广播软件，主要功能就是把教师机的屏幕广播到学生的电脑上，运行起来会消耗大量的CPU和内存资源，而且时不时出问题。
今天我重点谈谈如何在软件代码层面实现第二个目标，即如何编写高效率的计算机程序代码——执行的代码量尽量最少。所谓的高效率就是完成相同的任务，消耗CPU的时间最少，消耗的内存最少。CPU执行的时间体现在时间维度，而消耗的内存数量体现在空间维度，此乃程序员经常遇到的“时-空”取舍问题——时间和空间往往不能同时兼顾最佳，有时为了节约内存不得不增加代码，而在另外的场合可能为了追求执行速度又不得不消耗更多的内存。好在现在的电脑内存都比较大，程序员更多地在追求代码执行的速度。比如交换两个变量的值，下图是两种实现代码，左边的代码节约了内存，但是会消耗更多的cpu时间，右边的代码增加了一个变量（消耗更多的内存），但是降低了CPU的时间。
由于篇幅所限，本文侧重于探讨如何提高代码的执行速度方面。注意：我这里指的代码不是诸如C语言的源代码，而是能在CPU上执行的二进制代码，也就是源程序编译之后的代码，基本上等同于汇编语言代码。
2. 从一个例子开始
我们先看一个例子：计算2000000000的阶乘，下图是最常见的实现代码，运行时间需要3.722秒。
我们改改代码，见下图，执行时间只要1.333秒，节省了近三分之二的时间！
显然这是采用了循环展开手法。也许有同学问，为什么不改成下面的代码呢？看到了吧？耗时更长了。
为了理解上面第二份代码为何能大幅度提高执行速度，我们还得从计算机的底层讲起。
3. 数据通路
计算机运行程序的大致过程是：命令行输入程序名并回车，或者指到某个程序后双击鼠标，这时操作系统会把程序里的二进制代码指令读到内存中，然后cpu从内存“一条一条”取指令并执行指令，整条数据通路见下图。
硬盘通过SATA线缆接到电脑主板上，SATA线缆是串行线，也就是说传递数据时是一个比特一个比特位传的。
由于内存的速度要远远高于磁盘的速度，所以磁盘引入了用芯片实现的缓存，从磁盘读数据到内存时，先慢慢读到磁盘缓存中，然后一次性快速读到内存，相反当向磁盘写数据时，先一次性快速写到磁盘缓存，然后让磁盘自个儿慢慢写到磁盘中。一旦断电，磁盘缓存中的数据就会丢失，如果缓存太大，那么来不及写到磁盘的数据就丢了，“明明我保存了word文档啊，怎么来电之后电脑上没有文件呢？可惜了废了我半天时间编辑的文件就没了！”想必很多人遇到类似的问题。所以磁盘的缓存不能太大，一般不会超过256MB，否则就要给磁盘添加电池了——断电之后由电池供电继续落盘缓存中的数据。比如西数2TB硬盘的参数如下：
现代操作系统更智能化，当内存足够大时，还会拿出一部分内存来做磁盘的缓存，加上磁盘上的缓存就形成了双缓存机制，从而进一步优化了“磁盘-内存”的数据通路。看下图，电脑配备了8GB内存只用了800MB，所以就拿出了大约500MB做磁盘的缓存。
以块为单位访问磁盘，一块一般是4KB，即8个扇区，也就是说内存与磁盘之间每次传递的数据至少4KB，当然可以更多，但必须是4KB的整数倍。
CPU通过主板上的总线链接到内存，总线又分为数据总线和地址总线两种，数据总线是双向传递数据的，而地址总线是从CPU到内存单向传递内存地址的。总线就是印刷电路板上的一排线（见下图所示），对于64位的CPU来说，数据总线一共有64根，地址总线也有64根。CPU有一个参数叫字长，是指参与一次计算的数据的二进制位数，比如现在绝大多数的CPU字长都是64位，表示参与一次计算的数据是用64位二进制表示的，比如对于一次加法计算，和、加数与被加数都是用64位二进制数表示的。
大家仔细看看主板上的总线，存在一些故意拐弯抹角的线路，这称为蛇形走线，目的是保证同一类型的总线上的线路长度一样，正如操场上的跑到，弯道里面的要更短，所以为了增加其长度不得不采取蛇形走线。比如CPU与内存之间的64根数据总线，一旦要在主板上拐弯，靠里的线路就要蛇形走线，只有64根线路长度一样才能确保信号同时到达对方。
你可以把内存想象成一条很高的梯子，内存单元就像梯子上的一格，每个内存单元有一个唯一的编号（从0开始），这个编号称为内存地址，一个内存单元只能储存一个字节的数据，也就是8位二进制数。CPU读内存的步骤是：通过地址总线给内存发送地址，然后内存通过数据总线返回地址所对应的内存单元中的数据。CPU写内存步骤差不多，也是先发地址，然后发数据。比如下图中的66号内存单元存储了二进制数10011101。
CPU访问内存的最小单位是一个字节（也就是一个内存单元），但可以一次访问多个字节，比如在C语言中定义的一个整型变量，一般是32位二进制数，需占用四个连续的内存单元，所以给整型变量赋值，就是要往连续的四个内存单元写数据。
以上是从CPU的核的角度看的，实际上CPU与内存之间传递数据的单位是缓存行。缓存行又是什么鬼？这还得从CPU内部的缓存说起。
CPU的速度要远远高于内存的速度，即CPU执行一条指令的时间要远远小于从内存读取一条指令的时间。前面讲过，CPU执行的每一条指令都要从内存获取。打个夸张一点的比喻：CPU执行一条指令只需一秒钟，但是从内存读一条指令需要一个小时，这样CPU相当于99.99%的时间都在等待。为了解决这个问题，就在CPU内部引入了缓存机制，而且是三个层级的缓存，下图是英特尔4核CPU的内部结构。
每个物理核都能独立执行程序指令，比如一个4核的CPU，能同时并行运行四个程序。如果开启了超线程，那么一个物理核还能划分为两个逻辑核，逻辑核上可以“并行”执行线程——微观层面还是串行的，只不过多了几个寄存器（如pc寄存器），所以在切换上下文（A线程的时间片用完，下一个时间片轮到B线程执行）时需要保护的寄存器数量更少了，因此切换速度更快，只要增加几个寄存器就能带来30%的效力提升，所以现代CPU都采用了逻辑核机制。下图是我的电脑上看到的CPU参数。
每个物理核中都有几十个64位的寄存器，这些寄存器存取速度极快，常常用来临时储存计算的中间结果。每个物理核拥有独立的一级缓存和二级缓存，全部物理核共享三级缓存。一级缓存分为指令缓存和数据缓存，也就是一级缓存中，指令和数据是分开的。
一级缓存离核最近，速度最快，成本也最高，二级缓存次之，三级缓存离核最远，速度最慢，成本也最低，所以容量依次增大，请看下图：
说明四个一级缓存共256KB，所以每个一级缓存容量64KB，因而指令缓存和数据缓存各占32KB。每个核心独占的二级缓存容量是256KB（1MB的四分之一）。
缓存中的一行为64个字节（Linux下/sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size文件登记了缓存行的大小），所以根据上图中的缓存大小，可以算出每个核心的一级缓存有1024行（指令和数据缓存各有512行），每个核心的二级缓存有4096行，而三级缓存有98304行了。所以你可以把缓存想象成一张多行64列的表格。前面提到过CPU与内存之间传递数据的单位是缓存行，也就是每次64个字节，等于说每次要读取内存中连续的64个内存单元来填满缓存中的一行，这64个内存单元的首地址必须对齐64——能整除64，即对齐64的二进制地址的格式为（低6位二进制数为0）：
因此内存地址0、64、128、192、256都可作为缓存行的首地址，参考图前面的内存图作进一步理解。
现在假设一个逻辑核要读取内存中66号单元内的数据，具体过程是这样的（不妨假设刚开始缓存都是空的）：
(1). cpu通过地址总线向内存发送0000000000000000000000000000000000000000000000000000000001000010（对应十进制数66）。
(2). 内存计算出66号单元落在首地址为64的缓存行内，于是把64号至127号一共64个内存单元的数据通过数据总线发给CPU。
(3). CPU接到数据后依次保存在三级缓存、二级缓存和一级缓存内，刚好占用各级缓存中的一行。
(4). CPU进行计算。
当CPU执行下一条指令，需要读取70号内存单元时，并行搜索一级、二级和三级缓存，显然70号内存单元的数据已经保存在一级缓存中，因此一级缓存命中，同时终止二级和三级缓存的搜索，也不再访问内存。只有当访问的数据不在缓存中时才去访问内存，这称为不命中缓存。
程序的局部性原理是CPU引入缓存机制的理论基础，局部性原理包括时间局部性和空间局部性，时间局部性是指刚刚被执行的指令很可能马上又被执行，空间局部性是指刚被访问的内存单元的相邻内存单元很可能马上被访问。在程序代码上，例如循环语句体现了时间局部性，对数组的处理体现了空间局部性。一个程序总执行时间的80%是在重复执行20%的语句。既然是重复执行语句和处理的数据聚集在一块，那么缓存这些语句和数据就会大幅度提高电脑的性能，因为直接访问缓存的速度要远远大于访问内存的速度。
好了，总结一下，数据通路上的寄存器、一级缓存、二级缓存、三级缓存、内存、硬盘、网盘，速度依次降低，容量依次增大，也就是说寄存器速度最快但容量最小，而网盘速度最慢但容量最大。
4. CPU流水线
CPU执行一条指令需要五个阶段（一些小众CPU可能阶段数不同），这五个阶段分别是取指、译码、执行、取数、回写。取指就是从内存读取指令，译码就是把指令翻译成微码，执行就是执行译出来的微码，取数就是从内存读取数据，回写就是把结果写回内存。一条指令对应若干条微码，这些微码固化在CPU内部，能译成微码的指令就是合法指令，不能译成微码的指令称为非法指令，CPU一旦遇到非法指令电脑就会死机，指令（在底层也是用二进制表示的）在数据通路上传递时可能会发生一些二进制位跳变，尤其是内存不稳定时，本来一条合法的指令，只要发生一个二进制位跳变，很大概率就变成非法指令了，当然也存在另一种极小的可能性，那就是发生几个二进制跳变，结果变成了另一条合法指令。反回过来讲，一款CPU的微码决定了它所支持的指令集，当下流行的指令集都有一个名字，比如英特尔和AMD的CPU支持x86指令集，ARM CPU支持的指令集最新版是armv8，龙芯CPU的指令集是MIPS，显然能在英特尔CPU上运行的程序是不能在ARM和龙芯CPU上运行的，反过来也成立。指令集被各个CPU厂家申请了专利，比如我想开发一款新的CPU，如果要支持x86指令集就必须向英特尔购买专利，如果想支持armv8指令集，那必须向ARM公司购买专利，高昂的专利费使得我开发一款新的CPU就没有任何价值可言了。也许你会说，干脆自己搞一套新的指令集，那你搞出来的CPU不能运行地球上现存的任何程序了，因为这些程序中的指令对你的CPU来说都是非法的。
执行指令的五个阶段分别由不同的电路部件完成的，因此可想象成工厂里的一条流水线，见下图。
即取指电路部件获取到指令后发给译码电路部件，译码电路部件翻译成微码后发给执行电路部件，执行电路部件完工后发给取数电路部件，取数电路部件发给回写电路部件，最后回写电路部件把结果写回内存，到此一条指令执行完毕。接下来取指电路部件再读取下一条指令，以后的步骤以此类推。各个电路部件完成一个动作的时间都是一个时钟周期，一个时钟周期到底多长，可由CPU的主频算出来，比如主频是3.6GHz，1除以3.6G约等于0.259纳秒（即0.000000000259秒），显然CPU的主频越高，执行指令的速度就越快。
上面描述的流水是串行的，即当一条指令执行完毕之后才取下一条指令，参考下图。
显然在任何一个时钟周期内，只有一个电路部件在工作，其他四个电路部件空闲。我们自然会想到尽量让各个部件忙碌，于是就有了流水线机制，参见下图。
即一旦某个电路部件把任务交给下一个电路部件后就可以接受前一个电路部件的任务，比如取指电路部件获取到指令并发给译码电路部件后，可立即获取下一条指令。比如上图中，到了第5个时钟周期后，每个电路部件都在忙碌。
但是存在一些例外会影响流水线的顺畅传动，一种情况是相邻两条指令存在数据依赖，比如上图中的指令2计算的数据来自指令1的结果，所以指令2的MEM必须推后到下一个时钟周期，因此导致后续指令都得延迟一个时钟周期，参见下图。
从图可以看出，在第5个时钟周期内，执行电路部件一直被指令2占用，所以指令3的译码电路就不能把指令发给执行电路，这样指令3就占用了译码电路，导致指令4不得不占用取指电路，因为它不能发送给译码电路。这种阻塞流水线的现象称为数据冲突，比如下面的代码就会导致数据冲突。
x = 3.14;
y = x * 81;由于流水线上同时在处理五条指令，这在遇到分支语句时就很麻烦，比如上图中，假设指令1是分支判断指令，判断的结果接下来可能要执行指令2，也可能要执行指令3，也就是说指令2和指令3不会都要执行，这种现象称为控制冲突。现代CPU倾向于采用分支预测来处理控制冲突，也有CPU采取直接停止流水线直到判断判断结果明确之后再重启流水线。比如下面的代码，分支预测假设条件成立，让x=0这条指令进入流水线。当然分支预测涉及较复杂的算法，目的是尽量提高预测的成功率。如果预测失败流水线会面临较严重的性能惩罚。
if (i < 60) {
x = 0;
} else {
x = 1;
}5. 机器指令
机器指令也称为CPU指令或者二进制指令，能直接进入CPU流水线。而源程序代码是不能被CPU执行的，需要编译成机器指令后才能被CPU执行。一条源代码语句往往对应多条机器指令，但是汇编语言的语句基本上根机器指令一一对应。下图是部分C语言语句对应的机器指令。
可见语句j=i>10?3:7等价于语句if(i>10){j=3;}else{j=7;}，但是源代码可读性更好一些。
6. 计算机源程序
c语言源程序大致包含三种结构：顺序结构、分支结构和循环结构，顺序结构就是从上到下执行的一系列语句，分支结构使用if、switch或者?:选择执行的语句，而循环语句就是重复执行某些语句，常用for、while、do…until语句实现。其实不管是分支还是循环结构，内部还是包含顺序结构。只有顺序结构中的语句才是有意义的，而分支和循环引入的控制语句是无“意义”的，所以执行路径上的指令越少越好，运行一次程序执行到的全部指令称为执行路径。
对于顺序结构中的语句，要避免数据冲突，因为它会导致CPU流水线延迟，数据依赖的语句尽量分开（中间存在四五条语句）。对于分支结构，要根据业务数据，尽量把最容易满足条件的分支放在最前面，比如把学生百分制分数转换为等级制分数，一般得分在65至85区间的学生最多，所以要分数处于65-85之间的判断分支放在最前面，见下图。
这样做有两个好处，总执行的指令数大大减少，其次是分支预测成功率大大提高。
对于循环结构，光循环控制语句就占了五条（循环体内三条），如果循环体太小，那么无“意义”的语句占比就过高，从而大大增加了执行路径的总长度。就拿本文开头举的计算阶乘的例子来说，见下图，我们算算一共执行的指令数：一次循环执行8条指令，一共循环20亿次，总共要执行160亿条指令。
从这些指令可以看出：三条循环控制指令占比近40%，一次循环访问内存5次。还有就是存在多次数据冲突从而干扰了cpu流水线的正常流动。
然后做循环展开成如下图所示的代码，要循环5亿次，每次循环执行26条指令，总执行的指令数为130亿条。
这样只降低了循环控制语句的占比，但是数据冲突和频繁访问内存的毛病依然存在。所以还能进一步改进：对于循环体中使用频率高的变量，建议采用寄存器，比如改成如下代码后，执行时间只需0.564秒，因为不再需要访问内存了。
循环展开的本质是降低循环控制指令的占比，但是又不能过度展开，因为循环体过大就违背了局部性原理，可能不能全部储存在CPU的一级缓存中。循环体的语句最好控制在64个字节以内，这样就可以完全储存在缓存的一行内。
对于数据冲突问题，在源代码层面，尽量不要引用刚刚修改过值的变量。另外在发布最终版本时，建议编译带上-O3参数做最大程度的优化。
7. 内存对齐
二维数组先行后列被存储在内存中，即先存储第一行，然后第二行，……。所以处理二维数组时也要按行处理，这样就能充分体现数据局部性，进而高效使用CPU缓存。另外由于CPU读取内存是64地址对齐的缓存行，所以定义数组时最好也指定64地址对齐，比如定义二维数组的语句：int __attribute__((aligned(64))) a[32][100];
8. 进程和线程
一个进程包含至少一个线程，进程是申请资源的主体，同一个进程内的线程共享进程的资源，其中内存是主要的资源。线程是CPU调度的基本单位，因此同一个进程内的线程允许调度到不同的CPU核上执行——并发执行。编写多线程代码时要特别小心，因为它们共享全部的数据，即内存。所以要让各自要写的变量位于不同的缓存行里，这样缓存行就可以缓存在各个线程所在的 CPU核的一级缓存中。请看下面两个线程的例子。
运行时间需要5秒，我们交换第5、6条语句的位置，即把data[64]的定义放在a和b的中间，结果发现运行时间只有1.6秒。我们只是交换了两个变量的定义位置，为何运行效率提高了那么多？！那是因为交换后，a、b变量刚好位于不同的缓存行内，这两个缓存行从而可缓存在线程所在的核心的一级缓存中。
9. 结语
程序开发人员脑袋里一定要对CPU、内存有一个清晰的映像，记住总体的数据通路很重要。然后记住一些基本的常识，如顺序结构要避免数据冲突导致cpu流水线卡顿，分支结构要根据业务数据情况，把条件为真的概率最高的分支放在最前面，循环结构适当进行循环扩展以降低控制语句的占比，从而降低总的执行路径长度。
对于多维数组的处理，要先行后列。至于多线程编程，要避免共同修改相同的变量以及各自修改的变量不要挨在一起，尽量保证它们位于不同的缓存行内。