MemoryPool的LockFree實現(xiàn)

softarts

http://blog.csdn.net/softarts/archive/2009/04/08/4056465.aspx


沒事寫了這篇文章，正好看到Intel在搞多核編程征文，就去參加了，麻煩看到的人給投個票
投票地址：http://intel.csdn.net/multicoreblog/show.aspx?page=1（倒數(shù)第4頁，謝謝支持）


MemoryPool的LockFree實現(xiàn)-2009/04/07



MemoryPool已經(jīng)是一個非常古老的話題了，關于此方面的文章比比皆是，在Addison-Wesley 1999年出版的<Efficient C++ Performance Programming Techniques > (下面簡稱Efficient文)中，兩位富有經(jīng)驗的作者Dov Bulka, David Mayhew 詳細講述了如何編寫一個Multi-Thread的MemoryPool；而JAVA hotspot VM，Share Source CLI源碼中也可見這方面的實現(xiàn)。就我看來，他們的實現(xiàn)都大同小異。本文首先簡單介紹Efficient文中Memory Pool的實現(xiàn)，然后在此基礎上研究如何使用Lock-Free的機制去進一步改善性能。





<1>Multi-Thread MemoryPool的實現(xiàn)



以Dov Bulka版本為例,首先簡單看看一個最基本的基于對象的MemoryPool實現(xiàn)：

MemoryPool的基本思想是將在delete 的對象的時候并不真正delete，而是歸還到Pool中，以某種數(shù)據(jù)形式管理起來，在下一次分配對象內存的時候，先到Pool中尋找，看看有沒有空余的內存，如果沒有，在調用OS的malloc來分配新的內存。



MemoryPool的聲明:



template < class T >

class MemoryPool {

public:

    MemoryPool (size_t size = EXPANSION_SIZE);

    ~MemoryPool ();



    // Allocate a T element from the free list.

    inline void* alloc (size_t size);



    // Return a T element to the free list.

    inline void free (void *someElement);

private:

    // next element on the free list.

    MemoryPool<T> *next;



    // If the freeList is empty, expand it by this amount.

enum { EXPANSION_SIZE = 32};



    // Add free elements to the free list

    void expandTheFreeList(int howMany = EXPANSION_SIZE);

};



看看幾個關鍵的函數(shù)

分配內存:



template < class T >

inline

void* MemoryPool < T > :: alloc (size_t)

{

    if (!next) {

        expandTheFreeList();

    }



    MemoryPool<T> *head = next;

    next = head->next;



    return head;

}



釋放內存，原理是next 指針指向當前Pool的可用對象內存鏈表的頭部，在釋放對象內存的時候，就更新鏈表頭部時期指向剛釋放的對象內存塊



template < class T >

inline

void MemoryPool < T > :: free (void *doomed)

{

    MemoryPool<T> *head = static_cast <MemoryPool<T> *> doomed;



    head->next = next;

    next  = head;

}





擴充內存池, 這個是把新分配的內存依次串接到next所在的linked list中

template < class T >

void MemoryPool < T > :: expandTheFreeList(int howMany)

{

    // We must allocate an object large enough to contain the

    // next pointer.

    size_t size = (sizeof(T) > sizeof(MemoryPool<T> *)) ?

        sizeof(T) : sizeof(MemoryPool<T> *);



    MemoryPool<T> *runner = static_cast <MemoryPool<T> *> new char [size];



    next =  runner;

    for (int i = 0; i < howMany ; i++) {

        runner->next =

            static_cast <MemoryPool<T> *> new char [size];

        runner = runner->next;

    }

    runner->next = 0;

}







<2>MemoryPool的同步機制

從上面的代碼可見，分配和釋放都可能需要更新FreeList可用鏈表頭部，因此，多線程環(huán)境下需要使用鎖機制來保護對空閑鏈表頭部的修改，很多Linux/GNU 的Multi-Thread Memory Pool實現(xiàn)都會使用pthread_mutex_lock，例如SSCLI和JAVA hotspot VM中的實現(xiàn)。



