Click here to Skip to main content
11,634,634 members (68,324 online)
Click here to Skip to main content

Tagged as

O(1) Object Pool in C++

, 21 Apr 2014 CPOL 39.3K 717 67
Rate this:
Please Sign up or sign in to vote.
A C++ memory/object pool that's always O(1) for allocations and deallocations.

Introduction

I started to write an article regarding Garbage Collection in C++ and one of my comparisons was that real garbage collected languages may be faster than C++ in some situations because they allocate memory in blocks, which makes the allocation of many small objects become extremely fast, and this doesn't happen in C++.

Well, actually we can do the same in C++ but it is not automatic, so it is up to us to use it. To do that we should use some kind of memory or object pooling.

I looked for some existing implementations and I actually didn't like them. Boost, for example, has a pool that's fast to allocate memory but that's slow to free memory if we want to control when we destroy each object. So, I decided to create my own implementation, which I am going to present here.

The Solution

This solution is made of a single template class, named ObjectPool. I can say that choosing between naming the class "object pool" and "memory pool" is a little problematic. As the solution doesn't keep a certain number of objects already initialized, we can say that it is only a memory pool, so the cost to invoke the constructor and the destructor of individual objects will continue to happen. Yet I didn't want to say it is a "memory pool", as users will request objects, not raw memory, from the pool. Maybe I should find another name that doesn't cause confusion but, for now, it is called ObjectPool.

The implementation is like this:

  • An initial amount of memory is allocated (by default, it is a block capable of holding 32 objects, aligned as a pointer [4-bytes for 32-bit computers and 8-bytes for 64-bit computers]) and there's a reference to a "first deleted" object set to NULL;
  • Each time a new object is requested the code first checks if there's a pointer for a first deleted object. If there is, then that's the address that will be used and the first pointer will point to the "next" free object (which is the content at that pointer location). If there's no deleted object that we can reuse, then we check if we still have place in our memory block. If not, a new block of memory is requested (which doubles in size, with an specific limit). In any case, we will call the constructor of the object at the address that we chose and then we will return it;
  • To delete an object, it is pretty simple. We invoke the destructor and then we will consider the object as a pointer. Such pointer will be set to point to the actual "first free" object then its address will be put as the first deleted item;
  • When we delete the pool itself, it will free the first block and, as each block frees the next one, it will end-up freeing all blocks.

So, we can summarize things like this:

  • All object allocations are O(1). Surely in some cases memory needs to be allocated, which can take some time, but the performance of such allocation is not directly affected by the number of already allocated items as we put a limit on how big the blocks can become;
  • All object destructions are O(1), as we call the destructor and simply "swap pointers";
  • It is not important how many objects we have deleted. The pool will keep all memory blocks allocated until the pool itself is deleted;
  • When we delete the pool, the memory blocks are free but the destructor of the inner items are not called, so it is up to us to delete each item before destroying the pool (if we need to call the object destructor at all).

And there are the alternative methods that actually don't initialize or destroy the objects. Those methods do all the work for "allocating" or "deallocating" an object from the pool but don't call the constructor or the destructor. This may be useful if we need to call a specific, non-default constructor or if we know that the object doesn't have a destructor (or for some reason we don't want to call it).

When is this pool useful?

  • When we have a "work" to do that allocates/deallocates many objects and we know that we can keep the memory allocated until the end of such work (most loops enter in this category);
  • When we know that we have a limited number of objects that will be in memory at the same time, yet we keep "allocating" and "deallocating" them.

Using the code

To use the code we must initialize the pool giving the initial capacity and the maximum size for the other blocks. If we don't give any parameter, the defaults of 32 (for the initial capacity) and 1 million (for the maximum block size) are used.

So, a line like the following will initialize our pool in the stack (or statically) using those defaults:

ObjectPool<Test> pool;

Then, to allocate an object we do:

Test *test = pool.New();

And to deallocate an object we do:

pool.Delete(test);

If we don't want to use the default constructor, we can do:

T *unitializedObject = pool.GetNextWithoutInitializing();

// And then we can call an appropriate constructor:
Test *test = new (uninitializedObject) Test(/*... parameters here...*/);

And if we don't want to allow the destructor to be called but we want to return the memory to the pool, we can use:

pool.DeleteWithoutDestroying(test);

Obviously, we should use the appropriate class instead of Test and the appropriate variable names instead of test.

The source code of the pool is this:

template<typename T>
class DefaultMemoryAllocator
{
public:
  static inline void *Allocate(size_t size)
  {
    return ::operator new(size, ::std::nothrow);
  }
  static inline void Deallocate(void *pointer, size_t size)
  {
    ::operator delete(pointer);
  }
};

