最近這兩天研究了一下SGI STL中的內存池, 網上對於這一塊的講解很多, 但是要麼講的不完整, 要麼講的不夠簡單(至少對於我這樣的初學者來講是這樣的...), 所以接下來我將把我對於對於SGI STL的理解寫下來, 方便以後查閱同時也希望能夠對像我一樣剛剛接觸C++的初學者提供一些幫助吧.
首先我們需要明確, 內存池的目的到底是什麼? 首先你要知道的是, 我們每次使用new T來初始化類型T的時候, 其實發生了兩步操作, 一個叫內存分配, 這一步使用的其實不是new而是operator new(也可以認為就是C語言中的malloc), 這一步是直接和操作系統打交道的, 操作系統可能需要經過相對繁瑣的過程才能將一塊指向空閒內存的指針返回給用戶, 所以這也是new比較耗時的一部分, 而第二步就是使用構造函數初始化該內存, 這是我們比較熟悉的. 既然內存分配耗時, 那我們很容易想到的就是一次性分配一大塊內存, 然後在用戶需要的時候再劃分其中一部分給用戶, 這樣的話, 一次分配, 多次使用, 自然而然提高了效率, 而用來管理這所謂的一大塊內存的數據結構, 也就是今天我們要說的內存池. 另外一個好處在於, 頻繁地使用new將導致系統內存空間碎片化嚴重, 容易導致的後果就是很難找到一塊連續的大塊內存, 空間利用率低.
那麼我們先來看看, 內存池的整體結構 :
該內存池可以認為由上面的一個指針數組和下面的自由鏈表兩部分組成, 指針數組中第一個指針指向的是存放內存大小為8bytes的節點串接而成的自由鏈表, 之後依次是內存而16bytes, 24bytes直到128bytes, 當然在圖中我只畫出了一個自由鏈表. 所以內存池的基本思路在於 :
1. 如果用戶分配的內存大於128bytes, 直接用malloc, 否則的話找出適合的自由鏈表, 從其上摘下一個節點將其頭指針返回給用戶.
2. 釋放過程則正好與分配相對應, 如果用戶分配的內存大於128bytes, 直接用free, 否則找出適當的自由鏈表, 將指針所指的該段內存重新連接到自由鏈表中(注意此時並不返回給操作系統, 因為之後還可以再重復利用).
這一部分的所對應的代碼如下圖 :
1 private:
2 static const int Align = 8;
3 static const int MaxBytes = 128;
4 static const int NumberOfFreeLists = MaxBytes / Align;
5 static const int NumberOfAddedNodesForEachTime = 20;
6
7 union node {
8 union node *next;
9 char client[1];
10 };
11
12 static obj *freeLists[NumberOfFreeLists];
為了便於理解, 我對於源代碼中的所以屬性名都做了相應的改動, 唯一可能存在疑問的是這個node為什麼可以用聯合體? 這裡我們需要搞清楚這麼幾點, 自由鏈表上保存的都是一個一個並未使用的節點, 此時我們為了將所有的node串接起來, 我們當然可以獨立分配空間來實現這一功能, 如下圖, 比較容易想到的做法可能是這樣, 用一個結構體來維護指向真正要分配給用戶的內存塊以及下一個結構體. 但是這樣做有兩個缺點 :
1.首先它的每一個node都需要額外多出一個指針的空間來保存真正要分配給用戶的內存塊的地址
2. 其次在將該內存塊分配出去之後, 還需要再處理掉該node對應的結構體.
在分析分配函數的代碼之前, 我們先來看看幾個輔助函數 :
1 private:
2 static size_t ROUND_UP(size_t size) {
3 return ((size + Align - 1) & ~(Align - 1));
4 }
5
6 static size_t FREELIST_INDEX(size_t size) {
7 return (size + Align - 1) / Align - 1;
8 }
這兩個函數作用很簡單, 第一個返回的是大於等於輸入值的8的倍數, 第二個返回的是可以容納輸入值的最小的自由鏈表.
接下來就是內存池對外的接口, allocate函數的實現代碼.
1 void* alloc::allocate(size_t size) {
2 if (size > MaxBytes) {
3 return malloc(size);
4 }
5
6 size_t index = FREELIST_INDEX(size);
7 node* theMostSuitableNode = freeLists[index];
8 if (theMostSuitableNode) {
9 freeLists[index] = theMostSuitableNode->next;
10 return theMostSuitableNode;
11 }
12 else {
13 return refill(ROUND_UP(size));
14 }
15 }
1. 正如我們前面所講的, 當用戶希望得到size大小的內存空間時候, 此時我們只需要找到能夠容納size的最小的自由鏈表, 因為自由鏈表中都是還未分配出去的空間, 如果自由鏈表中還存在節點的話, 直接將該節點分配出去即可, 也就是這裡的theMostSuitableNode不為空的情況, 但此時我們要將數組中指向該自由鏈表的指針指向下一個Node, 因為這個Node已經分配出去了.
2. 另一方面, 如果自由鏈表中並沒有可用的Node(這裡有兩種情況會導致沒有可用的Node, 第一種是曾經分配過, 但是用光了, 第二種是這是該內存池初始化以來第一次使用這個大小的自由鏈表, 所以還未分配過空間), 我們直接使用refill函數來填充自由鏈表, 之所以要用ROUND_UP使得它成為8的倍數, 是因為處於效率原因我們可能會一次性分配不止1個Node(這裡是20個), 所以這裡的空間必須按照Node的大小來分配.
所以我們順蔓摸瓜, 接著來看refill的實現代碼.
1 void* alloc::refill(size_t size) {
2 size_t num = NumberOfAddedNodesForEachTime;
3 char* block = blockAlloc(size, num);
4 node** currentFreeList = 0;
5 node *curNode = 0, *nextNode = 0;
6
7 if (num == 1) {
8 return block;
9 }
10 else {
11 currentFreeList = freeLists + FREELIST_INDEX(size);
12 *currentFreeList = nextNode = reinterpret_cast<node*>(block + size);
13 for (int i = 1;; ++i) {
14 curNode = nextNode;
15 nextNode = reinterpret_cast<node*>(reinterpret_cast<char*>(curNode) + size);
16 if (num - 1 == i) {
17 curNode->next = 0;
18 break;
19 }
20 else {
21 curNode->next = nextNode;
22 }
23 }
24 return block;
25 }
26 }
先解釋一下第二行的blockAlloc, 這個函數的作用是去內存池中尋找size * num大小的空間然後劃分給當前的自由鏈表(也就是currentFreeList), 因為一旦調用了refill說明該自由鏈表已經沒有了可分配的Node, 所以我們這裡考慮再分配的時候就直接分配了NumberOfAddedNodesForEachTime個(也就是20個). 但是要注意的話其實這裡num傳進去的是引用, 為什麼傳引用呢? 因為還有可能會出現內存池空間不夠的情況, 此時如果內存池夠1個Node但是不夠20個的話, 就會將num設置為1, 說明此時只分配了1個Node空間. 所以可以看到第26行的判斷中, 當num為1的時候, 直接將block返回給用戶即可. 如果不是1的話, 再返回之前要先將剩下個節點串接在自由鏈表上. 這也就是那個for循環的作用.
當然在接觸到blockAlloc之前, 我們先來看內存池的另外另個熟悉.
1 static char *startOfPool, *endOfPool;
這兩個變量分別指向內存池所分配的空間中的起點和終點, 之前說道自由鏈表裡面如果沒有node了就到內存池中取, 其實就是從startOfPool開始的位置劃出所需要的空間.
最後直接和內存池接觸的當然就是blockAlloc了, 所以我們也來看一下這個函數.
1 char* alloc::blockAlloc(size_t size, size_t& num) {
2 char* re = 0;
3 size_t bytesNeeded = size * num;
4 size_t bytesLeft = endOfPool - startOfPool;
5
6 if (bytesLeft >= bytesNeeded) {
7 re = startOfPool;
8 startOfPool = startOfPool + bytesNeeded;
9 return re;
10 }
11 else if (bytesLeft > size) {
12 num = bytesLeft / size;
13 re = startOfPool;
14 startOfPool += num * size;
15 return re;
16 }
17 else {
18 //TODO
19 }
20 }
這裡本來有三種情況, 第一種是說如果空間足夠(足夠分配20個Node那麼大), 就直接分配, 然後把指向內存池中空間起始位置的startOfPool移到新的位置, 第二種是雖然不夠分配20個, 但是足夠分配一個, 此時使用相同的方式, 只不過需要對num進行改動(因為這裡num傳的是引用, 所以也沒什麼大問題), 最後一種情況是說連一個Node的內存都拿不出來, 這種情況需要再向系統申請內存, 我將在下面詳細說明. 這裡我們先來理一理, 目前的情況...
1. 使用allocate向內存池請求size大小的內存空間.
2. allocate根據size找到最適合的自由鏈表.
a. 如果鏈表不為空, 返回第一個node, 鏈表頭改為第二個node.
b. 如果鏈表為空, 使用blockAlloc請求分配node.
x. 如果內存池中有大於一個node的空間, 分配竟可能多的node(但是最多20個), 將一個node返回, 其他的node添加到鏈表中.
y. 如果內存池只有一個node的空間, 直接返回給用戶.
z. 若果如果連一個node都沒有, 再次向操作系統請求分配內存(這就是上面代碼中的TODO部分).
然後我們還能發現內存池的幾個特點 :
1. 剛開始初始化內存池的時候, 其實內存池中並沒有內存, 同時所有的自由鏈表都為空鏈表.
2. 只有用戶第一次向內存池請求內存時, 內存池會依次執行上述過程的 1->2->b->z來完成內存池以及鏈表的首次填充, 而此時, 其他未使用鏈表仍然是空的.
有了這個整體的了解之後, 我們現在就來看一下, 內存池是如何向操作系統申請內存的 :
1 char* alloc::blockAlloc(size_t size, size_t& num) {
2 char* re = 0;
3 size_t bytesNeeded = size * num;
4 size_t bytesLeft = endOfPool - startOfPool;
5
6 if (bytesLeft >= bytesNeeded) {
7 re = startOfPool;
8 startOfPool = startOfPool + bytesNeeded;
9 return re;
10 }
11 else if (bytesLeft > size) {
12 num = bytesLeft / size;
13 re = startOfPool;
14 startOfPool += num * size;
15 return re;
16 }
17 else {
18 // I am not sure why add ROUND_UP(poolSize >> 4)
19 size_t bytesToGet = 2 * bytesNeeded + ROUND_UP(poolSize >> 4);
20 if (bytesLeft > 0) {
21 node** theMostSuitableList = freeLists + FREELIST_INDEX(bytesLeft);
22 (reinterpret_cast<node*>(startOfPool))->next = *theMostSuitableList;
23 *theMostSuitableList = reinterpret_cast<node*>(startOfPool);
24 }
25
26 startOfPool = (char*)malloc(bytesToGet);
27 if (!startOfPool) {
28 node** currentFreeList = 0;
29 node* listHeadNode = 0;
30 for (int i = size + Align; i <= MaxBytes; i += Align) {
31 currentFreeList = freeLists + FREELIST_INDEX(i);
32 listHeadNode = *currentFreeList;
33 if (listHeadNode) {
34 *currentFreeList = listHeadNode->next;
35 startOfPool = reinterpret_cast<char*>(listHeadNode);
36 endOfPool = reinterpret_cast<char*>(listHeadNode + i);
37 return blockAlloc(size, num);
38 }
39 }
40 //if code can run into this place, it means we can no longer get any memeory, so the best way is to throw exception...
41 exit(3);
42 }
43 else {
44 poolSize += bytesToGet;
45 endOfPool = startOfPool + bytesToGet;
46 return blockAlloc(size, num);
47 }
48 }
49 }
你會發現空間不足的時候, 首先計算了所需要的內存就是這個bytesToGet, 我在代碼中也提到了我也不太清楚後面為什麼要加上一個round_up(...), 然後是把當前剩余的內存(如果有剩余的話)分配給合適的節點, 因為每次分配內存都是8的倍數, 所以只要有剩余, 也肯定是8把的倍數, 所以一定能找到合適的節點. 接著就開始分配內存, 如果分配內存失敗的話, 那麼從size + Align開始(其實源代碼好像是從size開始, 但是我感覺此時存有size大小node的自由鏈表顯然是空的, 不然也不會調用這個函數, 所以就直接size + align 開始了), 如果能從那些位置挪出一個node的話(顯然挪出來的node要更大), 那麼就可以完成分配了, 如果遍歷了所有比size大的節點都尋找不到這樣一塊node的話, 正如我代碼中所說的, 運行到那個位置就應該拋異常了. 另外如果分配成功, 更新相應的變量之後, 再次調用該函數進行分配, 此時內存池中有足夠的內存分配給自由鏈表.
早這裡關於內存的分配的全過程就講完了, 下面是內存的釋放 :
1 void alloc::deallocate(void* ptr, size_t size) {
2 if (size > MaxBytes) {
3 free(ptr);
4 }
5 else {
6 size_t index = FREELIST_INDEX(size);
7 static_cast<node*>(ptr)->next = freeLists[index];
8 freeLists[index] = static_cast<node*>(ptr);
9 }
10 }
內存的釋放很簡單, 如果大於128bytes的, 直接釋放(因為也是直接分配過來的), 否則把它掛到相應的鏈表中, 留待之後使用.
到這裡, 內存池的實現就算全部講完了, 但是在真正將它投入到stl的實際使用中之前, 還要進行一層封裝.
public:
typedef T value_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
public:
static T *allocate();
static T *allocate(size_t n);
static void deallocate(T *ptr);
static void deallocate(T *ptr, size_t n);
static void construct(T *ptr);
static void construct(T *ptr, const T& value);
static void destroy(T *ptr);
static void destroy(T *first, T *last);
};
template<class T>
T *allocator<T>::allocate(){
return static_cast<T *>(alloc::allocate(sizeof(T)));
}
template<class T>
T *allocator<T>::allocate(size_t n){
if (n == 0) return 0;
return static_cast<T *>(alloc::allocate(sizeof(T) * n));
}
template<class T>
void allocator<T>::deallocate(T *ptr){
alloc::deallocate(static_cast<void *>(ptr), sizeof(T));
}
template<class T>
void allocator<T>::deallocate(T *ptr, size_t n){
if (n == 0) return;
alloc::deallocate(static_cast<void *>(ptr), sizeof(T)* n);
}
template<class T>
void allocator<T>::construct(T *ptr){
new(ptr)T();
}
template<class T>
void allocator<T>::construct(T *ptr, const T& value){
new(ptr)T(value);
}
template<class T>
void allocator<T>::destroy(T *ptr){
ptr->~T();
}
template<class T>
void allocator<T>::destroy(T *first, T *last){
for (; first != last; ++first){
first->~T();
}
}
}
這也就是我們熟悉的標准庫中的allocator的接口...
所以最終內存池的思路其實是這樣的:
1. 使用allocate向內存池請求size大小的內存空間, 如果需要請求的內存大小大於128bytes, 直接使用malloc.
2. 如果需要的內存大小小於128bytes, allocate根據size找到最適合的自由鏈表.
a. 如果鏈表不為空, 返回第一個node, 鏈表頭改為第二個node.
b. 如果鏈表為空, 使用blockAlloc請求分配node.
x. 如果內存池中有大於一個node的空間, 分配竟可能多的node(但是最多20個), 將一個node返回, 其他的node添加到鏈表中.
y. 如果內存池只有一個node的空間, 直接返回給用戶.
z. 若果如果連一個node都沒有, 再次向操作系統請求分配內存.
①分配成功, 再次進行b過程
②分配失敗, 循環各個自由鏈表, 尋找空間
I. 找到空間, 再次進行過程b
II. 找不到空間, 拋出異常(代碼中並未給出, 只是給出了注釋)
3. 用戶調用deallocate釋放內存空間, 如果要求釋放的內存空間大於128bytes, 直接調用free.
4. 否則按照其大小找到合適的自由鏈表, 並將其插入.
特點其實是這樣的 :
1. 剛開始初始化內存池的時候, 其實內存池中並沒有內存, 同時所有的自由鏈表都為空鏈表.
2. 只有用戶第一次向內存池請求內存時, 內存池會依次執行上述過程的 1->2->b->z來完成內存池以及鏈表的首次填充, 而此時, 其他未使用鏈表仍然是空的.
3. 所有已經分配的內存在內存池中沒有任何記錄, 釋放與否完全靠程序員自覺.
4. 釋放內存時, 如果大於128bytes, 則直接free, 否則加入相應的自由鏈表中而不是直接返還給操作系統.
以上是我對於sgi stl內存池的理解, 如果有任何不對的地方, 歡迎指出, 謝謝...
