转自CSDN
好像boost库里面有这个专门用来分配小对象的类，不过貌似那个在初始化的时候特别慢。因为它会把一整块内存首先作切割成一个个小对象，然后用链表连起来成为一个free list，而这个事情就是在初始化的时候做，所以会很慢。
我的这个不会一开始就作切割，而是边分配边切割，貌似效率也没差多少。简单测试过一下，在连续访问的情况下（见main函数），第一次批量分配的时候（分配+切割），只比后来慢了一点点。。。当然，比传统的new/delete是要快很多。
不过遇到一个比较bt的情况。就是测试100w和1000w次分配的结果问题。在100w的测试中，new/delete耗费的时间是俺的20-30倍，但是在1000w的测试中，貌似差距就只有10%，虽然我的还是要快一点，不过优势没那么明显了。
晚上回家想了一下性能的问题，觉得测试代码中的vector有可能影响了测试结果。所以从测试代码中去掉了vector（新代码见最后）。
改完以后，1000w次分配的测试中，new/delete所耗费的时间大概多出50%左右。
但是和100w次测试时的差距还是巨大的，所以该问题还是没有很好的解答。。继续思考……
算法如下，有兴趣的讨论一下：
#include "stdio.h"
#include "windows.h"
#include <vector>
using namespace std;
#define PAGE_SIZE 4096
#define HANDLE_HEAP_SIZE 4*1024*1024
#define POINTER_SIZE sizeof(void*)
#define STRICT_DEBUGGING
typedef struct _PointerPair
{
void* one;
void* two;
}PointerPair;
class HandleListHeap
{
friend void main();
public:
static HandleListHeap* create()
{
// reserve memory
BYTE* heap_mem = (BYTE*)VirtualAlloc(NULL, HANDLE_HEAP_SIZE, MEM_RESERVE, PAGE_READWRITE);
if(!heap_mem)
return NULL;
// commit 1 page initially
heap_mem = (BYTE*)VirtualAlloc(heap_mem, PAGE_SIZE, MEM_COMMIT, PAGE_READWRITE);
if(!heap_mem)
return NULL;
// set class member values
HandleListHeap* heap = (HandleListHeap*)heap_mem;
heap->addressStart = heap_mem;
heap->addressEnd = heap_mem + HANDLE_HEAP_SIZE;
heap->sizeReserved = HANDLE_HEAP_SIZE;
heap->sizeCommitted = PAGE_SIZE;
heap->totalCount = heap->freeCount = (HANDLE_HEAP_SIZE - sizeof(HandleListHeap)) / sizeof(PointerPair);
heap->nextHeap = NULL;
heap->freeList = (PointerPair*)(heap_mem + sizeof(HandleListHeap));
heap->freeList->one = heap_mem + PAGE_SIZE;
heap->freeList->two = NULL;
return heap;
}
PointerPair* getOne()
{
if(!freeCount) // there's no room for new handle node in this heap
{
if(!nextHeap) // if there's no next heap, create one
nextHeap =
if(!nextHeap) // if we cannot create a heap, the app is out of memory, that means CRASH...
return NULL;
return nextHeap->getOne();
}
try_alloc:
BYTE* ret = NULL;
if(freeList)
{
ret = (BYTE*)freeList;
BYTE* addStart = (BYTE*)freeList;
BYTE* addEnd = (BYTE*)freeList->one;
addStart += sizeof(PointerPair);
#ifdef STRICT_DEBUGGING
if(addStart > addEnd)
throw "Bad! really bad! There some fatal error when calculating addresses.";
#endif
if(addStart == addEnd)
freeList = (PointerPair*)freeList->two;
else
{
memcpy(addStart, freeList, sizeof(PointerPair));
freeList = (PointerPair*)addStart;
}
--freeCount;
return (PointerPair*)ret;
}
else
{
// commit more if there's no enough free section
BYTE* heap_mem = (BYTE*)VirtualAlloc(addressStart, sizeCommitted + PAGE_SIZE, MEM_COMMIT, PAGE_READWRITE);
if(!heap_mem)
return NULL;
freeList = (PointerPair*)(heap_mem + sizeCommitted);
freeList->one = (BYTE*)freeList + PAGE_SIZE;
freeList->two = NULL;
sizeCommitted += PAGE_SIZE;
goto try_alloc;
}
}
void saveOne(PointerPair* theOne)
{
if(!theOne)
return;
if((BYTE*)theOne<addressStart || (BYTE*)theOne>addressEnd)
{
// theOne does not belongs to this heap, try next heap
if(nextHeap)
{
nextHeap->saveOne(theOne);
return;
}
else
throw "Can't save this. how did you get it? it's not from us.";
}
int offset = (BYTE*)theOne - (addressStart + sizeof(HandleListHeap));
if(offset < 0)
return;
#ifdef STRICT_DEBUGGING
if(offset%sizeof(PointerPair))
throw "Bad address";
#endif
// so we can save it now
theOne->one = (BYTE*)theOne + sizeof(PointerPair);
theOne->two = freeList;
freeList = theOne;
++freeCount;
}
private:
// for memory management
BYTE* addressStart;
BYTE* addressEnd;
UINT sizeReserved;
UINT sizeCommitted;
// for counting
// memo: the counts are calculated based on total reserver memory range
// but the pages may not been committed yet
// check this before allocating
UINT freeCount;
UINT totalCount;
HandleListHeap* nextHeap;
// memo: a freeList indicates a free section that can be resued
// a freeList is stored in the beginning of a free section
// freeList.one indicates the end address of the free section
// freeList.two indicates the address of next free section
// the address of a freeList equals to the address of coresponding free section
PointerPair* freeList;
private:
HandleListHeap();
HandleListHeap(const HandleListHeap&);
const HandleListHeap& operator = (const HandleListHeap&);
};
void main()
{
HandleListHeap* heap =
vector<PointerPair*> ppv;
register int allocationCount = 1000000;
PointerPair* ppp = NULL;
printf("Testing using HandleListHeap:\n");
for(int j=0; j<10; j++)
{
printf("Test %d\n",j+1);
int nCount = GetTickCount();
printf("Allocating...\n");
for(int i=0; i<allocationCount; ++i)
{
ppp = heap->getOne();
ppv.push_back(ppp);
}
printf("Freeing...\n");
for(int i=0; i<allocationCount; ++i)
{
heap->saveOne(ppv.back());
ppv.pop_back();
}
nCount = GetTickCount()-nCount;
printf("Test %d ended. Time spent: %dms\n\n",j+1,nCount);
}
printf("Testing using traditional new/delete:\n");
for(int j=0; j<10; j++)
{
printf("Test %d\n",j+1);
int nCount = GetTickCount();
printf("Allocating...\n");
for(int i=0; i<allocationCount; ++i)
{
ppp = new PointerPair();
ppv.push_back(ppp);
}
printf("Freeing...\n");
for(int i=0; i<allocationCount; ++i)
{
delete ppv.back();
ppv.pop_back();
}
nCount = GetTickCount()-nCount;
printf("Test %d ended. Time spent: %dms\n\n",j+1,nCount);
}
int nHeapCount = 0;
while(heap)
{
++nHeapCount;
heap = heap->nextHeap;
}
printf("Total heap created: %d", nHeapCount);
getc(stdin);
}
修改后的测试代码：
void main()
{
HandleListHeap* heap =
register int allocationCount = 10000000;
PointerPair* ppp = NULL;
PointerPair* tmp = NULL;
printf("Testing using HandleListHeap:\n");
for(int j=0; j<10; j++)
{
printf("Test %d\n",j+1);
int nCount = GetTickCount();
printf("Allocating...\n");
for(int i=0; i<allocationCount; ++i)
{
tmp = heap->getOne();
tmp->two = ppp;
ppp = tmp;
}
printf("Freeing...\n");
while(ppp)
{
tmp = (PointerPair*)ppp->two;
heap->saveOne(ppp);
ppp = tmp;
}
nCount = GetTickCount()-nCount;
printf("Test %d ended. Time spent: %dms\n\n",j+1,nCount);
}
printf("Testing using traditional new/delete:\n");
ppp = NULL;
tmp = NULL;
for(int j=0; j<10; j++)
{
printf("Test %d\n",j+1);
int nCount = GetTickCount();
printf("Allocating...\n");
for(int i=0; i<allocationCount; ++i)
{
tmp = new PointerPair();
tmp->two = ppp;
ppp = tmp;
}
printf("Freeing...\n");
while(ppp)
{
tmp = (PointerPair*)ppp->two;
delete ppp;
ppp = tmp;
}
nCount = GetTickCount()-nCount;
printf("Test %d ended. Time spent: %dms\n\n",j+1,nCount);
}
int nHeapCount = 0;
while(heap)
{
++nHeapCount;
heap = heap->nextHeap;
}
printf("Total heap created: %d", nHeapCount);
getc(stdin);
}