Blog

2016-05-29 13:40:23

Memory Pool

Here is a peice of code I wrote a while ago as part of a question for a job interview (3d graphics coding role iirc). The challenge was to write a simple pool allocator that out-performed malloc/free (new/delete). hopefully someone can get some use out of it.

Assumptions

Assumption made that contained object has a default public constructor and a public destructor.

Expected storage requirements

The pool will require sizeof(T) * N + 16 bytes storage space (assuming 4-byte alignment) where T is the contained type and N is the number of objects in the pool.

Trade-offs

The pool uses the memory of the contained objects to store the free list. This slightly reduces the amount of storage space required, but makes the code slightly more complex/involved.

Expected algorithmic complexity
Operation Complexity
Pool Creation O(n)
Pool Destruction O(1)
Object Creation O(1)
Object Destruction O(1)
Trade-offs made to reach algorithmic complexity targets

Upon destruction of an object, the pool does not check to see if the object is already in the free list. Thus if an object is deleted from the pool twice, undefined behavior will result. To rectify this, the free list could be iterated on object destruction to see if the object to be destroyed is already in the free list – this would increase the algorithmic complexity of object destruction to O(n).
Download

memoryPool.zip

Size: 2.96 KB, Date: 2016-05-29 14:09, MD5: 9fa4ec4ecb3d94c5e8b6132d81b41fc6

MemoryPool.h
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#pragma once

namespace util
{
    template<typename T> class MemoryPool
    {
    public:
        MemoryPool(unsigned int capacity) : m_size(0), m_freeHead(0),
            m_buffer(nullptr), m_full(false)
        {
            if(capacity == 0)
            {
                throw std::exception("invalid memory pool capacity specified.");
            }

            m_size = capacity;
            m_buffer = (T*)::operator new(sizeof(T) * m_size);

            for(unsigned int offset = 0; offset < m_size; ++offset)
            {   // set each free object to point to the next
                *(reinterpret_cast<unsigned int*>(&(m_buffer[offset]))) =
                    offset + 1;
            }
            // the last entry in the free-list points to itself
            *(reinterpret_cast<unsigned int*>(&(m_buffer[m_size - 1]))) =
                m_size - 1;
        }

        ~MemoryPool()
        {
            delete m_buffer;
        }

        T* Create()
        {
            if(m_full == true)
            {
                return nullptr;
            }

            T* freeObject = &m_buffer[m_freeHead];
            unsigned int newHead =
                *(reinterpret_cast<unsigned int*>(&(m_buffer[m_freeHead])));
            // if the next free-list object is this object, the free-list has
            // been exhausted and the pool is full
            if(newHead == m_freeHead)
            {
                m_full = true;
            }

            m_freeHead = newHead;

            freeObject = new(freeObject) T();
            return freeObject;
        }

        bool Destroy(T* object)
        {
            unsigned int objectOffset = (object - &m_buffer[0]);

            if(objectOffset >= m_size || object < &m_buffer[0])
            {
                return false;
            }

            object->~T();

            if(m_full == true)
            {
                m_freeHead = objectOffset;
                m_full = false;
            }

            *(reinterpret_cast<unsigned int*>(&(m_buffer[objectOffset]))) =
                m_freeHead;

            m_freeHead = objectOffset;
            return true;
        }
    private:
        unsigned int m_size;
        unsigned int m_freeHead;
        T* m_buffer;
        bool m_full;
    };    
}
MAIN.CPP
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include <vector>
#include <string>
#include <ctime>
#include <iostream>
#include <conio.h>
#include <assert.h>

#include "MemoryPool.h"

namespace test
{
    struct obj
    {
        obj() : i(1), f(2.0f), b(true)
        {}

        int i;
        float f;
        bool b;
    };

    template<typename T> class MemoryPoolAllocator
    {
    public:
        MemoryPoolAllocator(unsigned int objectCount) :
          m_memoryPool(objectCount), m_objectCount(objectCount)
          {}

          T* Create()
          {
              return m_memoryPool.Create();
          }

          bool Destroy(T* objectPtr)
          {
              return m_memoryPool.Destroy(objectPtr);
          }

          std::string Name()
          {
              return "memory pool";
          }

          unsigned int Size()
          {
              return m_objectCount;
          }
    private:
        util::MemoryPool<T> m_memoryPool;
        unsigned int m_objectCount;
    };

