C++

Forum

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

neziggy (5)
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...
};
Topic archived. No new replies allowed.