內存池的作用：
減少內存碎片，提高性能。
首先不得不提的是Win32和x64中對于指針的長度是不同的，
在Win32中一個指針占4字節，而在x64中一個指針占8字節。也正是不清楚這一點，當我在x64中將指針作為4字節修改造成其他數據異常。
首先我們先來定義三個宏
#define ALIGN sizeof(void*)
#define MAX_BYTES 128
#define MAX_COUNT (MAX_BYTES / ALIGN)
正如前面所說的，為了兼容Win32與x64應此我們將要申請的內存按void*的大小來對齊。正如前面所說的，我們認為小于128字節的內存為小內存，會產生內存碎片，應此在申請時應該勁量申請一塊較大的內存而將其中的一小塊分配給他。
然后讓我們來看一下內存池中的成員變量
struct obj
{
obj* next;
};
struct block
{
block* next;
void* data;
};
obj* chunk_list[MAX_COUNT];
size_t chunk_count;
block* free_list;
這里使用obj結構來存儲已釋放內存的列表，這樣做的好處是可以更節省內存。在Win32中使用這塊內存的前4字節來指向下一個節點，而在x64中使用這塊內存的前8字節來指向下一個節點。
chunk_list：保存通過deallocate或refill中釋放或是新申請的內存塊列表，deallocate和refill將會在下文中介紹。
chunk_count：內存塊列表中已有的內存塊數量。
free_list：保存了通過malloc申請內存塊的鏈表。
下面我們來看一下內存池的構造函數與析構函數
MemoryPool() : free_list(0), chunk_count(0)
{
for(int i = 0; i < MAX_COUNT; ++i) chunk_list[i] = 0;
}
~MemoryPool()
{
block* current = free_list;
while(current)
{
block* next = current->next;
free(current->data);
free(current);
current = next;
}
}
構造函數中初始化free_list和chunk_count為0，并初始化chunk_list為一個空列表。而在析構函數中我們必須釋放每一塊通過malloc申請的大內存塊。
接下來是內存的申請
template <typename T>
T* allocate(size_t n, void(*h)(size_t))
{
if(n == 0) return 0;
if(n > MAX_BYTES)
{
T* p = (T*)malloc(n);
while(p == 0)
{
h(n);
p = (T*)malloc(n);
}
return p;
}
const int i = INDEX(ROUND_UP(n));
obj* p = chunk_list[i];
if(p == 0)
{
return refill<T>(i, h);
}
chunk_list[i] = p->next;
return reinterpret_cast<T*>(p);
}
值得注意的是，在調用時必須傳入一個函數指針作為參數，當malloc申請內存失敗時會去調用這個函數來釋放出足夠多的內存空間。當要申請的內存大小超過128字節時，調用默認的malloc為其申請內存。否則先查找列表中是否還有足夠的空間分配給它，若已沒有足夠的空間分配給它，則調用refill申請一塊大內存。
然后是內存釋放函數deallocate
template <typename T>
void deallocate(T* p, size_t n)
{
if(p == 0) return;
if(n > MAX_BYTES)
{
free(p);
return;
}
const int i = INDEX(ROUND_UP(n));
reinterpret_cast<obj*>(p)->next = chunk_list[i];
chunk_list[i] = reinterpret_cast<obj*>(p);
}
值得注意的是在釋放時必須給出這塊內存塊的大小。若這塊內存大于128字節時，調用默認的free函數釋放掉這塊內存。否則將其加到對應的chunk_list列表內。
然后是調整內存塊大小函數reallocate
template <typename T>
T* reallocate(T* p, size_t old_size, size_t new_size, void(*h)(size_t))
{
if(old_size > MAX_BYTES && new_size > MAX_BYTES)
{
return realloc(p, new_size);
}
if(ROUND_UP(old_size) == ROUND_UP(new_size)) return p;
T* result = allocate<T>(new_size, h);
const size_t copy_size = new_size > old_size ? old_size : new_size;
memcpy(result, p, copy_size);
deallocate<T>(p, old_size);
return result;
}
參數中必須給出這塊內存的原始大小和要調整后的大小，同時也必須給出當內存不足時的釋放函數的指針。若舊內存塊和新內存塊的大小都大于128字節時，調用默認的realloc函數重新分配內存。否則先按調整后的大小申請一塊內存，并把原來的內容拷貝過來，最后釋放掉原來的內存塊。這里并不建議使用這個函數，而是手動的去重新申請內存并拷貝釋放。
然后來看4個非常簡單的計算函數
inline size_t ROUND_UP(size_t bytes)const
{
return (bytes + ALIGN - 1) & ~(ALIGN - 1);
}
inline size_t ROUND_DOWN(size_t bytes)const
{
return bytes & ~(ALIGN - 1);
}
inline int INDEX(size_t bytes)const
{
return (bytes + ALIGN - 1) / ALIGN - 1;
}
inline size_t obj_count(int i)const
{
size_t result = 0;
obj* current = chunk_list[i];
while(current)
{
++result;
current = current->next;
}
return result;
}
前3個用于內存對齊和計算索引，最后一個用于獲取一在空閑列表內一個內存塊的數量。
然后是refill函數，用于在沒有空閑內存塊時申請一塊大內存塊
template <typename T>
T* refill(int i, void(*h)(size_t))
{
const int count = 20;
const int preSize = (i + 1) * ALIGN;
char* p = (char*)malloc(preSize * count);
while(p == 0)
{
h(preSize * count);
p = (char*)malloc(preSize * count);
}
block* pBlock = (block*)malloc(sizeof(block));
while(pBlock == 0)
{
h(sizeof(block));
pBlock = (block*)malloc(sizeof(block));
}
pBlock->data = p;
pBlock->next = free_list;
free_list = pBlock;
obj* current = (obj*)(p + preSize);
for(int j = 0; j < count - 1; ++j)
{
current->next = chunk_list[i];
chunk_list[i] = current;
current = (obj*)((char*)current + preSize);
}
chunk_count += count - 1;
rebalance();
return reinterpret_cast<T*>(p);
}
首先申請一個大內存塊，然后將這塊申請到的內存塊放入free_list鏈表內，最后組織起chunk_list中對應內存卡塊的鏈表，然后重新調整chunk_list列表，最后將申請到的內存塊返回。
最后來看一下調整函數rebalance
void rebalance()
{
for(int i = MAX_COUNT - 1; i > 0; --i)
{
const size_t avge = chunk_count / MAX_COUNT;
size_t count = obj_count(i);
if(count > avge)
{
const int preSize = ROUND_DOWN((i + 1) * ALIGN / 2);
const int j = INDEX(preSize);
for(int k = count; k > avge; --k)
{
obj* chunk = chunk_list[i];
chunk_list[i] = chunk_list[i]->next;
if(i % 2 == 1)
{
chunk->next = (obj*)((char*)chunk + preSize);
chunk->next->next = chunk_list[j];
chunk_list[j] = chunk;
}
else
{
chunk->next = chunk_list[j];
chunk_list[j] = chunk;
obj* next = (obj*)((char*)chunk + preSize);
next->next = chunk_list[j + 1];
chunk_list[j + 1] = next;
}
++chunk_count;
}
}
}
}
這里從后至前查看對應內存塊空閑鏈表的長度，若超過平均數量，則將其切分為2塊較小的內存塊放入對應的鏈表內。這樣做的好處是可以形成一個金字塔形的分布狀況，既越小的內存塊大小擁有的節點數量越多，正如本文開頭所說，使用內存池是為了解決在申請小塊內存時造成的內存碎片。
至此，內存池的講解已完成，完整的代碼請到
http://qlanguage.codeplex.com下載
posted on 2012-07-14 18:40
lwch 閱讀(2445)
評論(1) 編輯 收藏 引用 所屬分類:
STL