性能调优那些事儿

问题

性能优化是软件开发中最重要的活动，也是软件工程中的深水区，可以说也是衡量一个程序员能力高低的标准。在大厂的面试中性能调优的问题也是最常见的，比如：为什么Nginx的单线程处理网络连接模型吞吐量与效率会如此之高？为什么Kafka的吞吐量会比其他的消息队列高？redisTPS/QPS比关系型数据库高出几个数量级？

要想回答这些问题，需要做很多的实践与探索，而且要面对杂乱无章的、真真假假的网络文章，需要耗费大量的时间，这也就是程序员常说的“我变强了，也TM秃了”的感慨原因。

虽然性能调优的方法与例子非常多，几乎而且每年都会涌现出新的技术、框架，很多知识因为各种原因进行了很高层次的包装，不容易看到其本质原理，很多事实、证据需要翻源码才能获得，但是因为知识点分散，过程困难而且枯燥。那么有没有一些通用的优化原则，或者基线呢？我想应该是有的，如果你想了解这方面的知识，这篇文章就属于你。

起源

著名的计算机科学家的Don Knuth认为计算机程序调优只有两种方式：

1、减少执行算法的指令数；

2、减少单条指令运行的时间。

这是一个高度抽象的近乎公理一般的结论，看似平淡而无趣，但是却推测出计算机程序的基本特点与边界，而我想面对一件具体的问题，定义其问题的边界是十分重要的，它能指导我们做事的方式与方法，避免一些错误与不必要的努力。那么计算机程序运行的边界在哪？我想有这些：

• 计算机程序是由指令组成的，在计算机能完成的任何工作都能对应到一条或者若干条指令；
• 每条指令都会消耗时间，而指令不同执行所需要的时间也会长或者短，通过提高指令执行运行速度可以提高程序运行效率；
• 同时，完成一个任务（算法）所消耗的指令数目也可以多也可以少，通过优化完成指令的数目可以加快程序的运行。

好了，我们到这里已经讲现在我们能够用的调优武器都介绍完了，有没有感觉到呢？计算机暴露给程序员的调优目标就是减少程序指令数目与“减少”程序指令的执行时间。

当然，你可能要说，我们在实际项目中哪有时间或者条件去跟踪、分析每条指令的执行？有那闲工夫，我们项目早就做完了；再说了，我们在项目中对于性能调优都会讨论缓存方案啊、多线程并行啊；说到IO速度慢我们可以用redis、kafka啊这些工具来应对，那么这些常用的手段是否跟前面介绍的两个基本原则有关系呢？

我想，我们不仅目前所有的工具优化实例都会对应到以上两个原则上；而且可以预测，只要计算机结构不发生本质的变化（比如量子计算机的普及）那么所有程序调优的活动都能对应到这两个基本的定理上来，这给我们分析程序性能划定了界限、指明了道路。

下面我们来详细分析下这两个原则的实际落地实例，我将整个程序调优活动按照上面两个定理化成两大类——加快指令执行速度与减少执行代码的数量，先看看加快指令执行速度的例子。

加快指令执行速度

你可能感到奇怪，我们在项目中使用的绝大多数优化手段，如缓存与并发都可以归类到这种类型的优化。程序员一般来说不是硬件工程师，我们一般不会去优化某条硬件指令的执行速度，但是我们可以通过优化组合程序指令执行顺序并利用硬件工程师提供的“便利条件”变向的达到加快指令运行速度的目的。

举个例子：我们程序的目标是将一个20斤的西瓜吃完，一个人显然一天是吃不完的，可能需要吃两天，为了好计算我们假设一个人吃完要20天；但是如果四个人同时吃呢？5天就吃完了，西瓜的总量没有变化，还是20斤，现在执行的速度从20天提升到5天，提高了4倍；那么，对于执行的速度就从1天吃1斤提升到了0.25天吃1斤，相当于单条指令的执行速度提高了4倍——这就是并行计算能加快执行指令速度的原理。

再举个例子：我们的程序是做菜，做菜这个程序分为2个大的阶段，首先，我们必须出门买菜；然后在厨房将买回来的菜做成熟菜。考虑两种执行策略：

1. 首先拿着菜谱进入厨房开始炒菜；按照菜谱的顺序开始执行；当炒菜的时候发现缺失的食材，中断炒菜的过程，出门去菜市场买菜，将缺失的食材买回来后继续炒制；然后循环这个过程直到最后完成整个菜的炒制过程；
2. 首先做规划，看看菜谱收集需要的食材清单；然后根据食材的清单出门买菜；菜买回来后进入厨房按照菜谱的顺序去执行。

我们可以对比下两种执行策略，可以根据我们的生活经验很快得出一个结论：

1、两种策略都能完成任务，而且完成任务所执行的步骤——“菜谱”是相同的，也就是完成的指令数目是一样多的；

2、显然第二种策略比第一种要优秀。因为它执行的时间比第一种要快很多，因为出去买菜是一个费时的指令，如果每准备一个食材就要出门买菜，那么整个执行过程会被拖长；然而，一个人出去买菜的“通信带宽”往往会比较大，比如，你出去一次可以同时携带大于1个的食材，甚至在带宽不足的时候还能采用骑车或者开车的方式增加带宽，所以第一种策略无形中浪费了很多“计算资源”所以效率更低。这个例子很清晰的说明了计算机中“缓存”这个重要的概念。我们通过分析，执行的任务总量没变，但是通过合理利用计算资源（硬件工程师提供的“便利条件”）能够大幅的提升计算速度。

并行计算与缓存是软件工程中的常用方法论，下面我举几个例子来说明他们的重要性。

程序在底层的并行化——CPU的流水线模型

并行计算为什么能够“看上去”提高单条指令的速度，我想其本质原因就是CPU的计算速度与数据传递过程中的速度严重不匹配，前者往往比后者快5-7个数量级——CPU的计算速度是内存频率的5个数量级；所以计算资源被严重浪费了，换句话说我们程序员的任务是更好的利用CPU的计算资源，不能让它们歇着。那我们先看看硬件工程师是怎么提高CPU的执行效率的，这些知识能够让我们在写程序的时候有更多的黑魔法可以用。一种一个典型的优化手段就是让指令在CPU中并行的执行——CPU流水线模型。

这里有一个前提，我们所针对的环境是单CPU单核处理器，如果是我们常见的多核那么不在这个范围内讨论。

什么是流水线模型

流水线模型来源于生活，还是以上面炒菜的例子，我们在厨房里面一般都有处理食材的单元，还有炒菜的单元；我们在处理食材的时候，炒锅是空闲的，而在炒菜的时候砧板是空闲的；那么要提高“厨房”的吞吐量，我们就可以安排两个人一起协同工作，当前一个人处理完食材交给厨师烹制的时候，切菜工可以接着处理下一个食材，而不是等着厨师炒完菜再“load”下一个食材——这就是流水线模式，我们的单核CPU就是这么工作的。

