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.
Figure 1: Main memory growth for console game machines.
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 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.
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)
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.