性能优化

算法的种类和实现浩如烟海，但是在这篇文章里面，不讨论单核，单线程的算法，而是讨论多核，

多线程的算法；不讨论所有的算法类型（这个不是本文作者能力范围之内的事），而是讨论在多

核网络设备里面常见的算法，以及可能的优化途径，这些途径有些经过了验证，有些还是处于想法

阶段，暂时没有实现数据的支持。

多核算法优化的目标无非两种：lock-free和lock-less。

lock-free是完全无锁的设计，有两种实现方式：

• Per-cpu data，顾名思义，每个核或者线程都有自己私有的数据结构（这里的私有和thread local

        data是有区别的，这里的私有是逻辑上私有，并不意味着别的线程无法访问这些数据；而thread

        local data是线程私有的数据结构，别的线程是无法访问的。当然，不管是逻辑上私有，还是物理

        上私有，把共享数据转化成线程私有数据，就可以避免锁，避免竞争）。全局变量是共享的，而局部

        变量是私有的，所以多使用局部变量，同样可以达到无锁的目的。

• CAS based，CAS是compare and swap，这是一个原子操作（spinlock的实现同样需要compare

        and swap，但区别是spinlock只有两个状态LOCKED和UNLOCKED，而CAS的变量可以有多个状态）；

        其次，CAS的实现必须由硬件来保障（原子操作），CAS一次可以操作32 bits，也有MCAS，一次可以

        比较修改一块内存。基于CAS实现的数据结构没有一个统一，一致的实现方法，所以有时不如lock based

        的算法那么简单，直接，针对不同的数据结构，有不同的CAS实现方法，读者可以自己搜索。

lock-less的目的是减少锁的争用（contention），而不是减少锁。这个和锁的粒度（granularity）相关，锁

的粒度越小，等待的时间就越短，并发的时间就越长。

锁的争用，需要考虑不同线程在获取锁后，会执行哪些不同的动作。以session pool的分配释放为例：假设

多个线程都会访问同一个session pool，分配或者释放session。session pool是个tailq，分配在head上

进行；而释放在tail上进行。

如果多个线程同时访问session pool，需要一个spinlock来保护这个session pool。那么分配和释放两个

不同的动作，相互之间就会有争用，而且多个线程上的分配，或者释放本身也会有争用。

现在我们可以考虑分配用一个锁，释放用一个锁，生成一个双端队列，这样可以减少分配和释放之间的争用。

http://www.parallellabs.com/2010/10/25/practical-concurrent-queue-algorithm/ （参考这篇文章）。

也可以考虑用两个pool，分配一个pool，释放一个pool，在分配pool用完之后，交换两个pool的指针（这时

要考虑两个pool都是空的情况，这里只是减少了分配和释放的争用，但不能完全消除这种争用）。

性能优化这个话题可大可小。从大的方面来说，在系统设计之初，需要考虑硬件的选择，操作系统的选择，

基础软件平台的选择；从小到方面来说，每个子系统的设计，算法选择，代码怎么写，如何使用编译器的

选项，如何发挥硬件的最大性能等等。本系列关注的是在给定硬件平台，给定操作系统和基础软件平台的

情况下，如何优化代码，简而言之，就是关注小的方面。

在给定硬件平台的情况下，如何发挥硬件的最大效能？前提是需要对硬件平台很熟悉。如何分离硬件相关

代码和硬件无关的代码是一个很重要的技能。针对某一硬件平台优化固然是好，但是如果代码都是硬件相关

的，就失去了可移植性，软件的性价比不一定高。

性能优化只是系统的一个方面，它会和系统的其他要求有冲突，比如

• 可读性：性能优化不能影响可读性，看起来不怎么漂亮的代码，没有人愿意维护
• 模块化：性能优化往往需要打破模块的边界，想想这是否值得
• 可移植：隔离硬件相关的代码，尽量使用统一的API
• 可维护：许多性能优化的技巧，会导致后来维护代码的人崩溃

需要在性能优化和上述的几个要求之间做出tradeoff，不能一意孤行。

性能优化的目标是什么？不外乎两个：

• 时间性能：减小系统执行的时间
• 空间性能：减小系统占用的空间

那么我们优化的策略，首先就是对系统进行分解，测量：

• 分解：系统包含的子系统，执行路径，函数，指令等等
• 测量：每个子系统，执行路径，函数，指令所花费的时间和空间

然后，选取执行次数最多，消耗时间最长的函数进行优化（这里需要指出的是，消耗时间最长的函数并不

一定就是优化的对象，这个需要放到某个执行路径上去考察，优化最常使用的执行路径）。

对于单核和多核的优化，有什么不同？以cache miss为例，在单核上