CPU的多级流水线

我们拿两条高级语言编写的累加代码说明CPU多级流水线如何工作：

i=0; //将0赋值给变量i

i=i+1;//将i累加1

这两条指令在多级流水线（超流水线）CPU中是并行执行的，为什么呢？我们来详细阐述下代码如何在CPU上执行的。有两个前置的知识点：

1. 不管是什么语言，最后只能由CPU来执行；我没见过人写的代码可以脱离计算机来运行的；
2. CPU运行代数计算的部件（布尔代数是核心），这就将程序分成了数据部分（变量）与算法（代码）部分，这也是program=data structure+algorithm的原因；任何程序都能表示成f(x) = ax+b的多项式形式，带入不同的数据会得到唯一的不同的运算结果，这也是为什么我们写的方法被叫成函数的原因；
3. CPU与内存是绑定在一起的，不可分开；缺少其中一方，程序就无法执行，这是冯诺依曼计算构架的基础；程序存在内存中，CPU通过取址指令来加载指令到寄存器，然后逻辑运算单元通过读写寄存器的数据完成一次计算；
4. 一个机器码，比如累加操作，在CPU内部会被分解成若干条”微指令”来执行，这样可以提高CPU的吞吐量。（注：你是不是遇到过很多跟微相关的概念：RICS、微内核、微服务，将复杂的过程分解成相关的部分有利于资源的利用与控制，这是所有工程都适用的治理手段，这是另一个话题了以后介绍）。

可以看到对于一条指令至少可以分解成两个阶段，比如：i=0这条代码，可以分解成：

1. 取指令：Cpu发送load指令，从内存中获取程序机器码；
2. 译码：通过指令译码单元将机器码翻译成控制电路信号；
3. 执行：执行赋值指令；
4. 访存：获取i对应的内存地址；
5. 写回：将结果0写回到i对应的内存地址存储单元。

这些阶段对于“i=0”这行代码来说只能串行执行，但是细心的你可能会发现，当cpu执行完取指令操作，就空闲了；译码单元执行完译码操作也空闲了，而此时“i=0”还没跑完，不能执行下一条指令，只能等着，这就造成了CPU资源浪费，一条赋值操作要等5个“周期”才能执行下一条“i=i+1”代码。为了提高吞吐量，CPU流水线模式应运而生。

CPU5级流水线

这是一个典型的5级流水线，可以看到，指令2不需要等到指令1完成计算结果写回操作就能开始取指令、开始执行；同时，第三条指令也不需要等到第二条指令执行完就能开始执行；这样一个5级流水线可以同时并行处理5条代码；CPU的吞吐量从5个“时钟周期”完成1条指令，提高到1个“时钟周期”完成1条指令，吞吐量加大了5倍之多，其宏观效应就是单条指令的耗时从5个单位时间减小到1个单位时间，加快了运行速度。

那么怎么利用流水线技术来写出高效的程序呢？举个简单的例子：

int sum,sum1,sum2,sum3,sum4;
for(i = 0;i<100;i+=4){
    sum0+=a[i];
    sum1+=a[i+1];
    sum2+=a[i+2];
    sum3+=a[i+3];
}
sum = sum1+sum2+sum3+sum4;

当你在看一些高性能组件的源代码时你可能会看到这种代码，为什么循环的步长会从1变成到4？那是因为，目标机器的CPU流水线中有“超标量”的功能用于解决流水线的指令冒险问题，而这个代码运行的CPU有4个超标量单元，可以同时执行4个整形加法运算，所以for循环中的四个加法累加操作是同时执行的，可以有效的加快循环执行速度。

关于如何利用CPU内的黑魔法写出高效的程序本身有太多的话题，限于篇幅这里不展开，但是可以看出CPU里面的世界远比我们想象得复杂，同时，这种微观世界的优化原则也跟高级的企业级优化原则有很多共同的特点，这也使得我们可以利用相同的方式在各个层次上写出高效的程序提供了理论基础。

注：世间的任何好都会带来弊端，CPU流水线也不例外，如指令冲突，数据冲突，控制冲突等等会造成CPU计算错误或者延迟；但是流水线带来的收益实在太过于明显，所以人们又不断开发出“超标量”、“分支预测”、“L1cache指令与数据分开存储的哈佛结构”等等技术来弥补，使得X86这种CPU的控制电路变得越来越复杂，功耗也越来越高；使得在手机上的市场出现明显短板，从而拖累了很多公司在移动设备上的失败（如微软）。

程序底层缓存优化技术——CPU的缓存行技术

现在我们来看看缓存优化技术，也就是前文说的“买菜部分”的优化，通过那个例子我们可以总结出缓存类优化技术的共同特点：

1. 缓存技术并不能减少指令代码的数量，也就是说缓存技术并不能减少“读取”操作本身的次数；更进一步说是优化前的程序的执行逻辑跟优化后的执行逻辑不会产生变化；
2. 缓存技术针对的是读场景，往往是高速处理部件读取低速处理部件数据时使用；适用于读多写少的场景；
3. 缓存虽然能够加快速度，但是对于系统来说会增加额外逻辑的复杂度；有些场景要慎用。

我们依然延续上节对CPU运行指令的解构过程，看看CPU如何使用缓存技术来加快程序的执行，以及如何利用缓存技术写出高效的代码。

CPU流水线与冯诺依曼瓶颈

我们可以回到最开始——CPU的流水线技术；最开始流水线技术其实有一个大的bug，或者说因为解决了这个问题CPU才会有流水线技术的诞生——冯诺依曼瓶颈。

冯诺依曼瓶颈其实通俗点讲就是CPU与内存之间的访问速度Gap，为什么会有这个gap呢？根本原因是冯诺依曼设计的计算机是指令存储执行构架的计算机，它将程序的执行与存储做了分离，执行方只提供指令的列表与执行单元，而程序员按照执行单元提供的有限条指令组合出不同的程序来存储到内存中，CPU通过读取内存中的代码执行，然后将执行结果返回到内存。这是一个划时代的创新，使得现代程序员不用为了实现特定的功能去思考如何修改CPU的指令集，也极大的简化了编程这个活动，推动了IT产业的进程。但是也带来了一个问题，CPU不存储指令与数据，那么就要访问内存，由于工艺原因，CPU与内存是有很大的访问延迟的；打个比方，如果把人类世界的1秒代表CPU执行一条指令的时间，那么访问一次内存就相当于过了5分多钟，300倍的gap，这是什么概念的，如果不做缓存，我们运行打开微信这样的App需要半个小时以上的时间，显然是不合理的。

