Fast Efficient Fixed-Size Memory Pool
No Loops and No Overhead
Ben Kenwright
School of Computer Science
Newcastle University
Newcastle, United Kingdom,
b.kenwright@ncl.ac.uk
Abstract--In this paper, we examine a ready-to-use, robust,
and computationally fast fixed-size memory pool manager
with no-loops and no-memory overhead that is highly suited
towards time-critical systems such as games. The algorithm
achieves this by exploiting the unused memory slots for
bookkeeping in combination with a trouble-free indexing
scheme. We explain how it works in amalgamation with
straightforward step-by-step examples. Furthermore, we
compare just how much faster the memory pool manager is
when compared with a system allocator (e.g., malloc) over a
range of allocations and sizes.
Keywords-memory pools; real-time; memory allocation;
memory manager; memory de-allocation; dynamic memory
I. I
NTRODUCTION
A high-quality memory management system is crucial
for any application that performs a large number of
allocations and de-allocations. In retrospect, studies have
shown that in some cases an application can spend on
average 30% of its processing time within the memory
manager functions [1–4] and in some cases this can be as
high as 43% [5].
However, speed is only one of the features we look at
for a good memory manager; in addition, we are also
concerned with:
• Memory management must not use any resources
(both memory or computational cost)
• Minimize fragmentation
• Complexity (ideally a straightforward and logical
algorithm that can be implemented without too
many problems)
• Ability to verify and identify memory problems
(corruption, leaks).
Nevertheless, the majority of applications use a
general memory management system, which tries to
provide a best-for-all solution by catering for every
possible scenario. For some systems, where speed is
critical, such as games, these solutions are overkill.
Instead, a simplified approach of partitioning the memory
into fixed sized regions known as pools can provide
enormous enhancements, such as increased speed, zero
fragmentation and memory organization.
Hence, we focus on a fixed-pool solution and
introduce an algorithm that has little overhead and almost
no computational cost to create and destroy. In addition,
it can be used in conjunction with an existing system to
provide a hybrid solution with minimum difficulty. On
the other hand, multiple instances of numerous fixed-sized
pools can be used to produce a general overall flexible
general solution to work in place of the current system
memory manager.
Alternatively, in some time critical systems such as
games; system allocations are reduced to a bare minimum
to make the process run as fast as possible. However, for
a dynamically changing system, it is necessary to allocate
memory for changing resources, e.g., data assets
(graphical images, sound files, scripts) which are loaded
dynamically at runtime. The sizes of these resources can
be determined prior to running. This then makes the fixed
memory pool manager ideal. Alternatively, as mentioned
a range of pools can be used for a best-fit approach to
accommodate varying size data.
Naive memory pool implementations initialize all the
memory pool segments when created [6][7]. This can be
expensive since it is usually necessary to loop over all the
uninitialized segments. Our algorithm differs by only
initializing the first element and so has little
computational overhead when it is created (i.e., no loops).
Hence, if a memory pool is only partially used and
destroyed, this wastes fewer processor cycles.
Furthermore, for dynamic memory systems where
partitioned memory is constantly created and destroyed
this initialization cost can be important (e.g., pools being
repeatedly partitioned into smaller pools at run-time).
In summary, a memory pool can make an application
execute faster, give greater control, add greater flexibility,
enable greater customizability, greatly enhance
robustness, and prevent fragmentation. To conclude, this
paper presents the implementation for a straightforward,
fast, flexible, and portable fixed-size memory pool
algorithm that can accomplish O(1) time complexity
memory allocation and de-allocation that is ideal for high
speed applications.
The fixed-size pool algorithm we present boasts the
following properties:
• No loops (fast access times)
• No recursive functions
• Little initialization overhead
• Little memory footprint (few dozen bytes)
• Straightforward and trouble-free algorithm
• No-fragmentation
1Copyright (c) IARIA, 2012. ISBN: 978-1-61208-222-6
COMPUTATION TOOLS 2012 : The Third International Conference on Computational Logics, Algebras, Programming, Tools, and Benchmarking