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.