性能优化的方法和技巧：算法

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

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

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

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

多核算法优化的目标无非两种：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都是空的情况，这里只是减少了分配和释放的争用，但不能完全消除这种争用）。

不管是lock-based还是CAS-based (lock-free)的数据结构，都需要一个状态机。不同状态下，做不同的

事，而增加锁的粒度，也就是增加了状态机的数量（不是状态的数量），减小状态保护的范围。这个需要在

实践中体会。

参考资料：

1：http://en.wikipedia.org/wiki/Lock-free_and_wait-free_algorithms

2：http://yongsun.me/2010/01/%E4%BD%BF%E7%94%A8cas%E5%AE%9E%E7%8E%B0lock-free%E7%9A%84%E4%B8%80%E4%B8%AA%E7%B1%BB%E6%AF%94/

3：http://www.cppblog.com/johndragon/archive/2010/01/08/105207.html

4：http://kb.cnblogs.com/page/45904/

5：http://www.parallellabs.com/2010/10/25/practical-concurrent-queue-algorithm/