我们再看看前面的5级流水线CPU，其中两条微指令“取指”与“访存”的语义是从内存中load数据，那么因为冯诺依曼瓶颈的存在，这两个微指令的延迟将是其他三个指令的100多倍；而流水线的吞吐量是有短板效应的，它只跟执行时间最长的步骤有关，如果要得到一个高效的流水线就必须将任务的步骤进行均分，避免短板的出现；所以如果不解决冯诺依曼瓶颈就无法实现CPU的流水线技术。

CPU的缓存行技术

为了解决冯诺依曼瓶颈，CPU硬件工程师，在不改变原有执行逻辑的基础之上增加了3层缓存层，分别是L1、L2与L3层，如下图：

CPU缓存

他们的容量跟访问速度成反比，但是跟CPU基本还在一个数量级上，比如典型的多核Intel X86 CPU，L1是32K-64K，L2 256K-512K，L3 4M-8M。

增加了3层cache后，CPU的内存访问模型发生了变化：

1. L1、L2与L3都被封装到CPU中，外界不可见；
2. 每个计算核心core有自己的L1 L2Cache，而所有核心共享一个L3 Cache；
3. CPU不会直接访问内存了，它只会从L1中加载数据与代码；
4. 形成了访问代理链，L1层负责代理L2，L2负责代理L3，L3又称环形电路负责代理整个内存；上层屏蔽下层；
5. L1、L2与L3是按照缓存行cacheline来管理的，而不是一个个的字节，一个cacheline通常有64个字节。

其中第5点是值得特别关心的，因为引入了一个新的概念——cacheline。这是个什么东西呢？还记得上文中买菜的例子，在生活中我们出去买菜肯定不是一次只买一个菜回来，而是将所有需要的菜一次都买回来，而出去一次买多少菜呢？CPU规定一次64个字节。

缓存行优化的原理

那么你可能会问，缓存行为什么能加快CPU读取数据的速度呢？而缓存行又有什么特点呢？

1. 减少了CPU直接访问内存的次数，提高了取址指令的执行速度（弥补了取址指令的总体执行速度跟执行单元执行速度的gap）；一次读取64个字节，对于一般的程序可能一次就把所有的数据与代码都加载到了L1中，而CPU访问L1的速度基本没损失；所以起到了提速的作用；
2. 程序代码与数据具有空间局部性；换句话说就是，程序编译完成，加载到OS后，其代码段与数据段往往是连续存储的，所以可以通过一次访问全部加载，这就是空间的局部性；
3. 程序代码与数据具有时间局部性：一段代码还有时间局部性，比如循环代码，一次加载到内存后长期都会命中L1缓存，所以在程序中写短小的循环代码能有效的提高执行性能；
4. 当然缓存行也有些弊端，它有着复杂的更新策略，比如，当一个缓存行中任何一个字节被修改，整个缓存行都会被重新加载，而且并同步到其他的核心中，造成一定的性能损失。这导致在多核构架的CPU中需要额外的更新协议（MESI）来同步各个核心的共享缓存行，这是一个很大的话题，尤其对于多线程的高并发程序来说。

一个利用缓存行优化的例子

因为代码在加载到OS中以后具有时间与空间的局部性，所以如果有效的利用这些局部性与缓存行机制就能写出性能较高的程序来。比如，我们通常会在程序中使用常量，而常量的目的是在多个线程之间共享状态，协调线程执行，那么，我们就需要这些数据能够常驻L1-L3级缓存以减小内存与CPU之间的IO开销。我在一个优秀的消息队列组件——Disruptor中找到这样一个实例：

class LhsPadding
{
    protected long p1, p2, p3, p4, p5, p6, p7;
}

class Value extends LhsPadding
{
    protected volatile long value;
}

class RhsPadding extends Value
{
    protected long p9, p10, p11, p12, p13, p14, p15;
}

/**
 * <p>Concurrent sequence class used for tracking the progress of
 * the ring buffer and event processors.  Support a number
 * of concurrent operations including CAS and order writes.
 *
 * <p>Also attempts to be more efficient with regards to false
 * sharing by adding padding around the volatile field.
 */
public class Sequence extends RhsPadding
{
    static final long INITIAL_VALUE = -1L;
    private static final Unsafe UNSAFE;
    private static final long VALUE_OFFSET;
......
}

从代码中可以看到，凡是继承了RhsPadding类的所有类都有一个可以长驻CPU缓存的成员变量value。为什么可以常驻CPU缓存呢？

• value的前面有p1-p7共7个long，一个long类型占用8个字节，加起来就是56个byte，后面也有56个字节，而一个缓存行共64个字节，那么value必将跟一组常量(P1-P7或者P9-P15)在一个缓存行中；
• 如果不加Padding的前后包裹，value就可能跟普通变量公用一个缓存行，那么如果在多线程并发的场景下，因为其他变量的反复更新导致常量value被动的反复失效，刷新到内存，又被拉取到内存，造成性能的严重损失。

这种在常量前后包裹额外的字节的技术叫做缓存行填充技术，在很多对性能要求较高的多线程并发项目代码中时常能够遇到，这个技术跟语言无关，只跟CPU相关，所以属于CPU级别的黑魔法。

当然，还有一些技术也是根据缓存行的特点来设计的，比如：很多高性能系统中使用Ring buffer做缓冲队列，它使用了一个环形的数组做队列，而没有使用LinkedList，是因为数组是连续的内存，更加容易被CPU的缓存行命中，从而减少对内存的寻址，在高并发的状态下可以提高整体系统的吞吐量。

注：缓存行是一个很大的话题，其中包括缓存行的存储结构（虚拟内存与缓存行的映射关系，多路分组技术）与MESI多核缓存行同步协议，了解这些底层知识对于读懂一些著名开源项目至关重要，甚至自己就能写出一个来。

程序在OS级别的缓存优化技术——IO治理

我们认识缓存对于性能优化的作用更多的是在应用系统级别，也就是操作系统级别的，原因是这里有更加丰富的场景，比如：当我们需要从关系型数据库加载大量数据或者比较频繁的加载数据的时候会想到Redis，因为后者具有更高的吞吐量，而Redis为什么在吞吐量上具有如此大的优势？我们从这两者的区别分析说起。

关系型数据库VS Redis

一个重要的原因在于Redis与关系型数据库如Mysql在存取数据方式的不同：

• Mysql等关系型数据库着重点在于数据的安全性与健壮性上，从而对数据有更安全的保证，所以在存储方式上使用更为存储特性更稳定、容量更大的磁盘；
• Redis则是互联网高速发展催生的产品，具有超高的吞吐量，超低的延迟，但是对于保证数据的安全与一致性方面则比关系数据库要低得多（虽然后面有很多的机制来维持比如内存数据的落地，但是相比磁盘读写还有要差得多，必进OS层也会对文件读写的安全性进行保证）；根本原因在于Redis是一个基于内存的数据结构服务器。