template<typename T, class TMemoryAllocator=DefaultMemoryAllocator>
class ObjectPool
{
private:
  struct _Node
  {
    void *_memory;
    size_t _capacity;
    _Node *_nextNode;

    _Node(size_t capacity)
    {
      if (capacity < 1)
        throw std::invalid_argument("capacity must be at least 1.");

      _memory = TMemoryAllocator::Allocate(_itemSize * capacity);
      if (_memory == NULL)
        throw std::bad_alloc();

      _capacity = capacity;
      _nextNode = NULL;
    }
    ~_Node()
    {
      TMemoryAllocator::Deallocate(_memory, _itemSize * _capacity);
    }
  };

  void *_nodeMemory;
  T *_firstDeleted;
  size_t _countInNode;
  size_t _nodeCapacity;
  _Node _firstNode;
  _Node *_lastNode;
  size_t _maxBlockLength;

  static const size_t _itemSize;

  ObjectPool(const ObjectPool<T, TMemoryAllocator> &source);
  void operator = (const ObjectPool<T, TMemoryAllocator> &source);

  void _AllocateNewNode()
  {
    size_t size = _countInNode;
    if (size >= _maxBlockLength)
      size = _maxBlockLength;
    else
    {
      size *= 2;

      if (size < _countInNode)
        throw std::overflow_error("size became too big.");

      if (size >= _maxBlockLength)
        size = _maxBlockLength;
    }

    _Node *newNode = new _Node(size);
    _lastNode->_nextNode = newNode;
    _lastNode = newNode;
    _nodeMemory = newNode->_memory;
    _countInNode = 0;
    _nodeCapacity = size;
  }

public:
  explicit ObjectPool(size_t initialCapacity=32, size_t maxBlockLength=1000000):
    _firstDeleted(NULL),
    _countInNode(0),
    _nodeCapacity(initialCapacity),
    _firstNode(initialCapacity),
    _maxBlockLength(maxBlockLength)
  {
    if (maxBlockLength < 1)
      throw std::invalid_argument("maxBlockLength must be at least 1.");

    _nodeMemory = _firstNode._memory;
    _lastNode = &_firstNode;
  }
  ~ObjectPool()
  {
    _Node *node = _firstNode._nextNode;
    while(node)
    {
      _Node *nextNode = node->_nextNode;
      delete node;
      node = nextNode;
    }
  }

  T *New()
  {
    if (_firstDeleted)
    {
      T *result = _firstDeleted;
      _firstDeleted = *((T **)_firstDeleted);
      new(result) T();
      return result;
    }

    if (_countInNode >= _nodeCapacity)
      _AllocateNewNode();

    char *address = (char *)_nodeMemory;
    address += _countInNode * _itemSize;
    T *result = new(address) T();
    _countInNode++;
    return result;
  }

  // This method is useful if you want to call a non-default constructor.
  // It should be used like this:
  // new (pool.GetNextWithoutInitializing()) ObjectType(... parameters ...);
  T *GetNextWithoutInitializing()
  {
    if (_firstDeleted)
    {
      T *result = (T *)_firstDeleted;
      _firstDeleted = *((T **)_firstDeleted);
      return result;
    }

    if (_countInNode >= _nodeCapacity)
      _AllocateNewNode();

    char *address = (char *)_nodeMemory;
    address += _countInNode * _itemSize;
    _countInNode++;
    return (T *)address;
  }
  void Delete(T *content)
  {
    content->~T();

    *((T **)content) = _firstDeleted;
    _firstDeleted = content;
  }
  void DeleteWithoutDestroying(T *content)
  {
    *((T **)content) = _firstDeleted;
    _firstDeleted = content;
  }
};

template<typename>
const size_t ObjectPool<t,>::_itemSize = ((sizeof(T) + sizeof(void *)-1) / sizeof(void *)) * sizeof(void *);
</t,></typename>

Thread-safety

The presented code is not thread-safe but this actually makes it faster. So, if we use it in a static variable or to pass it to other threads, it is up to us to use some kind of locking.

Personally I think that we should not have a real static pool and, if needed, we should have a pool per thread. This will avoid the performance degradations caused by locking.

Sample

The sample is an application that keeps creating and deleting 100 objects 1 million times, then it shows how much time it takes to finish the job, using the pool and using normal new and delete calls.

Of course this is not a real situation, but it shows how fast the pool can be compared to normal new/delete calls. It is up to you to use it in better situations.

