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