性能優化技巧之算法
算法的種類和實現浩如煙海，但是在這篇文章里面，不討論單核，單線程的算法，而是討論多核，多線程的算法;不討論所有的算法類型(這個不是本文作者能力范圍之內的事)，而是討論在多核網絡設備里面常見的算法，以及可能的優化途徑，這些途徑有些經過了驗證，有些還是處于想法階段，暫時沒有實現數據的支持。
多核算法優化的目標無非兩種：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)的數據結構，都需要一個狀態機。不同狀態下，做不同的事，而增加鎖的粒度，也就是增加了狀態機的數量(不是狀態的數量)，減小狀態保護的范圍。這個需要在實踐中體會。
【編輯推薦】