除開pthread_mutex函數(shù)族外，還有pthread_spin系列也可用于線程同步。這兩者的主要區(qū)別是，如果沒有獲得鎖資源，pthread_mutex會使線程睡眠，而pthread_spin 顧名思義，則會反復嘗試直到取得鎖資源，這樣會使CPU空轉。



Efficient文中提到pthread_mutex是這樣使用的：

class ABCLock {// Abstract base class

public:

    virtual ~ABCLock() {}

    virtual void lock() = 0;

    virtual void unlock() = 0;

};

class MutexLock : public ABCLock {

public:

    MutexLock() {pthread_mutex_init(&lock, NULL);}

    ~MutexLock() {pthread_mutex_destroy(&lock);}



    inline void lock() {pthread_mutex_lock(&lock);}

    inline void unlock() {pthread_mutex_unlock(&lock);}

private:

    pthread_mutex_t lock;

};



在需要保護臨界信息的地方使用lock()函數(shù)

template <class M, class L>

inline

void* MTMemoryPool<M,L>::alloc (size_t size)

{

    void * mem;



    theLock.lock();

    mem = stPool.alloc(size);

    theLock.unlock();



    return mem;

}



pthread_spin的自旋鎖特性導致其比較適用一些輕量級，極短時間的多核cpu系統(tǒng)上的鎖保護，在單核cpu上，pthread_spin實質上會死循環(huán)直到線程時間片耗盡，從而性能比pthread_mutex大為縮水，一個測試中也證明了這一點。



測試環(huán)境，2個線程，1個用于operator new 分配內存(通過alloc調用)，另一個用operator delete 釋放內存(通過free調用)



表一，2 core 的測試結果：



environment
Intel Core 2 Duo CPU     E6850  @ 3.00GHz

average time
MutexLock
SpinLock
  
  

Lock()
0.00045
0.00024
  
  

Unlock()
0.000185
0.00009919
  
  

Alloc()
0.000857
0.0005728
  
  

Free()
0.0007549
0.0005512
  
  






表二，在single core上，Spinlock 的性能降低。

Environment
nosmp maxcpus=0 Intel Core 2 Duo CPU     E6850  @ 3.00GHz

Average time
MutexLock
SpinLock
  
  

Lock()
0.0005167
0.0014
  
  

Unlock()
0.000312
0.000246
  
  

Alloc()
0.001176
0.002443
  
  

Free()
0.001506
0.00396
  
  








從表一中可以看到，Lock ( pthread_mutex_lock或者pthread_spin_lock)占用了Alloc() 一半以上的cpu時間，Dov Bulka和David Mayhew也覺得pthread_mutex太過overweight了，他作了如下假設，并且給出了一個AIX上快速鎖的例子：“我們需要的是一個輕量級的鎖，假設正在加鎖的線程還沒有持有鎖，正在解鎖的線程恰巧好是起初加鎖的那個線程。”這樣的鎖在Linux上并沒有對應的實現(xiàn)，我們只能采用pthread_spin_trylock 加上 pthread_spin_lock來模仿這樣的過程。







<3>Lock-Free機制



pthread_spin 雖然足夠輕量，但仍然是一種鎖機制，線程的運行需要依賴于持有鎖的那個線程。從上面的測試結果可以看到，減去Lock/Unlock消耗的時間，Alloc()真正的cpu時間大約在0.00083-0.00045-0.000185=0.00022左右，有沒有一種同步方法可以使Alloc的消耗時間降低到這個數(shù)值？



在2004年Maged M. Michael那片開創(chuàng)性的文章“Scalable Lock-Free Dynamic Memory Allocation”，采用了Lock-Free機制的malloc實現(xiàn)擊敗了目前所有現(xiàn)存的malloc庫，包括ptmalloc3,hoard等，Lock-Free一時間成為主流的研究重點。我們也打算采用這種方法來提高Alloc()的性能，不過由于實現(xiàn)的復雜性，本文所要介紹的Lock-Free實現(xiàn)，主要是用于避免在讀寫空閑鏈表頭部的Lock/Unlock帶來的性能損失，MemoryPool采用的lib_malloc仍然是Linux/GNU環(huán)境下的基于Lock/Unlock的ptmalloc實現(xiàn)。盡管如此，采用Lock-Free的實現(xiàn)比mutex/spin lock有明顯的性能提高。