• I-cache miss的原因是什么？一是代码路径太长，以至于超出了cache的容量，cache需要替换；二是

        多个执行路径之间相互交替，cache需要替换；三是I-cache, D-cache互相踩。（对于i-cache的优化，

        基本上没有什么可遵循的规则。最有效的还是：一，减少无用的代码；二，减少冗余的代码；三，减少

        函数调用的开销；4，快速路径短小精干，相关代码相邻；5，相关代码放到一个段里面等等）

• D-cache miss的原因是什么？一是数据结构太大，超出了cache的容量（大数组，长链表都会有这个问

        题，比较之下，还是数组更让人放心一点）；二是多个数据结构之间相互踩（问题是一个执行路径，需要

        访问那么多数据吗？如果是，这个路径是不是太复杂了一点）；三是D-cache和I-cache的冲突（这个不好

        说，系统里面会出现这种模式的cache miss吗？）

在多核上，cache miss会有什么新的特点？

• I-cache miss：多核有独立的L1 cache，共享的L2/L3 cache。如果多条执行路径同时进行，cache的冲突

        几率就会增大。但是这是没办法的事情，总不能什么事都不做吧。所以，对i-cache的优化，关注快速路径就

        可以了，不要把精力都花费在这个上面

从系统层次去优化系统往往有比较明显的效果。但是，在优化之前，我们先要问一问，能否通过扩展

系统来达到提高性能的目的，比如:

• Scale up: 用更强的硬件替代当前的硬件
• Scale out: 用更多的部件来增强系统的性能

使用更强的硬件当然和优化没有半点关系，但是如果这是一个可以接受的方案，为什么不用这个简单易行

的方案哪？替换硬件的风险要比改架构，改代码的风险小多了，何乐而不为？

Scale out的方案就有一点麻烦。它要求系统本身是支持scale out，或者把系统优化成可以支持scale out。

不管是哪一种选择，都不是一个简单的选择。设计一个可以scale out的系统已经超出了本文所要关注的范围，

但是，scale out应该是系统优化的一个重要方向。

下面会讨论一些常见的系统优化的方法，如果还有其他没有提到的，也欢迎读者指出来。

1) Cache

• Cache是什么？Cache保存了已经执行过的结果。
• Cache为什么有效？一是可以避免计算的开销（比如SQL查询的开销）；二是离计算单元更近，所以访

        问更快（比如CPU cache）。

• Cache的难点在哪里？一是快速匹配，这涉及到匹配算法选择（一般用哈希表），Cache容量（哈希表的

        容量影响查找速度）；二是替换策略（一般使用LRU或者随机替换等等）。

• Cache在哪些情况下有效？毫无疑问，时间局部性，也就是当前的结果后面会用到，如果没有时间局部性，

        Cache就不能提高性能，反而对性能和系统架构有害处。所以在系统设计之初，最好是审视一下数据流程，

        再决定是否引入Cache层。

2) Lazy computing

  Lazy computing（延迟计算），简而言之，就是不要做额外的事情，特别是无用的事情。最常见的一个例子

就是COW(copy on write)，可以参考这个链接http://en.wikipedia.org/wiki/Copy-on-write。

• COW是什么？写时复制。也就是说fork进程时，子进程和父进程共享相同的代码段和数据段，如果没有写

        的动作发生，就不要为子进程分配新的数据段（通常在fork之后，会有exec，用新的代码段和数据段替换

        原来的代码段和数据段，所以复制父进程的数据段是没有用的）。

• COW为什么有效？一是可以节省复制内存的时间，二是可以节省内存分配的时间（到真正需要时再分配，

        虽然时间不会减少，但是CPU的使用更加均匀，避免抖动）。

• COW的难点在哪里？一是引用计数，多个指针指向同一块内存，如果没有引用计数，内存无法释放；二是

        如何知道哪块内存是可以共享的？（在fork的例子里面，父进程，子进程的关系非常明确，但是在有些应用

        里面，需要查找能够共享的内存，查找需要花时间）

   Lazy computing在哪些情况下有效？目前能想到的只有内存复制。用时分配内存算不算哪？用时分配内存不能

代码层次的优化是最直接，也是最简单的，但前提是要对代码很熟悉，对系统很熟悉。很多

事情做到后来，都是一句话：无他，但手熟尔^-^。

在展开这个话题之前，有必要先简单介绍一下Cache相关的内容，如果对这部分内容不熟悉，

建议先补补课，做性能优化对Cache不了解，基本上就是盲人骑瞎马。

Cache一般来说，需要关心以下几个方面

1）Cache hierarchy

  Cache的层次，一般有L1, L2, L3 （L是level的意思）的cache。通常来说L1，L2是集成

  在CPU里面的（可以称之为On-chip cache），而L3是放在CPU外面（可以称之为Off-chip

  cache）。当然这个不是绝对的，不同CPU的做法可能会不太一样。这里面应该还需要加上

  register，虽然register不是cache，但是把数据放到register里面是能够提高性能的。

