Blog
View Blog Archive (All Entries) >>
Tag Cloud
still coming soon..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.
AssumptionsAssumption made that contained object has a default public constructor and a public destructor. Expected storage requirementsThe 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-offsThe 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
Trade-offs made to reach algorithmic complexity targetsUpon 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; } |