算法的種類和實現(xiàn)浩如煙海，但是在這篇文章里面，不討論單核，單線程的算法，而是討論多核，多線程的算法;不討論所有的算法類型(這個不是本文作者能力范圍之內(nèi)的事)，而是討論在多核網(wǎng)絡設備里面常見的算法，以及可能的優(yōu)化途徑，這些途徑有些經(jīng)過了驗證，有些還是處于想法階段，暫時沒有實現(xiàn)數(shù)據(jù)的支持。

多核算法優(yōu)化的目標無非兩種：lock-free和lock-less。

lock-free是完全無鎖的設計，有兩種實現(xiàn)方式：

• Per-cpu data，顧名思義，每個核或者線程都有自己私有的數(shù)據(jù)結構(這里的私有和thread local data是有區(qū)別的，這里的私有是邏輯上私有，并不意味著別的線程無法訪問這些數(shù)據(jù);而thread local data是線程私有的數(shù)據(jù)結構，別的線程是無法訪問的。當然，不管是邏輯上私有，還是物理上私有，把共享數(shù)據(jù)轉化成線程私有數(shù)據(jù)，就可以避免鎖，避免競爭)。全局變量是共享的，而局部變量是私有的，所以多使用局部變量，同樣可以達到無鎖的目的。
• CAS based，CAS是compare and swap，這是一個原子操作(spinlock的實現(xiàn)同樣需要compare and swap，但區(qū)別是spinlock只有兩個狀態(tài)LOCKED和UNLOCKED，而CAS的變量可以有多個狀態(tài));其次，CAS的實現(xiàn)必須由硬件來保障(原子操作)，CAS一次可以操作32 bits，也有MCAS，一次可以 比較修改一塊內(nèi)存?；贑AS實現(xiàn)的數(shù)據(jù)結構沒有一個統(tǒng)一，一致的實現(xiàn)方法，所以有時不如lock based的算法那么簡單，直接，針對不同的數(shù)據(jù)結構，有不同的CAS實現(xiàn)方法，讀者可以自己搜索。

lock-less的目的是減少鎖的爭用(contention)，而不是減少鎖。這個和鎖的粒度(granularity)相關，鎖的粒度越小，等待的時間就越短，并發(fā)的時間就越長。

鎖的爭用，需要考慮不同線程在獲取鎖后，會執(zhí)行哪些不同的動作。以session pool的分配釋放為例：假設多個線程都會訪問同一個session pool，分配或者釋放session。session pool是個tailq，分配在head上進行;而釋放在tail上進行。

如果多個線程同時訪問session pool，需要一個spinlock來保護這個session pool。那么分配和釋放兩個不同的動作，相互之間就會有爭用，而且多個線程上的分配，或者釋放本身也會有爭用。

現(xiàn)在我們可以考慮分配用一個鎖，釋放用一個鎖，生成一個雙端隊列，這樣可以減少分配和釋放之間的爭用。

http://www.parallellabs.com/2010/10/25/practical-concurrent-queue-algorithm/ (參考這篇文章)。

也可以考慮用兩個pool，分配一個pool，釋放一個pool，在分配pool用完之后，交換兩個pool的指針(這時要考慮兩個pool都是空的情況，這里只是減少了分配和釋放的爭用，但不能完全消除這種爭用)。

不管是lock-based還是CAS-based (lock-free)的數(shù)據(jù)結構，都需要一個狀態(tài)機。不同狀態(tài)下，做不同的事，而增加鎖的粒度，也就是增加了狀態(tài)機的數(shù)量(不是狀態(tài)的數(shù)量)，減小狀態(tài)保護的范圍。這個需要在實踐中體會。

原文：性能優(yōu)化的方法和技巧：算法

【編輯推薦】

1. 性能優(yōu)化技巧之必備知識
2. 性能損耗?文件服務器容量工具告訴你為什么
3. 性能優(yōu)化技巧之代碼層次優(yōu)化