TBB: concurrent_queue 高性能的奧秘作者：
softarts11 (3 篇文章)日期： 八月 13, 2009 在 11:49 上午
在如今的多線程開(kāi)發(fā)的滾滾浪潮中，線程安全會(huì)是一個(gè)充滿(mǎn)正面色彩的廣告語(yǔ)，還是一個(gè)隱含性能低下令人不安的信息？眾所周知，STL庫(kù)所提供的容器均不能保證線程安全，所有的工作都要需要開(kāi)發(fā)者來(lái)承擔(dān)。最簡(jiǎn)單的實(shí)現(xiàn)線程安全的手段便是使用鎖來(lái)同步對(duì)容器的訪問(wèn)，只需要lock和unlock兩行語(yǔ)句，容器就變成線程安全了，很簡(jiǎn)單，不是嗎？不過(guò)，這時(shí)候"線程安全"就成了性能低下的同名詞，期望的并發(fā)操作成了對(duì)容器的串行訪問(wèn)，我們不僅僅需要安全，還需要高性能。
TBB::concurrent_queue令人驚異地同時(shí)做到了這兩點(diǎn)，在讓開(kāi)發(fā)者放心地得到線程安全的同時(shí)，還可以心安理得的享受高性能的并發(fā)訪問(wèn)。這其中會(huì)有什么奧秘？作為普通的開(kāi)發(fā)者，我們可以從中學(xué)到什么東西？
Herb Sutter在DDJ 一文中拋出并行編程的三個(gè)簡(jiǎn)單論點(diǎn)，一是分離任務(wù)，使用更細(xì)粒度的鎖或者無(wú)鎖編程；二是盡量通過(guò)并行任務(wù)使用CPU資源，以提高系統(tǒng)吞吐量及擴(kuò)展性；三是保證對(duì)共享資源訪問(wèn)的一致性。
傳統(tǒng)的STL:queue 加鎖的方案，Intel Thread Profilec測(cè)量，圖的上半部分 fully utilized 只有9%（綠色部分），下半部分有大段時(shí)間處于串行執(zhí)行狀態(tài)（黃色），并行運(yùn)算度很低
這三個(gè)論點(diǎn)各有側(cè)重，我們看看concurrent_queue是怎么做的。
所謂分解任務(wù)，以盡可能細(xì)的粒度執(zhí)行，這樣就可以讓每個(gè)任務(wù)運(yùn)行而不互相干擾。并行編程中有一個(gè)對(duì)應(yīng)的重要概念，就是盡量使用thread的private/local數(shù)據(jù)，例如ptmalloc中采用了好幾個(gè)private heap，以降低多個(gè)線程同時(shí)請(qǐng)求分配內(nèi)存，造成訪問(wèn)globalheap時(shí)的contend。
針對(duì)一個(gè)concurrent_queue，內(nèi)部預(yù)先分配了8個(gè)micro_queue，并保存在名為array數(shù)組中，然后通過(guò)concurrent_queue_rep::choose函數(shù)來(lái)選擇其中一個(gè)隊(duì)列，這樣做的好處是能把MultiThread對(duì)1個(gè)queue的訪問(wèn)平均分布到多個(gè)內(nèi)部的micro_queue上，從而盡可能避免沖突。
micro_queue& choose( ticket k ) {
// The formula here approximates LRU in a cache-oblivious way.
return array[index(k)];
}
static size_t index( ticket k ) {
return k*phi%n_queue;//phi=3,n_queue=8
}
具體選擇哪個(gè)micro_queue，取決于一個(gè)為ticket類(lèi)型的變量k,這個(gè)變量實(shí)質(zhì)上是push操作次數(shù)的計(jì)數(shù)。
例如
k=0, 那么選擇 array[0*3%8]=array[0]
k=1,array[1*3%8]=array[3]
...
k=7,array[5]
k=8,array[0] //又回到了與k=0時(shí)一樣的結(jié)果。
無(wú)鎖的push操作
即使能把queue分布到內(nèi)部多個(gè)micro_queue上，那還是不可避免的會(huì)有沖突存在。例如，有可能2個(gè)不同的thread都是在訪問(wèn)同一個(gè)micro_queue。由上面結(jié)果可以看出，假設(shè)thread A在進(jìn)行push操作時(shí)，k=0，那么使用的是array[0]；而threadB同時(shí)在進(jìn)行第8個(gè)push操作，k=8，使用的也是array[0]，這種情況下怎么辦？
concurrent_queue用這段代碼來(lái)解決共享資源的訪問(wèn)沖突：
void micro_queue::push( const void* item, ticket k, concurrent_queue_base& base ) {
...
push_finalizer finalizer( *this, k+concurrent_queue_rep::n_queue );
if( tail_counter!=k ) {
ExponentialBackoff backoff;
do {
backoff.pause();
// no memory. throws an exception
if( tail_counter&0x1 ) throw bad_last_alloc();
} while( tail_counter!=k ) ;
}
...
}
對(duì)于每一次push操作，micro_queue使用了一個(gè)tail_counter來(lái)作為阻塞標(biāo)記。例如，array[0]被threadA占用時(shí)，該標(biāo)記會(huì)阻止thread B更新array[0](此時(shí)tail_counter!=k)，程序會(huì)在do{}while循環(huán)里反復(fù)測(cè)試等式是否成立，不然去執(zhí)行backoff.pause()以進(jìn)入睡眠狀態(tài)。
MorganStanley的Petru marginean在DDJ上的文章上曾經(jīng)提出過(guò)幾種阻塞的同步方法，分別是NO_WAIT(循環(huán)查詢(xún)),SLEEP(睡眠),TIMED_WAIT(超時(shí)等待)以及LOCK_NO_WAIT(鎖)，TBB使用的這種類(lèi)似于TIMED_WAIT的方法，通過(guò)pause指令讓線程暫停一會(huì)后，再重試。從網(wǎng)上得到的資料，pause指令在這種spin_lock模式的阻塞中，可以提高25倍效率。
保證共享資源訪問(wèn)的一致性，及使用new placement 改善內(nèi)存分配的性能
通過(guò)以上兩點(diǎn)，TBB::concurrent_queue已經(jīng)基本解決并行處理數(shù)據(jù)的問(wèn)題，然而還有些細(xì)節(jié)可以提高性能。有關(guān)內(nèi)存的操作永遠(yuǎn)都是性能測(cè)試中的熱點(diǎn)(hotspot)，改善性能也可以從內(nèi)存管理上入手
例如，每次push操作都需要為插入的元素分配內(nèi)存，malloc是一個(gè)昂貴的操作，如果能夠預(yù)先分配好一大段連續(xù)內(nèi)存，或者是從內(nèi)存池取得一段內(nèi)存呢？
TBB中，首先分配一個(gè)可以容納多個(gè)對(duì)象的page，然后在具體發(fā)生push操作時(shí)，使用C++的new placement語(yǔ)法，再?gòu)囊逊峙涞膒age上取得一個(gè)對(duì)象大小的內(nèi)存。
/*overide*/ virtual page *allocate_page() {
size_t n = sizeof(page) + items_per_page*item_size;
page *p = reinterpret_cast(my_allocator.allocate( n ));
if( !p ) internal_throw_exception();
return p;
}
此外，concurrent_queue利用了TBB庫(kù)的成果:atomic來(lái)聲明一些原子變量，如tail_counter.
結(jié)論：
測(cè)試表明，并行度達(dá)到50%（圖上半部分的藍(lán)色柱），時(shí)間上也比STL:queue加鎖的版本快了2-3倍。
concurrent_queue是一個(gè)典型的高性能并行容器實(shí)現(xiàn)，相信concurrent_haspmap和其它的容器，內(nèi)存池及算法，都可以采用類(lèi)似的方法去提高性能。只不過(guò)，仍然有些對(duì)concurrent_queue不解的地方：
為什么不采用Lock-Free的算法直接實(shí)現(xiàn)一個(gè)micro_queue?而是仍然使用一種類(lèi)似spin_lock的做法去同步線程？
不過(guò)，目前的方案很有可能是Intel開(kāi)發(fā)人員的折中選擇，隊(duì)列負(fù)載均衡，再加上預(yù)分配內(nèi)存后，push入隊(duì)操作應(yīng)該很快，發(fā)生碰撞的機(jī)率并不大。畢竟Lock-Free還不夠足夠成熟。
關(guān)于作者:曾任職于Alcatel-Lucent,Nokia,從事高速數(shù)據(jù)處理，移動(dòng)網(wǎng)絡(luò)系統(tǒng)軟件開(kāi)發(fā)等。對(duì)Linux Kernel，多核編程饒有興趣。
分類(lèi)：
博客征文專(zhuān)欄如需了解英特爾軟件產(chǎn)品相關(guān)的性能和優(yōu)化選項(xiàng)，請(qǐng)參閱
優(yōu)化注意事項(xiàng).
評(píng)論 (3)
2009年08月21日 11:20
zxeoc 實(shí)際上就是用多個(gè)micro_queue代替原本的單個(gè)queue，是并行和串行的一個(gè)折中。
2009年08月24日 04:45
朱慧春 能支持intel的CPU嗎
2009年08月25日 07:36
flygun "STL庫(kù)" 不提供線程安全嗎？ stlport提供的兼容的SGI stl是線程安全的。
硬件非?？炝?，軟件的速度確實(shí)還有很大優(yōu)化空間。
