See what's going on with flipcode!




This section of the archives stores flipcode's complete Developer Toolbox collection, featuring a variety of mini-articles and source code contributions from our readers.

 

  Fast Allocation Pool
  Submitted by



Creating objects on the heap is a very slow and, for small objects, memory intensive operation. In 'Effective C++' Scott Meyers gives a rather specific example of using a pre-allocated pool of items to speed up memory allocation. The code below is a presented as a fast and general alternative that is trivial to incorporate into individual classes. Hopefully the comments explain how to use it pretty well. Feel free to suggest any improvements.

Currently browsing [fastpool.zip] (2,275 bytes) - [Pool.h] - (1,739 bytes)

#ifndef __POOL_H__
#define __POOL_H__

#include <cassert>

// CPool: // An optimised way of performing dynamic memory allocation, using a // preallocated pool which grows in large blocks as more objects are required. // To use it, add a static member variable to the class definition: // static CPool m_pool; // Which has to be initialised in the class's .cpp file as: // CPool CItem::m_pool(1000, sizeof(CItem)); // Where 1000 is the initial number of items in the pool. // Then add overrides for the new and delete operator of your class: // static void* operator new(const size_t size) // { // return m_pool.New(size); // } // static void operator delete(void* pObject); // { // m_pool.Delete(pObject); // } // This class was originally implemented as a template but I decided that it // wasn't necessary since the new and delete operators always use void* anyway. class CPool { public: CPool(const WORD nPoolSize, const size_t nItemSize, const bool bGrow = true); ~CPool(); void* New(const size_t size); void Delete(void* pVoid); void Purge();

private: CPool(CPool* const pPrev);

// New allocation pools are created and inserted into a doubly-linked list. CPool* const m_pPrev; CPool* m_pNext;

const WORD m_nPoolSize; // Maximum number of items in the pool. const size_t m_nItemSize; // The size of the contained item. BYTE* m_pAvailable; // Next available item. BYTE* m_pLast; // End of the pool. WORD m_nTOS; // Top of the free stack. bool m_bGrow; // True if the pool is allowed to grow. BYTE* m_pPool; // The allocation pool of items. BYTE** m_pFreeStack; // The stack of deleted items. };

#endif

Currently browsing [fastpool.zip] (2,275 bytes) - [Pool.cpp] - (3,495 bytes)

#include "stdafx.h"
#include "Pool.h"

// Create a new pool by defining the number of items to preallocate, and the // size of each item. For situations where you do not want the allocation // pool increase in size, set bGrow to false. CPool::CPool(const WORD nPoolSize, const size_t nItemSize, const bool bGrow) : m_pPrev(0), m_pNext(0), m_nPoolSize(nPoolSize), m_nItemSize(nItemSize), m_nTOS(0), m_bGrow(bGrow) { m_pPool = reinterpret_cast<BYTE*>(::operator new(m_nItemSize * m_nPoolSize)); m_pFreeStack = new BYTE*[m_nPoolSize]; m_pAvailable = m_pPool; m_pLast = m_pPool + m_nItemSize * m_nPoolSize; }

// Add a new pool to the end of the linked list, this can only be called from // another CPool. CPool::CPool(CPool* const pPrev) : m_pPrev(pPrev), m_pNext(0), m_nPoolSize(pPrev->m_nPoolSize), m_nItemSize(pPrev->m_nItemSize), m_nTOS(0), m_bGrow(true) { m_pPool = reinterpret_cast<BYTE*>(::operator new(m_nItemSize * m_nPoolSize)); m_pFreeStack = new BYTE*[m_nPoolSize]; m_pAvailable = m_pPool; m_pLast = m_pPool + m_nItemSize * m_nPoolSize; }

CPool::~CPool() { delete m_pNext; delete m_pPool; delete [] m_pFreeStack; }

void* CPool::New(const size_t size) { // If the item being requested is not the right size then use the generalised // new operator. This will occur if the object is derived from the allocated // class. if (size != m_nItemSize) return ::operator new(size);

// If there are any holes in the free stack then fill them up. if (m_nTOS == 0) { // If there is any space left in this pool then use it, otherwise move // on to the next in the linked list. if (m_pAvailable < m_pLast) { BYTE* pReturn = m_pAvailable; m_pAvailable += m_nItemSize; return reinterpret_cast<void*>(pReturn); } else { // If there is another pool in the list then pass the request on to // it, otherwise try to create a new pool. if (m_pNext) { return m_pNext->New(size); } else { if (m_bGrow) { m_pNext = new CPool(this); if (m_pNext) return m_pNext->New(size); } // If we cannot allocate a new pool then return 0. return 0; } } } else return reinterpret_cast<void*>(m_pFreeStack[--m_nTOS]); }

void CPool::Delete(void* pVoid) { if (pVoid) { BYTE* pItem = reinterpret_cast<BYTE*>(pVoid);

// Check if the item being deleted is within this pool's memory range. if (pItem < m_pPool || pItem >= m_pLast) { // If there is another pool in the list then try to delete from it, // otherwise call the generalised delete operator. if (m_pNext) m_pNext->Delete(pItem); else ::operator delete(pVoid); } else { // Add a hole to the free stack. m_pFreeStack[m_nTOS++] = pItem;

// If this pool is empty and it is the last in the linked list // then delete it and set the previous pool to the last. if (m_pPrev && !m_pNext && static_cast<long>(m_nTOS * m_nItemSize) == m_pAvailable - m_pPool) { m_pPrev->m_pNext = 0; delete this; } } } }

// Reset all the pointers and indices, effectively deleting the allocated // items without actually calling their destructors. This function should // be used with extreme caution since all sorts of horrible things can result // from it's misuse. void CPool::Purge() { m_nTOS = 0; m_pAvailable = m_pPool; if (m_pNext) m_pNext->Purge(); }

The zip file viewer built into the Developer Toolbox made use of the zlib library, as well as the zlibdll source additions.

 

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.