2）Cache size

   Cache的容量决定了有多少代码和数据可以放到Cache里面，有了Cache才有了竞争，才有

   了替换，才有了优化的空间。如果一个程序的热点(hotspot)已经完全填充了整个Cache，那

   么再从Cache角度考虑优化就是白费力气了，巧妇难为无米之炊。我们优化程序的目标是把

   程序尽可能放到Cache里面，但是把程序写到能够占满整个Cache还是有一定难度的，这么大

   的一个Code path，相应的代码得有多少，代码逻辑肯定是相当的复杂（基本上是不可能，至少

   我没有见过）。

3）Cache line size

   CPU从内存load数据是一次一个cache line；往内存里面写也是一次一个cache line，所以一个

   cache line里面的数据最好是读写分开，否则就会相互影响。

4）Cache associative

   Cache的关联。有全关联(full associative)，内存可以映射到任意一个Cache line；也有N-way

   关联，这个就是一个哈希表的结构，N就是冲突链的长度，超过了N，就需要替换。

5）Cache type

   有I-cache（指令cache），D-cache（数据cache），TLB（MMU的cache），每一种又有L1,

   L2等等，有区分指令和数据的cache，也有不区分指令和数据的cache。

更多与cache相关的知识，可以参考这个链接：

 http://en.wikipedia.org/wiki/CPU_cache

或者是附件里面的cache.pdf，里面有一个简单的总结。

代码层次的优化，主要是从以下两个角度考虑问题：

1）I-cache相关的优化

   例如精简code path，简化调用关系，减少冗余代码等等。尽量减少不必要的调用。但是有用

还是无用，是和应用相关的，所以代码层次的优化很多是针对某个应用或者性能指标的优化。有

针对性的优化，更容易得到可观的结果。

“工欲善其事，必先利其器”（孔子），虽然“思想比工具更重要”（弯曲网友），但是，

如果没有工具支持，性能优化就会非常累。思想不好掌握，但是使用工具还是比较好学习的，

有了工具支持，可以让初级开发者更容易入门。

性能优化用到的工具，需要考虑哪些方面的问题？

1）使用工具是否需要重新编译代码？

  一般来说，性能优化工具基本上都需要重新编译代码。因为在生产环境里面使用的image，应该

是已经优化过的image。不应该在用户环境里面去调试性能问题。但Build-in的工具有一个好处就

是性能测试所用的image和性能调试所用的image是相同的，这样可以避免重新编译所带来的误差。

2）工具本身对测量结果的影响

  如果是Build-in的工具，需要减小工具对性能的影响，启用工具和不启用工具对性能的影响应该

在一定范围之内，比如5%，否则不清楚是工具本身影响性能还是被测量的代码性能下降。

  如果是需要重新编译使用的工具，这里的测试是一个相对值，不能做为性能指标的依据。因为

编译会修改代码的位置，也可能会往代码里面加一个测量函数，它生成的image和性能测试的image

不一样。

在这里要列出几个我用过的Linux工具，其他系统应该也有对应的工具，读者可以自己搜索。

性能测试工具一般分这么几种

1）收集CPU的performance counter。CPU里面有很多performance counter，打开之后，会

记录CPU某些事件的数量，比如cache miss, 指令数，指令时间等等。这些counter需要编程才能

使用。测量哪一段代码完全由自己掌握。

2）利用编译器的功能，在函数入口和出口自动加回调函数，在回调函数里面，记录入口和出口的

时间。收集这些信息，可以得到函数的调用流程和每个函数所花费的时间。

3）自己在代码里面加入时间测量点，测量某段代码执行的时间。这种工具看起来和#1的作用差

不多，但是由于performance counter编程有很多限制，所以这种工具有时还是有用处的。

在Linux里面，我们经常会用到

1）Oprofile

Oprofile已经加入了linux的内核代码库，所以不需要打patch，但是还需要重新编译内核才可以

使用。这是使用最广泛的linux工具，网上有很多使用指南，读者可以自己搜索参考。

http://oprofile.sourceforge.net/news/

http://people.redhat.com/wcohen/Oprofile.pdf

2) KFT and Gprof

KFT是kernel的一个patch，只对kernel有效；Gprof是gcc里面的一个工具，只对用户空间的

程序有效。这两个工具都需要重新编译代码，它们都用到了gcc里面的finstrument-functions

选项。编译时会在函数入口，出口加回调函数，而且inline函数也会改成非inline的。它的工作

原理可以参考：

http://blog.linux.org.tw/~jserv/archives/001870.html

这是一个可以用一本书来讲的话题，用一系列博客来讲，可能会比较单薄一点，这里只捡重要的说，

忽略很多细节，当然以后还可以补充和扩展这个话题。

