Memory Management
Optimizing Dynamic Memory
Allocation
• Memory affects performance in two ways:
– Dynamic memory allocation
• Memory allocation cost
– Solution: Custom memory allocators
– Memory access patterns
• Small data- continuous memory rather than spread
across
Optimizing Dynamic Memory
Allocation (Cont.,)
• Limitation
– Context-switch
• from user mode into kernel mode, process the
request, and then context-switch back to the
program.
• How to overcome?
– custom allocators
• Satisfy requests from a preallocated memory block
• Runs in user mode alone
• Avoid the cost of context switch
Optimizing Dynamic Memory
Allocation (Cont.,)
Common kinds of custom allocators
Stack Based Allocators
Pool Allocators
Single Frame and Double
Buffered Memory Allocators
Stack-Based Allocators
▪ Allocate a large contiguous block
▪ A pointer to the top of the stack is maintained
Memory address
below this pointer are in use
Above this pointer are free
Most recently allocated blocks
can be freed by moving the
pointer back by size of the block
Stack-Based Allocators
▪ memory cannot be freed in an arbitrary order
▪ all frees must be performed in an order opposite to that in
which they were allocated
Solution:
▪ provide a function that rolls the stack top back to a
previously-marked location, thereby freeing all blocks
between the current top and the roll-back point.
▪ a stack allocator often provides a function that returns a
marker representing the current top of the stack.
▪ The roll-back function then takes one of these markers as its
argument.
Double-Ended Stack Allocators
A single memory block can contain two stack allocators
Example: Midway’s Hydro Thunder arcade game
The bottom stack is used for loading and unloading levels (race tracks)
The top stack is used for temporary memory blocks that are allocated and
freed every frame.
This allocation scheme worked extremely well and ensured that Hydro
Thunder never suffered from memory fragmentation problems
Pool Allocators
• Applications that require lots of small blocks of
memory (same size) during runtime.
• Preallocating a large block of memory whose size
is an exact multiple of the size of the elements
that will be allocated
• A pool allocator allocates a chunk of
memory once, and divides that memory into
slots/bins/pools which fit exactly M instances of
size N
Pool Allocators - Example
As an example, consider we want to have a
maximum of 256 bullets in flight at the
same time, each bullet having a size of 32
bytes.
Thus, the pool allocator would allocate
256*32 = 8192 bytes once, dividing it into
slots which are then used for
allocating/freeing objects of size 32.
Single-Frame and Double-
Buffered Memory Allocators
All game engines allocate at least some
temporary data during the game loop. This
data is either discarded at the end of each
iteration of the loop or used on the next
frame and then discarded. This allocation
pattern is so common that many engines
support single- and double-buffered
allocators
Single-Frame Allocators
• Reserves a block of memory and manage it by
stack based allocator
• At the beginning of each frame, the stack’s
“top” pointer is cleared to the bottom of the
memory block
• The allocator will be cleared at the start of
every frame
• Limitation
Memory block allocated out of the single-
frame buffer will only be valid during the
current frame
Double-Buffered Allocators
• A double-buffered allocator allows a block of
memory allocated on frame i to be used on
frame (i + 1).
• For example, memory allocated during
frame n is cleared at the end of frame n + 1, and
those allocated during frame n + 1 will be
cleared at the end of frame n + 2.
• It will come in handy for things like velocity
calculations, which are things that require us to
know the position of the object in the last
frame.
Memory Fragmentation
▪ Major problem with dynamic heap allocations is that
memory can become fragmented over time.
▪ When the number of holes becomes large, and/or the
holes are all relatively small, we say the memory has
become fragmented.
▪ The problem with memory fragmentation is that
allocations may fail even when there are enough free
bytes to satisfy the request.
▪ Virtual memory can resolve this problem, but most of
the game engines do not make use of virtual memory.
Memory Fragmentation
(Cont.,)
Avoiding Fragmentation with
Stack and Pool Allocators
A stack allocator is impervious to
fragmentation because allocations are always
contiguous, and blocks must be freed in an
order opposite to that in which they were
allocated
Avoiding Fragmentation with
Stack and Pool Allocators
• A pool allocator is also free from
fragmentation problems. Pools do become
fragmented, but the fragmentation never
causes premature out of- memory
conditions as it does in a general-purpose
heap. Pool allocation requests can never
fail due to a lack of a large enough
contiguous free block, because all of the
blocks are exactly the same size.
Avoiding Fragmentation with
Stack and Pool Allocators
Defragmentation and Reallocation
When
differently sized objects are being allocated
and freed in a random order, neither a stack-
based allocator nor a pool-based allocator can be
used.
Solution: periodically defragmenting the heap
Defragmentation and Reallocation
Defragmentation involves coalescing all of the free “holes” in the
heap by shifting allocated blocks from higher memory addresses
down to lower addresses (thereby shifting the holes up to higher
addresses).
Defragmentation and Reallocation
Issue in defragmentation(moving allocated
blocks of memory around)
• If anyone has a pointer into one of these
allocated blocks, then moving the block will
invalidate the pointer.
Solution : Relocation(patch any and all
pointers into a shifted memory block so that
they point to the correct new address after the
shift)
Defragmentation and Reallocation
How is defragmentation and relocation done in
game engines?
• programmers must either carefully keep track of all
the pointers manually so they can be relocated, or
• pointers must be abandoned in favor of something
inherently more amenable to relocation, such as smart
pointers or handles.
Defragmentation and Reallocation
smart pointers or handles
Class it can be coded to handle memory relocation properly
References
Game Engine Architecture, 3rd Edition, Jason Gregory, A K Peters, 2019
https://www.gamedeveloper.com/programming/writing-a-game-engine-from-
scratch---part-2-memory