所以从存储介质的不同上我们就能很容易的推导出各自的优势与劣势来：

• Mysql等传统的关系型数据库更加擅长长久的保存重要的数据，比如交易数据、用户信息等，而且程序对其的增删查改操作往往有更好的原子性保证，在灾难恢复与数据备份上有更好的产品级支持；但是因为磁盘的访问延迟比内存低4-5个数量级，所以能支持的吞吐量与访问量都不高；本质原因就是将CPU的处理时间更多的放在了数据的安全性上了；
• 而redis是用于解决互联网应用的超高吞吐量与超高的并发访问性能而生的；所以需要将CPU的利用率拉高来达到用更少的机器服务更多用户的需求，所以Redis将数据保存在内存中，使用低延迟的存储来在达到单位时间内执行更多的指令目的。其弱点也是显而易见的，出该容易丢以外，Redis也只提供了少量而常用的几种数据结构，如：hashmap，list，set与zset等等，对于复杂的多维度数据的存储与查询显然支持不够，应用场景就比较单一。

所以，我们在实战的时候往往会综合使用两种存储的优势，然后避免各自短板，如使用关系型数据库作为最终数据备份与落地存储；而对于数据热点的访问、突发性数据访问、读写，可以先在应用层使用Redis来抵挡，然后再合适的时候同步回磁盘介质的关系型数据库。

注：计算机科学中往往会有一些悖论，比如事务性与吞吐量，我们可以使用技术手段将一个程序的吞吐量拉高到CPU的满负荷，但是这时你就必须为此放弃事务性的支持，相反也是，所以当我们看到某某工具宣称即有超高的吞吐量又能完美支持事务性的时候，我们应该多个心眼。

注：文档型数据库——ES或者MangoDB。这类db或者说是数据存取工具因为具有更特殊的存储特性——面向文档存储，而具有一些更加特殊的功能，其性能特点不像Mysql与Redis的区别这么鲜明，所以不展开讨论。我想，特殊的需求会催生出特殊的应用，ES就是这样，它的检索方式更加适合有全文检索需求的应用，其索引是采用倒排序索引方式构建，其占用的磁盘空间相比只能针对特定字段的B树索引需要占据更多的磁盘空间，所以催生出其卓越的分布式存储系统；但是如果把ES与Redis甚至Mysql混为一谈是错误的，具体问题应该具体分析，更不能人云亦云。

Kafka的性能优势

kafka是非常流行的队列服务器，因为其超高的吞吐量被大家所青睐，我们从IO特性来简单分析下原因。

内存消息批处理机制

大家都知道kafka是以“批”为单位来发送与接收消息的，这种“批”有以下两个特点：

1. 消息在发送的时候不是一个个的发送，而是积累到一批才发送，在内存上有局部性；
2. 消息在持久化的时候一批数据是顺序存储的，这样使得数据在磁盘上有很好的局部性、

这样做有什么好处呢？回想一下前面介绍的CPU Cache的缓存行机制就不难理解，“批”在空间上具有很高的局部性，使得发送与读取都能用到CPU的cache机制，使得CPU在访问这些“批”数据的时候能够用较少的内存寻址的指令来处理同样多的数据，从而能够提高程序的吞吐量，特别是在数量特别巨大的“批”上，优势就会体现的更加明显。其本质是，处理的数据量不变，CPU的执行取址指令数量不变的基础之上将部分的内存寻址指令替换成了cpu缓存的寻址，显然效率提高了一两个数量级。

当然凡事有一利必有一弊，我们也要看到，这样做的风险也是巨大的，一旦发送方机器宕机，那么就会丢掉数量以“批”计的数据，很明显“批”越大，风险就越高，kafka要为这个批处理编写大量的保障代码，甚至多副本机制来保障数据的安全性，造成很多资源的浪费；所以当我们需要相当高的安全性保证与事务性保证，但是不是很高的吞吐时，还是使用事务性更好的队列服务器比较好，毕竟达到一样的效果后者使用的资源更少。

磁盘文件的批处理

众所周知，在操作系统中，文件与内存都是以页为单位存取的，这点跟内存与CPU的的cacheline为单位存取机制是一致的，这样能够将这种空间与时间的局部性特点能应用到磁盘的IO上，使得操作系统在访问低速磁盘的时候能够用相同的指令数获得更大效率优势。其具体的机制是：

1. 操作系统对磁盘驱动程序读取或者写入的数据按照页（4K的块）进行缓存；
2. 页缓存具有时间局部性特点，如果操作系统从磁盘驱动读取了一块数据，那么大概率程序还会继续访问同一块数据，如果有缓存，则不需要再从磁盘load，特别是使用了“内存映射文件”机制的读写；
3. 页缓存具有空间局部性特点，比如kakfa接收到一批数据，会将它写入到磁盘暂存，而此时操作系统会先写入内存的页缓存，然后一次性刷入磁盘；而同时kafka的消息处理也是一批批的，所以load这同一批数据，就可以直接从操作系统缓存中获取，而不需要从磁盘中load，从而提高了读写性能。

kafka在做磁盘数据批量存取的时候，因为消息是顺序批存储的，所以能够能好的利用操作系统的磁盘缓存机制来提高IO的性能。

“零拷贝”机制——一个减少运行指令的优化

这也是操作系统提供的一个机制，对于数据传输类的程序尤其重要，我们知道数据的IO读写——磁盘与网络传输都是通过系统调用完成与采用什么编程语言无关。传统操作系统的IO读写操作包括两次系统调用开销，数据从驱动程序拷贝到内核内存，然后内核程序将这段数据原封不动的拷贝到用户态程序内存空间；本质原因是用户态程序不能直接访问内核态虚拟地址空间，而内核程序可以访问用户态虚拟地址空间造成的。

一种优化方式也是常见的方式是通过mmap系统调用，将一段用户态的虚拟内存地址空间直接映射到磁盘（为什么可以这么做呢？因为磁盘与内存共享相同的数据存取方式——页），然后当内核从驱动程序读取到数据后会直接向这段共享的虚拟地址空间写数据，跳过内核往用户态拷贝数据的代码，因为内核可以访问全部的内存空间，这种拷贝是被允许的；因此，这样一来就减少一次数据拷贝，在有大量数据要拷贝的时候就大大的节约了CPU时间，提高了系统的性能。

那么既然可以减少一次，那么你可能已经想到了，那么在一些情况下是可以完全避免这种因为特殊的CPU与OS构造带来的不必要的拷贝的，可以采用直接从磁盘通过DMA控制器向网卡发送数据就可以了。对，kafka就是这么发送“批”数据的；使用是Linux操作系统提供的sendfile系统调用完成所谓的“零”拷贝，从而从IO上做到了机制。