嚴格講,Lock-Free是一套以原子操作為基礎，采用事務->提交->提交失敗->重試這樣特定編程手法的機制，它使得正在訪問共享資源的線程不依賴于任何其它線程的調度和執(zhí)行，并且能夠在有限的步驟內完成。



Lock-Free的實現(xiàn)往往都是通過CAS-Compare And Swap原子操作完成，聲明如下：



CAS(addr,expval,newval) atomically do

if (*addr == expval) {

*addr = newval;

return true;

} else

return false;



Linux上一種典型的實現(xiàn)是：

inline int CAS(unsigned long *mem,unsigned long newval,unsigned long oldval)

{

  __typeof (*mem) ret;

  __asm __volatile ("lock; cmpxchgl %2, %1"

                     : "=a" (ret), "=m" (*mem)

                     : "r" (newval), "m" (*mem), "0" (oldval));

   return (int) ret;



}



以MemoryPool < T > :: alloc (size_t)為例：

….

//更新next指針的內容

do {

oldheader = next;

if (oldheader==NULL)

    expandTheFreeList();

else

    target=oldheader->next;



}

while (CAS(&next,target,oldheader)!=oldheader)



實際執(zhí)行中，如果next 的值為oldheader，那么就會更新next的值為target，并返回oldheader，這一過程是原子操作；如果在執(zhí)行CAS指令的時候，next的內容已經(jīng)發(fā)生變化，那么CAS的返回值就不會等于oldheader,while中的條件為false，程序會返回重新執(zhí)行oldheader = next，直到next 的值被成功更新。同時，expandTheFreeList也要作類似的Lock-Free修改，下面的例子中把原先expandTheFreeList的代碼放置到alloc中。



newbuf_head = NULL //note1

do

{

    oldheader =(MemoryPool*) next;            //note2

    if (!oldheader)

    {            

       if (!newbuf_head)

       {      

           size_t size = (m_sizeofClass > sizeof(MemoryPool *))?m_sizeofClass:sizeof(MemoryPool*);

            MemoryPool *runner = reinterpret_cast<MemoryPool*>(new char[size]);

           newbuf_head  = runner;

           for (int i = 0 ; i < EXPANSION_SIZE; i++)

            {            

              runner->next = reinterpret_cast<MemoryPool *>(new char [size]);

              runner =(MemoryPool*) runner->next;

            }

           runner->next = 0;

           newbuf_tail = runner;

       }

    }

    if (newbuf_head)  //note3

    {

        newbuf_tail->next = (MemoryPool*)next;

        target = newbuf_head;

    }

    else if (oldheader)

    {

        target = oldheader;//note4

}

//note5

}while ( CAS((unsigned long*)&next,/*m_freeheader,*/(unsigned long)target->next,(unsigned long)oldheader) !=(int) oldheader);



如果oldheader 為NULL,那么就會分配一段新的內存，頭部為newbuf_head，尾部為newbuf_tail，并且把原先的FreeList頭部掛接到新內存的尾部，以新內存的頭部作為新的FreeList的頭部去更新next的值。



如果分配內存后，CAS執(zhí)行失敗了，這沒關系，此時newbuf_head已被置值，因此并不會再次分配內存，程序仍然試圖執(zhí)行上一次執(zhí)行過的路徑。



考慮一種極端情況，起初next指向一個有效地址(oldheader也指向一個有效值)，因此程序跳過了分配新內存那段(斜體字)，不幸在執(zhí)行到note3處時，next卻由于另一個線程分配了內存的關系置為NULL，此時怎么辦？



答案，CAS操作時next的內容與oldheader不一致，因此CAS失敗，程序再次返回note2處執(zhí)行。



<4>Lock-Free中的ABA問題

承接上面的那一個極端問題，

線程A在執(zhí)行note2時的空閑鏈表狀態(tài)如下: A-B-C-D-E-NULL，在執(zhí)行到note5時，期間發(fā)生了如下事情：



線程B從FreeList中分配了一個A和B兩個內存塊，F(xiàn)reeList變?yōu)镃-D-E-NULL，但隨后線程B歸還了內存塊A，從而FreeList再次變?yōu)锳-C-D-E-NULL。



