I'm trying to write a custom allocator. After doing some searching, I decided to try implementing something I can just throw in just by overloading new/delete. I set up a singleton class that stores several STL maps. The keys are simply the size types of whatever is invoking the allocator.
1 2 3
|
std:::map<size_t, Pool> poolList; //contains linked list of pool heads
std::map<size_t, std::set<void*> > chunkUsed; //used pointers
std::map<size_t, std::queue<void*> > chunkFree; //available pointers
| |
The pool list is a linked list with each node containing the pointer to a pre-allocated void memory pool, and is already segmented by void pointers pushed into the free queue. Whenever
Allocate is called, it grabs a pointer from the chunkFree->second queue and inserts it into the chunkUsed->second set. Vice versa when using
Free.
Now my question is... Is this the best way to go about designing such a class? I'm a little concerned about performance seeing as how a lot of these operations will be performed on the fly. I ran a simple test to see how much it impacted performance: the difference between using this allocator and not at all was fairly large.
1 2 3 4 5 6 7 8 9
|
foo* array[1000];
for(int i = 0; i < 5000; i++) {
for(int j = 0; j < 1000; j++) {
array[j] = new foo(i, j);
}
for(int j = 0; j < 1000; j++) {
delete array[j];
}
}
| |
With the overloaded new and delete operators, I averaged about 3.2 seconds to termination. Without the overload, I averaged 1.4 seconds. The overhead from the allocator nearly doubled. The number of allocations, however, becomes severely reduced, and there is no risk of fragmentation or dangling pointers. That is a fairly steep tradeoff though.
Is there any more optimization/redesigning I can do or is using a singleton a bad idea? The idea was that I could just drop this into a project and it would work on its own, but if it has performance issues, I might as well just use a memory class for each object that plans to use it.
The entirety of the code with the test is located at
http://pastebin.com/ZGjs1hRL
Here is the class definition if you're lazy.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
|
class Memory {
public:
static Memory* Instance(); //singleton called with Memory::Instance()
void* Allocate(size_t); //returns a void pointer and creates a respective pool if none available
void Free(void*, size_t); //marks the void pointer as available
private:
Memory() {}
~Memory();
static Memory* pInstance;
struct Pool {
void* pool;
Pool* next;
};
std::map<size_t, Pool> poolList; //contains list of memory pool heads
std::map<size_t, Pool>::iterator poolListIter;
std::map<size_t, std::set<void*> > chunkUsed; //used pointers
std::map<size_t, std::queue<void*> > chunkFree; //available pointers
std::map<size_t, std::set<void*> >::iterator chunkUsedIter;
std::map<size_t, std::queue<void*> >::iterator chunkFreeIter;
void* ExpandPool(size_t, size_t);
void SegmentPool(void*, size_t, size_t);
void Cleanup();
void Cleanup(size_t); //clear specific pools...
};
| |