同时可以看到，这种优化方式其实减少了一部分不必要的IO指令来完成的，跟缓存方式并不一样，在大的分类上属于减少指令运行数量来提高性能的方式。

好了，到这里，我们要结束缓存这个机制的介绍，从而开启另一种性能调优常常使用的手段——多线程技术。

程序的并行化执行——多线程技术

多线程技术是一个十分通用的优化方案，在编程语言级别上写出一个有良好结构的多线程程序越来越容易，比如java的CompletetableFuture框架，.Net的anync await异步框架，众多的语法糖大大的降低了多线程程序的构建过程。但是，多线程的基本问题却还是会不断被问到，比如为什么多线程技术能够加速程序执行？是不是所有的程序都能够采用多线程方式提速？

我们照例从文章开头引用的两条定理出发来推出答案。

这要从我们前面介绍过一个事实——冯诺依曼瓶颈说起，CPU与内存，内存与外部存储设备都存在很大的访问延迟，导致我们读写数据的时候需要按照“批”与“块”的方式进行，以充分利用程序或者数据在时间、空间具有局部性原理，从而加快访问速度；所以我们看到了缓存行、操作系统page cache等工程实践。

但是，只有这一种方式来填充冯诺依曼瓶颈吗？如果换个角度看问题，一个程序要处理的事务要是能够由多个worker分工同时做完，那么只要加大资源投入不是也能达到降低单条指令执行速度的目标吗？

我们接着之前炒菜的例子，对于切菜这个工序，我们完全可以使用加大切菜工资源投入来获取并行执行的能力。比如，一个师傅切土豆，另一个师傅切肉，如果还有菜要切那么就加入更多的师傅进来，理论上只要厨房能够容纳得下，切菜这个工序可以在一个单位时间内完成——这就是多线程的本质——切分任务让有限的资源得到充分的利用。

这个方式跟流水线并行处理有何不同之处呢？我想在于切分主体不同：

1. 流水线是通过切分处理单元（CPU）本身来达到任务之间的并行执行；
2. 多线程是通过切分任务本身（WorkLoad）让有限的计算资源获得充分的利用来提高执行的执行效率。

下面一个重要的问题是，是不是所有的工作都能并行化呢？

我想也未必，比如准备食材与切菜、切菜与炒菜这些工序之间就不能并行，因为前后两个工作是有先后依赖的；比如，辣椒炒肉这个菜，必须把辣椒与肉都备齐才能开始炒制，否则就不行。

这就基本可以得出多线程并发执行的特点：

1. 多线程并发也是一种利用提高CPU资源（主要是多核资源）利用率来加快指令运行速度的调优方式；
2. 不是所有的程序都能并行化执行，只有那些能够切分成若干个前后无依赖子问题（map），并通过对这些子问题并行规约（reduce）求解，从而得到问题最终解的那些任务才能通过所谓的多线程方式并行求解；简单的说就是任务能够被map也要能被reduce出最终的结果。

所以，我们又可以推导出能够做多线程并发的先决条件：

1、任务可以被map-reduce；比如：经典的统计词频的算法；矩阵相乘等这种计算密集型任务；

2、重I/O依赖的程序，如web服务器，队列服务器，数据库服务器等等；为了不让CPU空转，线程往往会放弃等待I/O事件，转去执行其他不依赖I/O的任务；当然也可以去执行其他I/O ready的访问请求，如即时通讯类程序就能完美的利用多线程带来的红利。

多线程的弊端

多线程技术能够加快很多程序的运行，但是还是那句话，有利就有弊，多线程的弊端是：

• 线程的上下文切换开销。这也是跟操作系统的设计相关的话题，因为线程工作在用户态，但是归属权却在内核态。打个比方，厨房的师傅虽然工作地点在厨房，但是必须到办公室拿到任务才能知道自己下一步做什么事情；那么经常就会遇到这种情况，师傅刚刚把土豆切到一半，办公室就喊了，““01”号师傅来一趟，有新的任务要执行”，然后01号师傅放下手头的工作跑去办公室领任务；接到新的任务又重新跑回到厨房执行新的任务；试想一下，如果在一个繁忙的厨房，你可以看到所有师傅来回穿梭于厨房与办公室之间；甚至在途中浪费的时间比实际切菜的时间还要多；这就是线程上下文切换的开销；
• 多线程程序虽然有语法糖，但是如果不清楚多线程运行的实质，也很难获得性能的提升。比如，一个不能并行执行的任务，我们也用多线程语法糖去套用，就可能会得到错误的结果，常常表现在一些数据结构的错误使用上，比如java中的Hashmap并不是线程安全的，如果多线程并发会造成死循环。
• 多线程技术会使得程序乱序执行，如果多线程读写了进程共享变量，往往会造成数据读脏或者写脏，导致程序时而计算正确时而计算错误，形成周期性出现的bug。如果，对锁机制不太了解，就很难真正将多线程技术发挥到极致——增加了编程的难度。

多线程编程所涉及到的内容十分多，比较重要的技术点有：CPU多核处理构架（缓存行更新机制）、CPU内存屏障与原子操作、操作系统的几个上下文切换特点、操作系统的锁机制，最后还有每个不同编程语言的内存模型，这些都跟编写高效的多线程程序息息相关，内容多而庞杂，让人头皮发麻想掉头发。

所以，近年来单线程+多路复用+事件通知来处理I/O的模式又兴起了，其实这是另一种优化策略的体现——减少指令运行数量策略，为什么呢？下面来细细讲解。

减少指令运行的数量

Epoll模型——多路复用技术

接着讨论多线程技术在超高并发环境下带来的弊端，其最主要的弊端是线程上下文切换与锁同步机制带来的性能开销。对于一个超高并发的系统，比如每秒可能要接收处理数十万的并发请求，这时服务器上可能有数千线程在OS中来回切换，其带来的切换开销就会变得非常可观，对于workload本身是计算类型，处理时间很短的业务来说线程来回上下文切换的指令执行成本甚至高于了业务计算指令的开销，这就得不偿失了。

形象的比喻就是，厨房没有师傅在干活，都在满大厅的来回乱跑，把时间都耗在路上了。

而另一方面，计算机的多核构架越来越成熟，一个服务器有十几个核心变得家常便饭，这就为单线程构架的复兴提供了充分的前提条件。这里的单线程指的是系统在处理业务时的线程数是每个核心压上一条线程，如果有超线程技术就压上两条，这样在线程不多的情况下，得到多线程并发的好处也有效的规避了其弊端。

那么，你可能会问，单线程的程序规避了多线程带来的上下文切换带来的开销，那么对于一个重IO的程序，如web服务器，如何在一个线程中去管理数十万的Socket链接呢？以前可能是一条线程一个socket，因为socket之间并没有很强的关联性，所以并发执行刚刚可以充分利用CPU做业务，这样的优点不正好也是单线程不具备的吗？更何况，当线程去处理大量的连接，需要去遍历每个socket的IO状态十分消耗时间，那么如何去平衡这多出来的计算量也是单线程模型要面临的挑战。

