|
 Features
Play
by Play: Effective Memory Management
Back before
Al Gore invented the Internet, back when 64KB was more memory than any
computer would ever need, there was a time when memory managers didn’t
exist. But gradually, new computer systems came out with larger amounts
of memory (Figure 1). Game designers discovered ways to eat up RAM faster
than any system could dish it out. It became obvious that managing all
this data with a simple static memory map was too much work. Programmers
needed a way to create memory maps that could change dynamically at run
time depending on the state of the program. Thus, the memory manager was
born.
For an excellent
introduction to how a basic memory manager works, check out www.memorymanagement.org/articles/begin.html.
This article will assume this basic knowledge and focus instead on things
to think about when writing your own memory manager and point out some
of the problems you may encounter in using a memory manager. This discussion
is based on our experiences in writing and rewriting the memory manager
for Madden NFL 97 to Madden NFL 2002. This
article is also slanted toward the C language as written for console game
machines. The same principles would apply to C++ and Windows programming,
but the details are likely different.
Growing Your Own
So you know that memory managers are great, but what’s wrong with just
using malloc and free?
They are part of the standard C library, so they should be the best, right?
One major problem is that you don’t really know what they are doing. If
you write your own memory manager, you can generate statistics, add debug
code, and add advanced features that might not be found in the default
memory manager — features like handles, heap compaction, and virtual memory.
The ultimate weapon of game programmers is context. You know the needs
of your game and can tailor the memory manager accordingly. Developing
a successful memory manager requires addressing five different issues:
ease of use, performance, memory over-head, fragmentation control, and
debugging support. Unfortunately, these attributes are all interconnected,
and optimizing one can result in substandard results for another. The
memory manager designer must govern a delicate balancing act.
At a lower
level, memory manager design also requires paying attention to platform-specific
requirements. In addition, it may be possible to utilize hardware support
to assist the memory manager.
Ease of Use
 With
respect to a memory manager, the ease of use consideration really comes
down to a single question: Should the memory manager support pointers,
handles, or both? When design-ing a memory manager and dealing with the
problem of fragmentation, the use of handles can be very appealing. Unfortunately,
while handles provide a straight-forward solution to the fragmentation
problem, they are much more difficult to use than pointers. A memory manager
that supports only handles is essentially pushing its internal complexity
back onto the user.
While supporting both handles and pointers is possible, the resulting
memory manager is more complicated than one that supports a single method.
Madden used to support both handles and point-ers until an analysis
showed that pointers were being used 99 percent of the time. Not surprisingly,
when given a choice, programmers used pointers, since they were the easiest
solution. Therefore, we simplified the latest Madden memory manager
by removing handle support and optimizing the pointer support.
Performance
Performance must be addressed both in terms of speed and consistency.
A memory manager that is fast most of the time but slows down dramatically
at unpredictable times is unacceptable in a gaming environment. Therefore
it is important to understand the issues that contribute to performance.
From the memory manager user’s point of view, two operations will impact
the game: allocations and recycling.
Allocation performance is determined by allocation poli-cy, free list
management, and the use of garbage collection. The most popular allocation
policies are best fit, first fit, and next fit. By organizing the free
blocks as a linked list, best fit has consistent O(n) performance,
while first fit and next fit have worst-case O(n) and on average
O(n/2). By organizing the free blocks as a size-sorted binary tree,
best fit has worst-case O(n) and on average O(n log n).
By organizing the free blocks as a balanced binary tree, best fit has
consistent O(n log n). Garbage collection applies only to
memory managers with handle support, and generally involves a fairly significant
performance penalty when it occurs, as it essentially makes a copy of
the entire memory heap during compaction.
Recycling
performance is based on free list management and the use of free block
coalescing. Free block coalescing requires the ability to locate the blocks
immediate-ly preceding and following any arbitrary block. Some memory
structures, such as boundary tag (see Donald Knuth’s Fundamental Algorithms
under References for more information on the boundary tag), allow this
in O(1) time, while those that don’t require an O(n) scan of the
free block list. The current Madden memory manager uses boundary
tags to allow O(1) access to previous/subsequent blocks and organizes
the free list as an unbalanced binary tree. The result is allocation and
recycling performance both in the O(n log n) to O(n)
range.
MemoryOverhead
Memory overhead is the cost we have to pay to manage memory, since each
allocation will cost some memory. Memory overhead is an important consideration,
especially if the memory manager will be handling a large number of objects.
The first decision is whether the memory map state should be stored internally
or externally to the memory being managed. If it is stored internally,
then the maximum number of allocated blocks does not need to be known
in advance, but memory that is not directly CPU-addressable cannot be
managed. If it is stored externally, you must know the maximum allocated
and free blocks in advance and set aside memory for this state, but address
spaces that are not directly CPU-addressable can be managed.
Madden previously used external storage for the memory state, but
this required additional overhead because it was impossible to predict
accurately the maximum number of allocated and free blocks. We had to
include a “safety factor,” which turned directly into wasted memory. The
new memory manager uses internal storage as shown in Figure 2, thus avoiding
the entire issue. All allocations are 16-byte aligned and each block has
16-byte overhead. By limiting allocations to a minimum of 16 bytes, every
block is guaranteed to have this much storage available. Therefore, when
an allocated block is released, those 16 bytes can be used to organize
the block into the free list.
It is worthwhile to digress slightly and consider the management of non-CPU-addressable
memory. Because consoles are designed for low cost and high performance,
they sometimes incorporate special-purpose memory that is not directly
CPU-addressable. For example, the Gamecube has 16MB of auxiliary memory
(ARAM) that supports only DMA access. A memory manager that stores its
state internal to the memory it is managing cannot be used in such cases,
while a memory manager that stores its state externally can. While it
may seem appealing to use external state storage in order to support all
kinds of memory, our experience with Madden has shown this to be
a mistake. Memory that is not directly CPU-addressable is normally used
only for special types of objects, due to the com-plexity of using the
memory, and often contains only a small number of objects. Therefore,
Madden now uses a single, general-purpose internal storage memory
manager for all CPU-addressable memory and an additional, customized external
storage memory manager for any special-purpose case, such as the Gamecube’s
ARAM.
______________________________________________________
|
|
|
|
|
Effective
Memory Management
