CppExplore

作者：CppExplore 地址：http://www.shnenglu.com/CppExplore/
2、定長內存池。典型的實現有LOKI、BOOST。特點是為不同類型的數據結構分別創建內存池，需要內存的時候從相應的內存池中申請內存，優點是可以在使用完畢立即把內存歸還池中，可以更為細粒度的控制內存塊。
    與變長的相比，這種類型的內存池更加通用，另一方面對于大量不同的數據類型環境中，會浪費不少內存。但一般系統主要的數據結構都不會很多，并且都是重復申請釋放使用，這種情況下，定長內存池的這點小缺點可以忽略了。
(1)Loki::SmallObject。Andrei Alexandrescu的《Modern C++ Design》第四章節已經進行了詳細的描述，盡管和當前的loki版本實現有出入，還是了解Loki::SmallObject的最佳文字講解，結合最新的loki源碼，足夠了。這里我再羅唆一下。先舉例看下使用：

#include "loki/SmallObj.h"
class Small:public  Loki::SmallObject<>//繼承SmallObject即可，所有都使用默認策略
{
public:
 Small(int data):data_(data){}
private:
 int data_;
};
int main()
{
 Small *obj=new Small(8);
 delete obj;
}

使用valgrind執行可以證實new一個obj和多new幾次，申請的內存都是4192。可以看出loki在使用層面非常簡單。
    loki的內存池分4層,從低向上依次是chunk、FixedAllocator、SmallObjAllocator、SmallObject。
1）chunk：每個chunk管理一定數量（最大255，char型保存）的block，每個chunk中block的申請和釋放，時間復雜度都是o(1)，非常快，實現算法非常精巧，boost::pool中也是采用的相同算法。
    這里簡單說下這個算法：首次申請一塊連續內存，pdata_指向該內存基址，依據block大小，劃分成多個連續的block，每個block開頭的第一個字節保存該block的順序號，第一個是1，第二個是2，依次類推。另有一字節變量firstAvailableBlock_存儲上次分配出的block序號，開始是0。
    分配block：返回pdata_ +firstAvailableBlock_*blocksize，同時firstAvailableBlock_賦值為該塊的序列號。
    回收block：block指針假設為pblock，該塊序列號賦值為firstAvailableBlock_，firstAvailableBlock_賦值為（pblock-pdata_ ）/blocksize即可。
2）FixedAllocator：chunk中的block上限是255，不具有通用性，因此封裝了一層，稱為FixedAllocator，它保存了一個vector<chunk>，消除了單個chunk中block數目的上限限制。
   FixedAllocator中的block申請：FixedAllocator中保存活動的chunk（上次有空閑空間的chunk），申請block的時候如果活動chunk有空閑快，直接申請，否則掃描vector，時間復雜度o(N),同時更新活動chunk。
   FixedAllocator中的回收block：簡單想，給定block回收到FixedAllocator，自然要掃描vector，以確認block屬于哪個chunk，以便chunk回收。實際實現的時候，Loki針對應用場景進行了優化，一般使用都是批量使用，回收一般和申請順序相同或者相反，因此FixedAllocator保存上次回收block的chunk指針，每次回收優先匹配這個chunk，匹配不上則以該chunk為中心，向兩側chunk順序檢測。
   FixedAllocator帶來的優點：上文提到的消除了block的上限限制。另一方面，可以以chunk為單位，把內存歸還給操作系統。實際實現中防止剛釋放的內存立即又被申請，是存在兩個空閑chunk的時候才回收一個。這個特點，這里暫時歸結為優點吧。實際使用中，回收多余內存個人認為是個缺點，意義并不是很大。
   FixedAllocator帶來的缺點：很明顯，就是申請回收block的時間復雜度。
3）SmallObjAllocator：截至到FixedAllocator層面blocksize都是定長。因此封裝一層適用于任意長度的內存申請。SmallObjAllocator保存了一個FixedAllocator的數組pool_，存儲擁有不同block長度的FixedAllocator。《Modern C++ Design》中描述該數組下標和存儲的FixedAllocator的block長度無直接關系，從SmallObjAllocator申請以及回收block的時候二分查找找到對應的FixedAllocator再調用相應FixedAllocator的申請或者回收。當前最新版本的loki，已經拋棄了這種做法。當前SmallObjAllocator的構造函數有3個參數：chunksize，maxblocksize，alignsize。數組元素個數取maxblocksize除以alignsize的向上取整。每個FixedAllocator中實際的blocksize是（下標＋1）*alignsize。
     SmallObjAllocator中block申請：依據block和alignsize的商直接取到數組pool_下標，使用相應的FixedAllocator申請。
     SmallObjAllocator中回收block：根據block和alignsize的商直接找到相應的FixedAllocator回收。
     優點：差異化各種長度的對象申請，增強了易用性。
     缺點：《Modern C++ Design》中描述增加掃描的時間復雜度，當前版本的loki浪費內存。這也是進一步封裝，屏蔽定長申請的細節，帶來的負面效應。
4）SmallObject。暴露給外部使用的一層。該層面秉承了《Modern C++ Design》開始引入的以設計策略類為最終目的，讓用戶在編譯期選擇設計策略，而不是提供框架限制用戶的設計。這也是引入模版的一個層面。當前版本SmallObject有6個模版參數，第一個是線程策略，緊接著的三個正好是SmallObjAllocator層面的三個構造參數，下面的一個生存期策略，最后的是鎖方式。
    這里說下SmallObjAllocator層面的三個默認參數值，分別是4096，256，4。意味著SmallObjAllocator層面有數組（256+4-1)/4=64個，數組存儲的FixedAllocator中的chunksize一般都是4096（當4096<=blocksize*255時候）字節（第一個chunk的申請推遲到首次使用的時候），各FixedAllocator中的chunk的blocksize依次是4、8......256，大于256字節的內存申請交給系統的malooc/new管理，數組中FixedAllocator中單個chunk中的blocknum依次是4096/4=824>255取255、255......4096/256=16。如果這不能滿足需求，請調用的時候顯式賦值。
    當前loki提供了三種線程策略：

SingleThreaded	單線程
ObjectLevelLockable	對象級別，一個對象一個鎖
ClassLevelLockable	類級別，一個類一個鎖，該類的所有對象共用該鎖

目前只提供了一種鎖機制：Mutex
它的基類SmallObjectBase復寫了new/delete操作子，因此直接繼承SmallObject就可以象普通的類一樣new/delete，并且從內存池分配內存。
    SmalObject中block申請和釋放都從一個全局的SmallObjAllocator單例進行。
評價：chunk層面限制了上限個數，導致了FixedAllocator層面出現，造成申請回收時間復雜度的提高，而以chunk為單位回收內存，在內存池的使用場景下意義并不是很大。SmallObjAllocator為了差異化變長內存的申請，對FixedAllocator進一步封裝，引入了內存的浪費，不如去掉這個層面，直接提供給用戶層面定長的接口。另一方面，loki已經進行了不少優化，盡可能讓block申請釋放的時間復雜度在絕大多數情況下都是O(1),而SmallObjAllocator中內存的浪費可以根據alignsize調整，即便是極端情況下，loki將chunk歸還給系統又被申請出來，根據chunk中block的最大值看，也比不使用內存池的情況動態申請釋放內存的次數減少了1/255。因此，loki是一個非常不錯的小巧的內存池。