我以前就说过，性能优化有三个层次：

• 系统层次
• 算法层次
• 代码层次

系统层次关注系统的控制流程和数据流程，优化主要考虑如何减少消息传递的个数；如何使系统的

负载更加均衡；如何充分利用硬件的性能和设施；如何减少系统额外开销（比如上下文切换等）。

算法层次关注算法的选择（用更高效的算法替换现有算法，而不改变其接口）；现有算法的优化

（时间和空间的优化）；并发和锁的优化（增加任务的并行性，减小锁的开销）；数据结构的

设计（比如lock-free的数据结构和算法）。

代码层次关注代码优化，主要是cache相关的优化（I-cache, D-cache相关的优化）；代码执行顺序

的调整；编译优化选项；语言相关的优化技巧等等。

性能优化需要相关的工具支持，这些工具包括编译器的支持；CPU的支持；以及集成到代码里面的

测量工具等等。这些工具主要目的是测量代码的执行时间以及相关的cache miss, cache hit等数据，

这些工具可以帮助开发者定位和分析问题。

性能优化和性能设计不同。性能设计贯穿于设计，编码，测试的整个环节，是产品生命周期的第一个

阶段；而性能优化，通常是在现有系统和代码基础上所做的改进，属于产品生命周期的后续几个阶段

（假设产品有多个生命周期）。性能优化不是重新设计，性能优化是以现有的产品和代码为基础的，

而不是推倒重来。性能优化的方法和技巧可以指导性能设计，但两者的方法和技巧不能等同。两者关注

的对象不同。性能设计是从正向考虑问题：如何设计出高效，高性能的系统；而性能优化是从反向考虑

问题：在出现性能问题时，如何定位和优化性能。性能设计考验的是开发者正向建设的能力，而性能

优化考验的是开发者反向修复的能力。两者可以互补。

后续我会就工具，架构，算法，代码，cache等方面展开讨论这个话题，敬请期待。

cache在性能优化里面占有很重要的地位，在性能优化的不同层次上，都会用到与cache相关的知识，下面是一些问题和思考。

1）很显然，cache的容量是有限的，所以就会有cache miss，cache miss一般有三种原因：

a: 当cache为空的时候，需要把内容调入cache。

b: 当超出cache容量的时候，需要淘汰一些旧的内容，腾出空间给新的内容。

c: cache conflict，在有冲突的时候，需要用旧的覆盖新的。

第一种情况对任何cache都是适用的；第二种情况，比如CPU的L2 cache，如果是全关联的cache，那么超出容量是，任何一个旧的都可能被踢出去；第三种情况一般是在N-way 关联的时候，映射到相同cache line的内容之间有冲突。

一般来说CPU有如下的cache类型：

  L1 I-cache, L1 D-cache, TLB, L2 cache, L3 cache。L1 cache和TLB cache容量较小，可以做成全关联的，L2, L3 cache一般是N-way关联的。cache在正常情况下，应该是可以提高性能的，但是在cache thrashing (pingpong)的时候，对性能却是有害的。在这种情况下，所有的访问都不能从cache里得到数据，而是需要到Main memory里去拿数据，所以编程的时候要比较cache thrashing。

2）如果避免cache thrashing，如何提高性能？

一般来说，跨边界的数据结构都是有害的。比如一个小于32 bytes的数据结构跨两个cache line，比如程序代码太大，正好在这个路径上，发生了cache conflict。一般来说L1 cache有64k，而L2 cache有1M或者更大。代码路径的长度不太可能有这么大的跨度。但是，最好是把相关的代码放在一起，最好减小代码的体积，最好把数据结构cache line对齐等等一下基本规则还是从一开始就遵守的好。

解决这个问题使用的技巧就是coloring。page coloring比较好理解，相同color的page会映射到相同的cache上去，所以在分配的时候，尽量比较给同一个process分配相同color的page。但是对于slab allocator的color就有点不太明白了。如果color的偏移是cache line大小还好理解，如果是其他的大小，感觉就没什么用。而且在slab allocator的论文里面提到memory channel，这个和cache没什么关系。memory channel是特定的物理地址在特定的内存片里面，如果是dual channel，最好数据地址能够分配到两个channel上，这样就可以并行读入，而不是顺序读入。这个是用来提高内存带宽的（当然可以可以说是避免冲突，因为如果是顺序访问，就说明两次读入是有冲突的）

3）L1 cache或者TLB里面，是虚地址，还是物理地址。这个和cache本身没有关系，这涉及到一个转换的问题。所以我认为在cache里面应该是物理地址，也就是说CPU在访问内存时，MMU是首先执行的，首先解决了TLB miss的问题，才能解决cache miss的问题，顺序不能乱。

The Elements of Cache Programming Style

http://en.wikipedia.org/wiki/Cpu_cache