性能优化技巧之算法

算法的种类和实现浩如烟海，但是在这篇文章里面，不讨论单核，单线程的算法，而是讨论多核，多线程的算法;不讨论所有的算法类型(这个不是本文作者能力范围之内的事)，而是讨论在多核网络设备里面常见的算法，以及可能的优化途径，这些途径有些经过了验证，有些还是处于想法阶段，暂时没有实现数据的支持。

多核算法优化的目标无非两种：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)的数据结构，都需要一个状态机。不同状态下，做不同的事，而增加锁的粒度，也就是增加了状态机的数量(不是状态的数量)，减小状态保护的范围。这个需要在实践中体会。