    template<typename T> class DefaultAllocator
    {
    public:
        DefaultAllocator(unsigned int objectCount) :
          m_objectCount(objectCount)
          {}

          T* Create()
          {
              return new T();
          }

          bool Destroy(T* objectPtr)
          {
              delete objectPtr;
              return true;
          }

          std::string Name()
          {
              return "default allocator";
          }

          unsigned int Size()
          {
              return m_objectCount;
          }
    private:
        unsigned int m_objectCount;
    };

    template<typename T> void TimeAllocator(T& allocator)
    {
        std::time_t timeVal = std::time(nullptr);
        std::vector<obj*> objects;
        const unsigned int objectCount = allocator.Size();

        std::cout << allocator.Name() << " test started - creating " << objectCount <<
            " objects: " << std::asctime(std::localtime(&timeVal));
        clock_t createStarted = clock();

        for(unsigned int i = objectCount; i-- > 0;)
        {
            obj* object = allocator.Create();
            objects.push_back(object);
            assert(object != nullptr);
        }

        clock_t createStopped = clock();
        std::cout << allocator.Name() << " test stopped - creating " << objectCount <<
            " objects: " << std::asctime(std::localtime(&timeVal));
        float createDuration = 1000.0f * (((float)createStopped - createStarted) / CLOCKS_PER_SEC);
        std::cout << "duration: " << createDuration << "ms" << std::endl;

        std::cout << allocator.Name() << " test started - destroying " << objectCount <<
            " objects: " << std::asctime(std::localtime(&timeVal));
        clock_t destroyStarted = clock();

        for(unsigned int i = 0; i < objectCount; ++i)
        {
            obj* objectPtr = objects[i];
            bool result = allocator.Destroy(objectPtr);
            assert(result == true);
        }

        clock_t destroyStopped = clock();
        std::cout << allocator.Name() << " test stopped - destroying " << objectCount <<
            " objects: " << std::asctime(std::localtime(&timeVal));
        float destroyDuration = 1000.0f * (((float)destroyStopped - destroyStarted) / CLOCKS_PER_SEC);
        std::cout << "duration: " << destroyDuration << "ms" << std::endl;
    }

    void TimeTest()
    {
        const unsigned int objectCount = 1024 * 256;

        MemoryPoolAllocator<obj> memoryPoolAllocator(objectCount);
        TimeAllocator(memoryPoolAllocator);

        DefaultAllocator<obj> defaultAllocator(objectCount);
        TimeAllocator(defaultAllocator);
    }

    void OverCapacityTest()
    {
        const unsigned int objectCount = 3;
        util::MemoryPool<obj> memoryPool(objectCount);
        std::vector<obj*> objects;

        for(int i = objectCount; i-- > 0;)
        {
            objects.push_back(memoryPool.Create());
        }
        // try to create from full pool
        obj* createFailed = memoryPool.Create();
        assert(createFailed == nullptr);
    }

    void DeleteExternalObjectTest()
    {
        const unsigned int objectCount = 3;
        util::MemoryPool<obj> memoryPool(objectCount);
        std::vector<obj*> objects;

        for(int i = objectCount; i-- > 0;)
        {
            objects.push_back(memoryPool.Create());
        }
        // try to destroy object not belonging to pool
        obj* externalObject = new obj();
        bool destroyFailed = memoryPool.Destroy(externalObject);
        delete externalObject;
        assert(destroyFailed == false);

        for(int i = 0; i < objectCount; ++i)
        {
            obj* objectPtr = objects[i];
            memoryPool.Destroy(objectPtr);
        }
    }
}

int main(int argc, char* argv[])
{
    using namespace test;

    TimeTest();
    OverCapacityTest();
    DeleteExternalObjectTest();

    _getch();
    return 0;
}
Last Modified: 2017-02-15 18:22:59