Version History

  • 12, April, 2014: Added a memory allocator parameter to the template, the default one uses the new/delete operators instead of malloc/free, declared the copy constructor/copy operator as private to avoid the default implementation, made the constructor explicit and changed the delete of the memory blocks to be in a while instead of being recursive to avoid excessive use of the stack;
  • 21, March, 2014: Corrected a bug (double allocation) in the constructor;
  • 19, March, 2014: Initial version.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Paulo Zemek
Engineer Microsoft Corporation
United States United States
I started to program computers when I was 11 years old, as a hobbist, programming in AMOS Basic and Blitz Basic for Amiga.
At 12 I had my first try with assembler, but it was too difficult at the time. Then, in the same year, I learned C and, after learning C, I was finally able to learn assembler (for Motorola 680x0).
Not sure, but probably between 12 and 13, I started to learn C++. I always programmed "in an object oriented way", but using function pointers instead of virtual methods.

At 15 I started to learn Pascal at school and to use Delphi. At 16 I started my first internship (using Delphi). At 18 I started to work professionally using C++ and since then I've developed my programming skills as a professional developer in C++ and C#, generally creating libraries that help other developers do they work easier, faster and with less errors.

Now I just started working as a Senior Software Engineer at Microsoft.

Want more info or simply want to contact me?
Take a look at: http://paulozemek.azurewebsites.net/
Or e-mail me at: paulozemek@outlook.com

Codeproject MVP 2012, 2015
Microsoft MVP 2013-2014

You may also be interested in...

