Dynamic allocation of game objects can be costly. Instead of allocating objects dynamically during gameplay it can be more effective to retrieve a free object out of a pre-allocated contiguous array of cache-friendly items. This is typically called “pooling.” An object pool is a common way to reduce dynamic allocation during gameplay. Below is the description of my implementation of such Object pool called Bitpool. Source code can be downloaded here.
This implementation makes use of a bitmap that keeps track of objects that are in use or free. This bitmap is a char array with each element (size 1-byte(8-bit)) representing 8 different memory locations. Based on the size of pool, number of char elements needed for bitmap is calculated.
In the constructor call of Bitpool each char element in bitmap, starting from lsb to msb, all bits are made 1. Once all the bits are made 1 in an element, same procedure is implemented in the next element until the number of bits turned to 1 are equal to size of the pool.
For example, if size of the pool is 15.
numOfElements in bitmap would be : 15/8 = 1.
So, we have bitmap[0] …..bitmap[numOfElements]. In this case, bitmap[0] and bitmap[1].
After inserting all 1s, bitmap elements would look like this,
bitmap[0] = 1111 1111 => 8
bitmap[1] = 0111 1111 => 7 8+7 = 15, i.e., size of pool
When GetObject() is called, starting from bitmap[0] to bimap[numOfElements] bits are checked from lsb to msb until a bit with value 1 is found. Once that bit is found, memory address corresponding to that bit is returned and that bit value is changed to 0 indicating that it is ‘in use’ now. If no bit with value 1 is found, there is no free object in pool and hence a nullptr is returned.
Similarly for ReturnObject(), the bit corresponding to provided memory pointer is found and that bit value is changed to 1 to indicate it is ‘free’ now.
In addition to above, a variable objects_available is used that keeps track of number of objects that are available in pool. So with each call to GetObject(), this value is decreased by 1 & vice versa when ReturnObject() is called.
Source Code : Bitpool.docx
References : http://www.ibm.com/developerworks/aix/tutorials/au-memorymanager/
Bitpool
BlockingQueue is the concept of creating a container of a predetermined size in such a way that it is safe to use over n reader threads and m writer threads. This implementation creates a ThreadSafeContainer class to create this Blocking Queue. ThreadSafeContainer class is a simple generic container with a fixed maximum length established when it is created. This design is subject to race conditions between calls to add and remove functions. Add and Remove functions are used to add/remove an element in/out of the container.These functions serve the same purpose when run in multithreaded environment. When a couple of threads call Add, it adds two elements inside container & similarly when they call remove, it removes two elements from container. But, when this container is out of space and we try adding an element in Container, the add operation blocks all the threads until a space is available. Likewise, when container is empty calling remove blocks all the threads until there is any element inside Container. Thus allowing thread safety on n number of reader threads & m number of writer threads. This design is thread safe because multiple threads manipulate shared data in such a way that multiple threads while keeping a flow of control do not end up reading/writing wrong data. A brief explanation on how it achieved is stated below.
When Add is called, a lock is acquired which is applied on a condition variable (cv_add) that blocks all other threads making call to this function until there is any space left in container. On the other hand, Remove function does the same thing by applying lock on its condition variable(cv_remove) until the container is not empty.
In a case when the container is full and a call is made to Remove, it’ll remove an element & notify the condition variable(cv_add) indicating that the container is no longer full & all the threads blocked during Add are now allowed to enter Add.
Similarly when the container is empty & a call is made to Add, it adds an element & notifies cv_remove indicating that the container is no longer empty & removes block on all the threads making call to Remove.
Shutdown function simply sets a boolean to true that satisfies the other condition of both the condition variables(cv_add and cv_remove) allowing threads to enter into Add & Remove & throw a ShutDownException.
Clear function simply sets head and tail pointer of queue to its initial position(i.e. 0) indicating the container is now empty.
Source Code : ThreadSafeContainer.docx