下面来介绍如何弥补管理海量socket通知请求的鸿沟。

Epoll模型一个成功的多路复用技术

什么是多路复用技术呢？这是一个通信领域的术语，简单的说就是在原来单一的信道上去承载多路的信息传递；比如说，原来一根电话线只能接通一路语音通信，只能服务两个人同时通话；那么通过分频技术的发展，一个电话线可以同时支持多路通话，增加了资源的利用率，这个技术叫做多路复用。

在计算机网络编程领域，多路复用技术专指在同一个线程中响应处理多路socket连接请求。我们知道，socket是网络IO，它位于延迟金字塔的最底层，延迟非常高，是CPU处理速度的5-7个数量级，也就是说理论上讲，单线程是可以同时处理几十万的socket数据的（当然前提是workload不重，能够快速计算返回结构给请求方），问题在于如何在单线程程序中高效的获知socket IO的ready状态，也就是解决前面提出的问题。

Linux因为历史原因曾经支持过多路复用，比如select、poll这两个系统调用，处理的方式是将连接socket描述符都存储在一个链表中，然后每次获得IO就绪的通知，都从头遍历这个链表从而找到一个或者多个就绪的的socket连接；学过算法的同学都知道，遍历链表的复杂度是O(n)，在数据量比较大、操作十分频繁的系统中，这种遍历是非常消耗时间的，这就会吃光单线程程序的优势。

但是，聪明的内核开发者，敏感的意识到这是个典型的算法优化点，只要能够将查找就绪的socket时间从O(n)降下来不就可以完美的解决这个问题了吗？

打个比方说，你要去学校找一个同学，而你只知道他的名字，那么你到了学校后会只能挨个班，挨个人找，最坏的情况是需要全部遍历所有的学生才能最终找到你的同学。

解决这个问题有两个方法，一个是你花钱雇更多的人同时分班去找，只要人足够多，那么就能快速的找到你的同学；这就是多线程技术的解决方案，这个方案的弊端就是你必须花很多钱去雇佣人帮忙，当班级特别多的时候，花销大的惊人，这个场景是线性增长；

而算法技术的提升则是一种类似于降维打击的手段，通过采用合适搜索算法，从根本上减少搜索过程要执行的指令次数，从而缩小问题的计算规模，达到性能的提升。就好比，你托人拿到了学校所有同学的姓名与班级表，并且姓名是拼音排序好的，这是你只要根据要找人的姓名就能快速索引到你要找的同学的班级；这就是算法带来的性能提升，它减少了执行一样任务所包含的指令数。

Epoll最后使用了一种叫做红黑树的数据结构来存储所有的几十万个链接的描述符，而这个数据结构有一个很优异而稳定的查找与插入性能，都是O(logn)！看到公式你可能还不明白这个降维打击的厉害之处，举个例子，如果这个学校有十万人，这个数据结构查找一个特定的元素不会高于12次查询，你看比原来的十万少了多少个数量级；再比如，你要搜索一个拥有4亿人的大班级，也只要30多次即可！是不是很神奇，这就是算法的魔力所在吧。

所以，有了红黑树有了Epoll，单线程管理海量的socket成为了现实，成功的填补了多线程切换带来的性能损失，将CPU的功能都花在了业务处理上来了。

有很多大名鼎鼎的工具如Nginx，Redis都是使用这个模型来实现超高吞吐量的。当然，这个模型也不能滥用，一个前提就是当每个请求的workload不高的情况下，也就是处理短小的业务比较擅长。你可以看看nginx与redis的使用场景便可知道。nginx最大的作用是负载均衡与反向代理，处理的业务跟模式匹配有关属于计算密集类型；而redis更不用说，内存型的数据结构服务器，大部分的查询通过算法与IO优化后都能在超短的时间内完成响应。相反，如果你用这个模型去做高计算量的事务就会得不偿失，顾此失彼了。

算法优化——优化的终点

从上面Epoll的单线程并发模型我们可以领略到算法的能力，将它作为性能优化的终点毫不夸张。一个问题如果在算法上找到降维打击的手段，比如将计算量进行了降阶处理，往往带来的想象力就是无穷的；就好比，化石能源遇到核裂变反应堆，核裂变遇到核聚变一样。

平心而论普通人要想在算法上获得突破其实非常难，对于工程师来说，能够掌握常用的算法知识，掌握常用的数据结构知识，并能够正确识别算法与数据结构的使用场景就已经非常难能可贵了。所以，我们还是来讨论对于软件工程师来说应该如何从数据结构与算法的角度优化系统的性能。

什么是计算机算法

我觉得我们常常讨论的算法应该包含这么几个内涵：

1. 首先计算机算法，顾名思义是只能在计算机上运行的算法；我们知道算法脱胎与数学，而数学本身是博大精深的，而能在计算机上跑的算法应该是数学众多问题中的一小部分。举个例子，计算机能够描述的问题都不是连续的，是离散的，比如数据讨论一个简单的方程y=x^2，数学上讨论的定义域是整个实数域而计算机是不可能描述这么多的数字的；所以计算机讨论的问题都是离散的个别的；
2. 算法对程序的优化主要集中在减少程序所要运行的指令数上（分治算法除外）；
3. 算法具有数学特性，其性能可以使用数学方法形式化严格证明，是跟编程语言，操作系统，硬件构架都无关的普遍真理；比如，很多人说自己得出了比快速排序更优的算法，其实是算法知识掌握不牢固的表现，快速排序是基于元素比较方式下原地排序算法中最优的，这个是通过数学家严格证明的，我们就不用去质疑了，只要知道它的使用条件能够灵活使用就行；
4. 计算机算法是受到数据结构制约的，或者换句话说，计算机算法是运行在特定数据结构的基础之上的，离开了数据结构讨论算法是不对的。比如，还是快速排序算法，如果我么讨论这个算法的性能时不知道它是运行在数组这个基本的数据结构基础之上的那么我们就不可能理解它的内在思想，实现的时候如果用链表存储待排序元素就得不到相应的性能数据了。

那么，知道了什么是计算机算法，我们应该怎么去使用算法优化程序的执行效率呢？我想有些基本的常识是应该了解的，比如常用的数据结构以及运行在上面的算法。

数据结构与算法

要了解数据结构与算法，就必须要要了解计算机如何存储与表达数据。我们知道，计算机分为计算单元CPU与存储单元内存，CPU通过对内存进行随机读写来执行程序，那么随机读写这个特性就决定了计算机存储的一个特征——连续存储的数据结构——我们常说的数组。对，数组这个数据结构可以说是数据结构的始祖，任何一个更高级的数据结构都是从数组演化而来。有了数组这第一个推导出来的数据结构，我们很容易利用计算机随机寻址的功能推测出链表这第二个数据结构。有点类似中国古代哲学的一生二，二生三，三生万物。对，数组与链表就构成了计算机世界中的所有数据结构。