Comments and Discussions

 
Questionthanks Pin
king46451848610-Oct-14 16:35
memberking46451848610-Oct-14 16:35 
AnswerRe: thanks Pin
Paulo Zemek10-Oct-14 16:54
professionalPaulo Zemek10-Oct-14 16:54 
Questionusing with std::list Pin
Amr010-Oct-14 10:01
memberAmr010-Oct-14 10:01 
AnswerRe: using with std::list Pin
Paulo Zemek10-Oct-14 15:10
professionalPaulo Zemek10-Oct-14 15:10 
QuestionMinor suggestions Pin
Chan Ka Ming21-Jul-14 19:26
memberChan Ka Ming21-Jul-14 19:26 
AnswerRe: Minor suggestions Pin
Paulo Zemek22-Jul-14 2:27
professionalPaulo Zemek22-Jul-14 2:27 
Questioni donot understand why _itemSize Pin
Member 1094125113-Jul-14 17:18
memberMember 1094125113-Jul-14 17:18 
AnswerRe: i donot understand why _itemSize Pin
Paulo Zemek14-Jul-14 2:18
professionalPaulo Zemek14-Jul-14 2:18 
GeneralRe: i donot understand why _itemSize Pin
Member 1094125114-Jul-14 18:22
memberMember 1094125114-Jul-14 18:22 
GeneralRe: i donot understand why _itemSize Pin
Paulo Zemek14-Jul-14 18:23
professionalPaulo Zemek14-Jul-14 18:23 
SuggestionReusing objects in pool Pin
tower1209-Jul-14 7:40
membertower1209-Jul-14 7:40 
GeneralRe: Reusing objects in pool Pin
Paulo Zemek9-Jul-14 7:52
professionalPaulo Zemek9-Jul-14 7:52 
GeneralRe: Reusing objects in pool Pin
tower1209-Jul-14 8:09
membertower1209-Jul-14 8:09 
GeneralRe: Reusing objects in pool Pin
Paulo Zemek9-Jul-14 8:29
professionalPaulo Zemek9-Jul-14 8:29 
GeneralRe: Reusing objects in pool Pin
tower1209-Jul-14 8:54
membertower1209-Jul-14 8:54 
Questionvery good! Pin
regainworld22-Apr-14 14:50
memberregainworld22-Apr-14 14:50 
AnswerRe: very good! Pin
Paulo Zemek22-Apr-14 14:59
professionalPaulo Zemek22-Apr-14 14:59 
GeneralRe: very good! Pin
regainworld22-Apr-14 17:08
memberregainworld22-Apr-14 17:08 
QuestionSMALL OBJECT ALLOCATORS Pin
geoyar22-Apr-14 10:54
membergeoyar22-Apr-14 10:54 
AnswerRe: SMALL OBJECT ALLOCATORS Pin
Paulo Zemek22-Apr-14 11:17
professionalPaulo Zemek22-Apr-14 11:17 
GeneralRe: SMALL OBJECT ALLOCATORS Pin
geoyar22-Apr-14 16:10
membergeoyar22-Apr-14 16:10 
GeneralRe: SMALL OBJECT ALLOCATORS Pin
Paulo Zemek22-Apr-14 16:15
professionalPaulo Zemek22-Apr-14 16:15 
QuestionA couple of things Pin
Florian Rappl31-Mar-14 13:14
mvpFlorian Rappl31-Mar-14 13:14 
AnswerRe: A couple of things Pin
Paulo Zemek31-Mar-14 13:28
professionalPaulo Zemek31-Mar-14 13:28 
GeneralRe: A couple of things Pin
Florian Rappl31-Mar-14 20:42
mvpFlorian Rappl31-Mar-14 20:42 
GeneralRe: A couple of things Pin
Paulo Zemek1-Apr-14 1:26
professionalPaulo Zemek1-Apr-14 1:26 
GeneralRe: A couple of things Pin
Florian Rappl1-Apr-14 2:23
mvpFlorian Rappl1-Apr-14 2:23 
GeneralRe: A couple of things Pin
Paulo Zemek1-Apr-14 2:40
professionalPaulo Zemek1-Apr-14 2:40 
GeneralRe: A couple of things Pin
Florian Rappl1-Apr-14 3:13
mvpFlorian Rappl1-Apr-14 3:13 
GeneralRe: A couple of things Pin
Paulo Zemek1-Apr-14 3:36
professionalPaulo Zemek1-Apr-14 3:36 
GeneralRe: A couple of things Pin
Bill_Hallahan13-Apr-14 13:18
memberBill_Hallahan13-Apr-14 13:18 
GeneralRe: A couple of things Pin
Paulo Zemek13-Apr-14 13:23
professionalPaulo Zemek13-Apr-14 13:23 
GeneralRe: A couple of things Pin
Bill_Hallahan14-Apr-14 16:40
memberBill_Hallahan14-Apr-14 16:40 
GeneralRe: A couple of things Pin
Paulo Zemek14-Apr-14 16:52
professionalPaulo Zemek14-Apr-14 16:52 
GeneralRe: A couple of things Pin
Bill_Hallahan15-Apr-14 16:25
memberBill_Hallahan15-Apr-14 16:25 
GeneralRe: A couple of things Pin
Paulo Zemek15-Apr-14 16:45
professionalPaulo Zemek15-Apr-14 16:45 
GeneralRe: A couple of things Pin
Bill_Hallahan15-Apr-14 17:15
memberBill_Hallahan15-Apr-14 17:15 
GeneralRe: A couple of things Pin
Paulo Zemek15-Apr-14 17:45
professionalPaulo Zemek15-Apr-14 17:45 
GeneralRe: A couple of things Pin
Bill_Hallahan15-Apr-14 18:50
memberBill_Hallahan15-Apr-14 18:50 
GeneralRe: A couple of things Pin
Paulo Zemek16-Apr-14 3:09
professionalPaulo Zemek16-Apr-14 3:09 
GeneralRe: A couple of things Pin
Bill_Hallahan16-Apr-14 15:19
memberBill_Hallahan16-Apr-14 15:19 
GeneralRe: A couple of things Pin
Stefan_Lang24-Apr-14 5:06
memberStefan_Lang24-Apr-14 5:06 
AnswerRe: A couple of things Pin
Paulo Zemek12-Apr-14 2:53
professionalPaulo Zemek12-Apr-14 2:53 
GeneralRe: A couple of things Pin
Florian Rappl12-Apr-14 6:16
mvpFlorian Rappl12-Apr-14 6:16 
GeneralRe: A couple of things Pin
Paulo Zemek12-Apr-14 6:39
professionalPaulo Zemek12-Apr-14 6:39 
GeneralRe: A couple of things Pin
Florian Rappl12-Apr-14 7:06
mvpFlorian Rappl12-Apr-14 7:06 
QuestionYou can find another implementation .... Pin
Stefan_Lang25-Mar-14 5:54
memberStefan_Lang25-Mar-14 5:54 
GeneralMy vote of 5 Pin
Volynsky Alex23-Mar-14 10:05
professionalVolynsky Alex23-Mar-14 10:05 
GeneralRe: My vote of 5 Pin
Paulo Zemek23-Mar-14 11:02
professionalPaulo Zemek23-Mar-14 11:02 
GeneralRe: My vote of 5 Pin
Volynsky Alex23-Mar-14 13:07
professionalVolynsky Alex23-Mar-14 13:07 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.150728.1 | Last Updated 21 Apr 2014
Article Copyright 2014 by Paulo Zemek
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid