Should I be using STL containers for allocation...?

[neziggy]

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.

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.

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.

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...
};