Game Engine Gems 2

 409

26

AHighlyOptimizedPortable

MemoryManager

Jason Hughes

Steel Penny Games, Inc.

26.1Introduction

Every game has a memory manager of some sort. On PCs, this tends to be Mi-

crosoft’s C run-time library memory manager. On the various consoles, it’s likely

to either be the platform-specific memory manager that was written by the hard-

ware vendor or the one provided by the compiler company in its run-time library.

Do they all work the same way? No. Do they exhibit the same performance char-

acteristics? Absolutely no. Some allow the heap to become fragmented very

quickly, while others may be very slow for small allocations or when the number

of allocations becomes quite large, and still others may have a high per-allocation

overhead that invisibly eats away at your memory.

Memory allocation is a fundamental operation, thus, it has to satisfy a wide

number of use cases robustly and efficiently. This is a serious technical chal-

lenge. Even a good implementation can harm a game’s performance if exercised

in just the wrong way. A naive implementation can utterly cripple performance

or cause crashes due to artificial low-memory situations (e.g., fragmentation or

overhead). The good news is that most of the provided memory managers are

relatively efficient and work well enough for simple cases with few allocations.

After enough experiences where cross-platform stability and performance

came down strictly to the memory manager, however, you may be tempted to

implement your own that is scalable and easy to tune for best performance. These

days, with so many platforms to support, it’s a mark of quality for an engine to

run well across all machines.

410 26.AHighlyOptimizedPortableMemoryManager

AlternativestoRollingYourOwn

Surely someone has already written a good heap. Doug Lea’s dlmalloc is one of

the best and is typically the memory manager of choice on Linux. There are

many derivatives on the internet that claim some improvements, but there are

many flavors to choose from. dlmalloc is a good choice primarily because it’s

very stable and well-tested, it’s public domain code that is freely available, and it

runs on 32-bit and 64-bit systems of either endianness. Very compelling.

The main gripes with dlmalloc is that it is a mess to look at, it’s horrible to

debug in case of heap corruption, and it’s easily corrupted in case of a buffer

overrun. As for usability, there’s no way to create one-off heaps with it that have

been optimized for special use cases, where you can predict sizes and counts of

allocations. dlmalloc also has a fairly high per-allocation overhead that chews up

memory. As general-purpose heaps go, it’s excellent, but for games, we some-

times need custom solutions with more bells and whistles.

DesirableProperties

After writing about eight or nine different memory managers, a list of priorities

emerges from recognizing the importance of certain attributes that make a

memory manager good. Here are a few:

1. Must not thrash the CPU cache. High performance comes with limiting the

number of bytes that have to interact with RAM. Whatever is touched should

fit within a minimum number of cache lines, both to reduce memory latency

and to limit the amount of cache disruption to the rest of the program.

2. No searching for free space. The naive implementation of a memory manag-

er is a linked list of blocks that are marked free or empty. Scanning this list is

hugely expensive and slow under all circumstances. Good memory managers

have lookup tables of some sort that point to places where free blocks of

memory of various sizes are.

3. Minimum overhead per allocation. Reducing overhead in a memory manager

is almost like adding compression to memory—you can fit more data in the

same physical space.

4. Should be easy to debug. Sometimes memory problems happen, and it’s im-

portant to consider the difficulty in tracking down such issues. Sometimes

this means temporarily adding features to the memory manager. Ideally, the

debug build should do some basic instrumentation as it runs that determines

whether memory has been trampled without slowing down the system.

5. Should resist corruption. Most memory managers are organized such that

blocks of program data are sandwiched between heap tracking information.