線程A在執(zhí)行到note5，進入CAS臨界操作時，next的內容仍然和note2時的一致，均指向A，但CAS的第二個關鍵參數(shù),target->next 的卻已不是B了！(在note4時target被設置為oldheader即A，從而target->next為B)，如果把next更新為B，那么就會造成程序錯誤。



這個就是Lock-Free與生俱來的ABA問題，CAS無法判斷目標內容從A變?yōu)锽，然后又變?yōu)锳這種情況，解決的辦法通常是使用一個額外的tag來記錄這種情況，并且使用CAS2，來同時檢查tag和目標內存兩個值又沒有發(fā)生變化，聲明如下：

bool CAS2 (volatile void * ptr, uint32_t old1, uint32_t old2, uint32_t new1, uint32_t new2)

{

    bool ret;

    __asm__ __volatile__ ("lock cmpxchg8b (%1) \n\t sete %%al"

        :   "=a"(ret)

        :   "D"(ptr), "a"(old1), "d"(old2), "b"(new1), "c"(new2)

        :   "memory";

    return ret;

}

CAS2可以用來檢查一個64 bit長度的內存指并原子交換他們的內容。



在某些情況下也可以采用thread specified Pool這種方案，就是每個線程有其專用的內存池，不會出現(xiàn)兩個線程同時在一個Pool上分配內存的情況，這需要額外的空間在分配的對象中嵌入線程的信息。





<5>Lock-Free的性能

可見Lock-Free的實現(xiàn)并不算一件太新鮮復雜的事情，Windows平臺上早就有了InterlockedCompareExchange之類的函數(shù)，Windows中提供的Slist也是一個Lock-Free 的linked-list。那么在何種情況下使用Lock-Free能達到最理想的效果？



Lock-Free機制在single core上會取得明顯的性能優(yōu)勢。所有的CAS操作實質上在CPU微觀世界里是串行執(zhí)行的，由于沒有別的線程干擾，一個處于運行狀態(tài)的線程永遠不會發(fā)生CAS操作失敗。



2 cpu core的情況下,一個線程alloc對象另一個線程free對象內存，可能會導致一個線程里有少量的CAS失敗，但是與pthread_spin_lock機制相比，耗時仍然非常少。究其原因，pthread_spin_lock會受到鎖粒度的的影響，假如Alloc需要耗時0.00023秒的話，那么pthread_spin_lock就可能需要消耗同樣的時間。而CAS是一種盡力處理的機制，即使在某個線程里發(fā)生了一個CAS失敗，一方面程序會以一個很細的粒度馬上重試，另一方面也表明與此同時另一個線程成功執(zhí)行了一次CAS操作。



從下表看出，CAS的耗時僅僅是pthread_mutex_lock的1/10。而整個alloc的耗時比較，Lock-Free也只有pthread_mutex版本的1/4。



如果增加alloc/free的線程以及cpu 的數(shù)量，Lock-Free機制會由于CAS操作失敗而不斷重復執(zhí)行do {}while(CAS) 中的代碼，從而導致一定的性能下降。因此，應該盡量讓do{}中的代碼寫得簡短，以保證較高的CAS成功率，其次是針對特定場景開發(fā)Lock-Free應用，例如在多核程序中進行pipeline處理，在同一個地方分配內存，在同一個地方回收內存。





Environment
Intel Core 2 Duo CPU     E6850  @ 3.00GHz

average time
MutexLock
SpinLock
Lock-Free
  

Lock()
0.00045
0.00024
0.000059(CAS)
  

Unlock()
0.000185
0.00009919
0
  

Alloc()
0.000857
0.0005728
0.0002425
  

Free()
0.0007549
0.0005512
0.0002002
  








<6>參考資料



[1] Maged M. Michael, Scalable Lock-Free Dynamic Memory Allocation http://researchweb.watson.ibm.com/people/m/michael/pldi-2004.pdf



[2] Dov Bulka, David Mayhew, Efficient C++: Performance Programming Techniques



[3] 搜狗實驗室技術交流文檔 Vol4:2 C10K與高性能程序續(xù)篇