我们看看这两个原始的数据结构的特点：

数组——具有天然的随机读写性能O(1)，但是在数组中插入与删除元素的性能是O(n)

链表——具有天然的动态扩容的性能，对于随机插入与删除元素的性能O(1)，但是随机读写的性能降为了O(n)。

这是最简单也是最重要的特点了，这两个基本的富有对称性与矛盾性的数据结构共同决定了所有计算机算法的运行效率，或者说，计算机算法都是通过这两中数据结构组合而成。

是不是有点向中国文化中的太极？互相矛盾，而又富有高度的对称美，它就是整个计算机世界的基石。

下面我们来看看如何分析数据结构与性能调优的关系：

数组

我们从数组开始，数组是一块连续的内存空间，它其实对性能调优十分重要，因为内存与硬盘本质上就是数组：

1. 数组有相当好的时空局部性，

   1. 用它存储的数据可以很快的被CPU加载，如果常驻内存有很好的缓存命中（cachline那节有阐述）性能，可以用最少的内存访问次数加载完程序的数据，实际会用在高并发的场景如ring buffer等高性能缓冲；
   2. 如果使用数组存储文件，也能够很好的利用到操作系统提供的缓存机制——Kafka的高性能；总之，如果想到缓存则可以想到数组这个数据结构；

2. 随机访问也是一个很好的特性——访问数组元素中任何位置的时间复杂度是O(1)。

   1. 比如，快速排序算法的重要步骤是交换“标杆元素”前后两个元素的位置，那么就要求根据数组索引访问到元素的位置必须是O(1)的，如果用链表，快排就会退化到O(n^2logn)了，比插入排序等都慢；我们知道在世界上的计算机中一半以上的时间都在排序，所以排序算法是算法中最重要的，而这跟数组的随机访问特性分不开；
   2. 利用数组的随机访问特性另一个应用就是构建出堆这种数据结构，有些编程语言叫做priority queue优先级队列。这个数据结构非常有用，因为它有个非常好的特性就是动态插入元素以及找出其中最大(大顶堆)或者最小元素（小顶堆）的时间复杂度都是O(logn)，跟堆中的元素的对数成正比。我们知道对数函数是互联网级的时间复杂度，只要能够拥有这种性能就能被用到大数据，大并发的场景中。具体的应用就是在不需要排序的情况下找到巨量元素中的排名前N的元素，如搜索引擎框中的的topN提示；当然还有流数据计算场景，因为堆是一种动态的数据结构，可以将其想象成一个队列，流过它的数据就能马上过滤出前N个最大或者最小值。堆在编程语言中是一定是用数组实现的，不然性能就会急剧退化；使用的就是数组的随机访问特性+一点点数学知识；
   3. 还有就是哈希表，哈希表在元素不多的情况下可以达到查找性能O(1)，当然也是利用了数组的随机访问的特性。

   当然数组也有它的劣势，如：

   1. 因为数组的动态特性不好，也就是随机插入与删除元素都涉及到大量的元素拷贝与移动，所以对于需要动态变化容量的使用场景就不适合使用数组，比如队列，栈；ringbuffer是个例外，但是它的实现需要写很多复杂的逻辑来保证其动态特性，导致代码复杂健壮性不好；
   2. 哈希表的适用性也受到数组扩容性能差的影响。在工程中特别是像linux内核这种要求对性能有严格预期的大系统，很少使用哈希表做查找表的实现，其一个重要的原因是哈希表的动态扩容性能不佳，在极端情况下，数组的扩容需要完成“拷贝”与“rehash”两个重量级操作，系统的性能就有抖动；而且在多线程情况下容易出现死循环，所以哈希表往往只能在对性能不苛刻的业务场景。

   链表

   链表弥补了数组动态性能低的特点，因为有很好的可塑性，可以用来实现很多结构更离散的数据结构：

   1. 二叉树就是链表的一个使用场景。二叉树是一种树状结构，其中平衡二叉树在插入与删除的过程中只要移动logn次就能找到自己的新位置，而且代码简单易于维护（不容易写错也是工程中一个重要的考虑点，如果写得代码过于复杂就要反思下是否使用错了数据结构）。比如：红黑树就是一个综合性能很好的平衡二叉查找树；它是一个动态的数据结构，可以在动态添加与查找过程中稳定在O(logn)量级；在Linux内核中大量使用；而且在Java中的ConcurrentHashMap在冲突大的情况下，冲突元素大于8也会升级成红黑树存储冲突元素，来平衡工程与算法效率之间的矛盾；
   2. 队列与栈——十分重要的动态数据结构，可以用来实现大量数据的缓冲，构建大量数据的离散关系。这两种数据结构本身的应用场景非常的多，队列用来实现图的广度优先遍历，而栈则用于深度优先的遍历；栈的先进先出的特点，还是实现函数调用的核心数据结构，也是在编译期器中模拟数学表达式的数据结构；队列的使用场景就更多，java中的ReentryLock的线程排队阻塞队列就是一个队列；
   3. 链表通过改造也可以有很快的查询效率，比如因为Redis而火起来的skiplist（跳跃表，实现zset的数据结构），其本质跟我们平时根据地址快速投递快递的原理是一致的；快递员在投递快递之前并不需要对所有中国人的地址进行排序，可以说我们的地址是高度离散的；虽然人们的地址存储是无序的，但是我们地址信息是高度索引化的，比如，所有人的地址格式可以是：XX省XX市XX区XX街道XX小区XX楼XX单元XX号，这么8个等级，每个等级可以帮助你过滤掉一大批数据；比如你在湖北省，那么可以在O(1)的时间里面过滤掉十几亿人，然后每比对一层过滤掉一些数据，最后精确定位到你，这样的搜索效率可以看做是O(logn)级别的；而人的出生与迁移，也只要在各自的索引区间中动态的链接新的信息，删除老的信息即可，时间复杂度也是O(logn)的，这种数据结构就是互联网级别的。跳跃表就是在链表的基础上加入了额外的索引指针，用来根据不同的维度将链表中的数据进行分块，类似于对地址区域的分块，这样既保证了高效的查询效率也保证了动态的更新效率；同时还能快速的输出区间元素，是一种工程上很好的数据结构，唯一的弊端可能就是相比红黑树需要更多的存储空间来存放索引信息，而些开销相比收益是可以忽略的。

   融合是关键

   数组与链表是两个极端，我想对于性能调优来说，重要的是灵活组合他们的的优势，规避它们各自的劣势，达到工程上的平衡才是我们的终极目标。比如java中的LinkedHashMap就是融合了数组、哈希表与链表的优秀实践：

   • 普通的哈希表因为通过哈希函数将元素链接到数组的索引号上面，实现高速的查找性能，但是丢失了元素的插入顺序，而有时候我们需要这个顺序性来实现特殊的需求，比如缓存淘汰策略；
   • 而如果使用链表，形成一个插入的队列，先插入的在队列头，后插入在队列尾部；但是这样虽然保存了插入的顺序但是丢失了查找性能；
   • 为了平衡，我们可以在哈希表的基础上，每个元素再增加一个指针用来连接前后插入的元素，形成队列，这样没插入一个元素不仅在哈希表上挂载新的索引点，还要将新元素挂接到队列的尾部，而每一步都是O（1）的开销，是可以接受的，这就是LinkedHashMap的实现原理。

