This article introduces the results of a quick experiment to check how memory pool can be used to optimise performance.
Implementing an algorithm by using dynamically allocated memory can be slower than by using statically allocated memory for (at least?) 2 reasons.
Hence, when speed performance is desirable statically allocated memory should be preferred to dynamically allocated one. If the amount of needed memory is known the implementation is straightforward. If not, one could statically allocate for each variable an amount of memory larger than what will ever be used. This is only possible if an upper bound can be determined, threaten to crash or bug if that upper bound was mistakenly too low, and generally consumes more memory than necessary.
Another solution is to pre-allocate memory and redefined the allocation/free operations to use and reuse that memory. It can be made more efficient than conventional dynamic memory allocation by constraining the size of the allocated memory. Depending on the details of the implementation it is known as memory pools, object pools, or slab allocation. The more often a block of memory is allocated/freed, the more advantageous this solution becomes.
To try it, I've implemented a memory pool as follow. The pool is a double linked list of a given data structure (let's call it T). Upon creation the pool is an empty list. When the user requests the allocation of an instance of T, if there is a free one in the list it is returned, else a new one is dynamically allocated, added to the list, and returned. When the user requests the free-ing of an instance of T, it is not freed but instead marked as free to reuse. The list is kept ordered as follow: free instances are at the beginning of the list, currently used instances are at the end of the list. The memory pool implementation keeps a pointer to the list's head and tail. Then, allocating/freing memory is as simple as checking for the head or tail status, and moving one element from/to both ends of the list or adding a new element when the list is full. When the memory pool is freed, the remaining elements are actually freed. The two macros below allow to create such a memory pool for a given data structure.
The macros can be used as follow to create a dummy Data structure and a memory pool for that structure:
I've tested the performance of that solution as follow. I run through Pascal's triangle and allocate/free as many instances of Data as the value at the current position in the triangle. Then I compare execution time for both malloc/free and the memory pool described above.
Results are as follow:
The version using memory pool appears to be around 2.2 times faster than the version using malloc/free.