性能優(yōu)化技巧之算法
算法的種類和實(shí)現(xiàn)浩如煙海，但是在這篇文章里面，不討論單核，單線程的算法，而是討論多核，多線程的算法;不討論所有的算法類型(這個(gè)不是本文作者能力范圍之內(nèi)的事)，而是討論在多核網(wǎng)絡(luò)設(shè)備里面常見(jiàn)的算法，以及可能的優(yōu)化途徑，這些途徑有些經(jīng)過(guò)了驗(yàn)證，有些還是處于想法階段，暫時(shí)沒(méi)有實(shí)現(xiàn)數(shù)據(jù)的支持。
多核算法優(yōu)化的目標(biāo)無(wú)非兩種：lock-free和lock-less。
lock-free是完全無(wú)鎖的設(shè)計(jì)，有兩種實(shí)現(xiàn)方式：
- Per-cpu data，顧名思義，每個(gè)核或者線程都有自己私有的數(shù)據(jù)結(jié)構(gòu)(這里的私有和thread local data是有區(qū)別的，這里的私有是邏輯上私有，并不意味著別的線程無(wú)法訪問(wèn)這些數(shù)據(jù);而thread local data是線程私有的數(shù)據(jù)結(jié)構(gòu)，別的線程是無(wú)法訪問(wèn)的。當(dāng)然，不管是邏輯上私有，還是物理上私有，把共享數(shù)據(jù)轉(zhuǎn)化成線程私有數(shù)據(jù)，就可以避免鎖，避免競(jìng)爭(zhēng))。全局變量是共享的，而局部變量是私有的，所以多使用局部變量，同樣可以達(dá)到無(wú)鎖的目的。
- CAS based，CAS是compare and swap，這是一個(gè)原子操作(spinlock的實(shí)現(xiàn)同樣需要compare and swap，但區(qū)別是spinlock只有兩個(gè)狀態(tài)LOCKED和UNLOCKED，而CAS的變量可以有多個(gè)狀態(tài));其次，CAS的實(shí)現(xiàn)必須由硬件來(lái)保障(原子操作)，CAS一次可以操作32 bits，也有MCAS，一次可以 比較修改一塊內(nèi)存?；贑AS實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)沒(méi)有一個(gè)統(tǒng)一，一致的實(shí)現(xiàn)方法，所以有時(shí)不如lock based的算法那么簡(jiǎn)單，直接，針對(duì)不同的數(shù)據(jù)結(jié)構(gòu)，有不同的CAS實(shí)現(xiàn)方法，讀者可以自己搜索。
lock-less的目的是減少鎖的爭(zhēng)用(contention)，而不是減少鎖。這個(gè)和鎖的粒度(granularity)相關(guān)，鎖的粒度越小，等待的時(shí)間就越短，并發(fā)的時(shí)間就越長(zhǎng)。
鎖的爭(zhēng)用，需要考慮不同線程在獲取鎖后，會(huì)執(zhí)行哪些不同的動(dòng)作。以session pool的分配釋放為例：假設(shè)多個(gè)線程都會(huì)訪問(wèn)同一個(gè)session pool，分配或者釋放session。session pool是個(gè)tailq，分配在head上進(jìn)行;而釋放在tail上進(jìn)行。
如果多個(gè)線程同時(shí)訪問(wèn)session pool，需要一個(gè)spinlock來(lái)保護(hù)這個(gè)session pool。那么分配和釋放兩個(gè)不同的動(dòng)作，相互之間就會(huì)有爭(zhēng)用，而且多個(gè)線程上的分配，或者釋放本身也會(huì)有爭(zhēng)用。
現(xiàn)在我們可以考慮分配用一個(gè)鎖，釋放用一個(gè)鎖，生成一個(gè)雙端隊(duì)列，這樣可以減少分配和釋放之間的爭(zhēng)用。
http://www.parallellabs.com/2010/10/25/practical-concurrent-queue-algorithm/ (參考這篇文章)。
也可以考慮用兩個(gè)pool，分配一個(gè)pool，釋放一個(gè)pool，在分配pool用完之后，交換兩個(gè)pool的指針(這時(shí)要考慮兩個(gè)pool都是空的情況，這里只是減少了分配和釋放的爭(zhēng)用，但不能完全消除這種爭(zhēng)用)。
不管是lock-based還是CAS-based (lock-free)的數(shù)據(jù)結(jié)構(gòu)，都需要一個(gè)狀態(tài)機(jī)。不同狀態(tài)下，做不同的事，而增加鎖的粒度，也就是增加了狀態(tài)機(jī)的數(shù)量(不是狀態(tài)的數(shù)量)，減小狀態(tài)保護(hù)的范圍。這個(gè)需要在實(shí)踐中體會(huì)。
【編輯推薦】