LinkedHashMap

通过分析SkipList与LinkedHashMap的例子，我们可以得出结论，在优化数据结构的时候您需要综合考虑数组与链表的特性，并通过要实现的插入与查找的性能特定灵活的组合出你所需要的数据结构来。

而且，在分析数据结构性能的时候，特别是平衡动态更新与快速查找效率这两个对立面的时候，我们要想起数组与链表的特点，想起它们就是一个太极图的两个部分，如果要获取两者的优点，就必须要付出空间或者时间的额外代价来实现——天下没有免费的午餐。

算法设计技术——通用的算法思考方法

很多同学对算法设计技术并不是很熟悉，我们前面知道，算法是构建在数据结构基础之上的，具备一定数学特点的计算规则，它可以帮我们将一个问题的计算规模降维打击，达到优化程序运行的需求。数据结构与算法往往只针对具体的技术点，比如平衡存储与查找的效率，优化局部的技术问题，这跟具体的现实世界的问题还有区别的，比如著名的“背包问题”，“编码长度优化”问题，往往这些问题更加贴近生活，需要更高的算法设计能力，而不同的设计方案往往会因为最终的计算指令规模不同而体现出不同的运行效率。

举个例子：“背包问题”如果用蛮力算法，其计算量是O(2^n)级别的，这个级别的代码对于计算机来说因为随着背包中物品数量n的增长计算量是指数级别增长的，几乎是计算机不可解范围；而如果用分治算法优化，可以达到O(nlogn)级别，达到计算机可解范围；而如果用动态规划方式优化，则可以达到线性的级别O(n)；可见一个问题到底用什么算法技术去解决就可以得到完全不同的结果，所以在实际的工作中，我们对于一些具体的问题，可以形成一些解决方案套路，通过套用这些套路获取一个计算量的预期，从而实现优化——这就是算法设计技术的作用。

算法设计技术是一个很复杂的领域，是计算机科学的深水区，同时也是算法领域的深水区，可以说计算机能解决什么样的具体问题、可解问题的边界在哪都是由算法设计技术推动与决定的。这块内容十分高深，涉及的知识非常多，是计算机科学家工作的领域，比如著名的N=NP问题就是这个领域的著名问题，如果成功解决可以获得图领奖，但是直到现在也还悬而未决。

那么工程师要知道哪些算法设计的技术呢？我远远不是这方面的专家没法给出答案，但是我觉得至少算法技术的分类以及一些基本的常识还是能够理解的，不然遇到具体程序优化问题就不知道要找什么领域的论文寻找答案。

算法设计大致可以分为三种：

1. 贪心算法，特点是往往是最值的求解，比如寻找一种最优的编码方案——哈夫曼编码；在图中寻找最小生成树——Prim算法，大名鼎鼎的单源最短路径算法，对这些算法中都有最字，本质是在海量的排列组合中通过一个算法高效的计算出最优的一个来。而贪心算法有一个区别其他规划算法的特点——结构简单，只用一个简单容易理解的原则就能求出最优解。比如凑硬币问题，1，2，5，10三种面额的硬币，凑出金额n的零钱来，请问最少的硬币数是多少？那么可以通过每次使用最大面额来匹配来得出最后的最优解。可见，贪心算法结构是十分简单的，编程也十分清晰，但是世界是公平的，实际能够使用贪心解决的问题特别少（原因不明），较为不常见。而且，在使用贪心算法求解之前必须要通过数学证明，而对于贪心来说，数学证明是难点；

2. 分治算法，分治是很容易理解的，它的思想被用在很多大数据框架上，比如，Map-Reduce，PageRank的计算等等。分治的特点是：分而治之，将原本规模很大的问题分解成n个规模较小的子问题，而这些子问题是彼此无关的，计算机通过将这些子问题发送到多台计算机上同时处理，达到加速计算的目标，最后通过线性的归并过程处理每个分片的结果得到最后的解。分治的难点是子问题分解，要特别注意分解后的子问题要是无关联的，只有无关联最后归并才会正确；而要证明一个问题能够被分解成n个子问题是需要去证明的，这是分治的关键；一般来说能够用分治解决问题的计算规模都是O(nlogn)。

3. 动态规划算法。动态规划能够解决的问题是最多的，从“背包问题”、“生产规划问题”、“CPU良品率检测”、“工作安排”、“图像压缩”到“RNA最优二级子结构”，应用的领域非常广，是经常需要使用或者考虑的算法设计方法；动态规划的特点有：

   1. 动态规划要解决的问题跟贪心算法很像，一般都是解决最值问题，要解决的问题都是在几何级数增长的组合中找到最优解；
   2. 动态规划跟分治在结构上很相似，都是将大问题切分成若干个子问题来求解，最大的区别在于分治要求子问题无关，而动态规划要求子问题有关而且计算是有重叠的；这样的重叠子问题越多，用动态规划获得的收益越高；
   3. 动态规划的本质就是在子问题递归树上通过对重复计算子问题缓存结果，减少重复计算来提高运行效率。通过对分支重复子问题计算进行优化可以动态规划算法往往能够得到比分治算法更好的结果。往往时间复杂度能被优化到线性O(n)级别；
   4. 动态规划算法有较好的时间复杂度收益与广泛的使用场景，但是要找到动态规划的递推方程是十分难的，需要具备很好的逻辑推理能力，与长期的训练才能达到。

   建议大家可以读读算法设计领域的书，这块已经到达了计算机科学的核心，是最后的高峰。

总结

性能优化本身是一个很大的话题，从不同的技术、不同的工具有不同的特点与实现细节，不同的技术细节又有不同的运行环境，要涵盖所有的优化方案显然是不可能的；但是幸好，我发现不管是什么领域什么技术，只要它运行在计算机上，那么它就有一些通用的方法，本文就是努力为您阐释两个基本的套路——减少指令数量与缩短指令运行时间；了解这些分析性能问题的基本套路就能在面对具体调优问题是达到事半功倍的目的。