|
 Features
Play
by Play: Effective Memory Management
Platform Specifics
A memory manager presents a logical view of memory in the same way that
a file system provides a logical view of a disk drive. Most often, memory
managers are concerned with managing dynamic RAM of some sort. Some console
makers like to make things more interesting by providing a relatively
large main memory but also scattering other smaller chunks of RAM around
the system.
The memory
manager allows us to abstract away the physical details of the memory
subsystem and deal instead with a nice, logical model of memory. For example,
on the PS2 we don’t necessarily need to know that the first megabyte of
RAM is reserved for the operating system. It’s enough that the memory
manager knows. By abstracting away some of the details of the physical
memory system, our game can become more platform independent.
Most console hardware has alignment requirements that, not so surprisingly,
differ from platform to platform. Many platforms require anywhere from
4- to 64- byte alignment for buffers in graphics rendering or file IO.
Each type of hardware might need the memory manager to be tweaked to better
fit the needs and abilities of the platform. Often this information can
be passed to the memory manager using a heap setup structure.
Finally, you should be wary of third-party libraries that may use malloc
and free , effectively bypassing your memory manager’s interface. The
printf function in the PS2 standard C library uses malloc and free ; our
solution was to write our own printf function.
Hardware
Support
On most modern computers, the issue of fragmentation has been greatly
reduced by the use of a hardware-based paged memory manager unit (PMMU).
Obviously, the fact that virtual memory provides an application with lots
of addressable memory means that even an inefficient memory manager can
be used. However, the more interesting point is that the PMMU without
any secondary storage can dramatically help with fragmentation. The PMMU
takes a very large address space (larger than the physical RAM it represents)
and maps it onto physical memory. Obviously, this mapping is not one-to-one,
but rather it maps a subset of the memory space onto a “working set” of
memory pages.
The key impact of using a PMMU in terms of fragmentation is that when
a memory block is released, any portion of that block completely spanning
one or more PMMU pages can be remapped by the PMMU. The result is actually
two forms of fragmentation: address-space fragmentation and memory fragmentation.
While this effect might seem to make a bad problem worse, it actually
simplifies things. Because the PMMU provides a large address space, the
address-space fragmentation can be largely ignored. Instead, the allocation
algorithm concentrates on minimizing memory fragmentation by first attempting
to utilize the unused portions of allocated memory pages (pages that contain
some allocation but are not completely full) before remapping unused memory
pages back into memory.
Managing Your Memory Manager
Memory managers are like most real-life managers. You have to keep them
under control, or else they tend to wander off without adequate information
and make strange decisions. Your memory manager sometimes needs your help
to stay on the right track too. Let’s look at some common problems that
can occur and how to work around them.
Fragged again.One of the major side effects of hand grenades and memory
managers is fragmentation. Previously, we discussed fragmentation in the
context of designing the memory manager to avoid or reduce the effects
of fragmentation. However, there are also some application- level techniques
that can reduce fragmentation.
The use of static allocation (memory defined within a module with storage
allocated within the application image) avoids the memory manager completely
and thus avoids fragmentation. Of course, this usage really only makes
sense when a single object will be represented and when the lifetime of
that object is approximately the duration of the entire application. In
such cases, static allocation can provide a benefit by limiting utilization
of the dynamic memory manager to those memory objects that are truly dynamic.
Another strategy that relies entirely on the memory manager user is to
perform submanagement of memory based on specific program knowledge. For
example, if a module knows that it needs to allocate X objects of size
Y, it may be far more efficient for the user to allocate a single block
of X * Y bytes and perform its own management within that larger block.
By reducing the number of blocks that the memory manager has to deal with,
the user has generally made the job of course, a caveat. Depending on
the amount of fragmentation and the size of X * Y, it is possible that
the application could find itself in the situation where an allocation
of X * Y fails due to fragmentation, whereas X allocations of Y would
have succeeded. We also try to discourage this practice when possible,
as there is code-maintenance overhead.
One way to help avoid memory fragmentation is to always free memory in
the opposite order from which it was allocated. In fact, if you were always
able to allocate and release in such an order, you would never have memory
fragmentation. Realistically, it’s not possible to follow this practice
all the time, but doing it as much as possible will help. Memory fragmentation
is going to occur, and at some point you will probably run into a situation
where it causes a problem in your game. You might have fragmentation that
is occurring in one part of your game that is causing a memory allocation
to fail in a totally unrelated area. Fragmentation might even manifest
itself as a situation where your game will fail only when arriving at
part of your game through a specific path (that causes the fragmentation).
If you don’t have some advanced form of garbage collection, you are going
to have to use other, more crude methods to limit this problem. One possibility
is to change the code that is causing the fragmentation to use a different
allocator so that it doesn’t cause fragmentation. A common way to accomplish
this is to have an allocator that allocates from the other end of memory.
Depending on your game, fragmentation can become more problematic over
time (especially if your allocations don’t have close locality of lifespan).
You can use brute force to minimize these effects, such as shutting down
and restarting code modules between levels as a brute-force garbage collection
technique.
Release builds.When running a release build, there isn’t any debugging
information in the game, as it will consume extra memory. But you still
need a way to know where the game runs out of memory. For Madden,
we assume in memory. If the game does run out, it will crash and optionally
dump some memory info. With a special build, we display some partial information
about the memory manager and the game state so that we can determine if
it ran out of memory because of fragmentation or other reasons.
Getting
on the Field
When talking about memory management, programmers often resort to words
more often associated with cow pastures than games. Terms like heaps,
stacks, and chunks are thrown around like flies buzzing around you-know-what.
To see how important a memory manager is to a game, you have to get past
the abstract poo. A good memory manager allows you to have more animations,
more characters, more textures, more sounds — in short, more of everything
that your game-playing customers love.
In this article we have described some of the issues that may come up
in writing and using your own memory manager. After years of writing and
rewriting memory managers for the Madden series, one piece of advice
that bears highlighting is simply to make sure you schedule adequate design
time on this very important piece of your system; you’ll be glad you did.
References
The Memory Management Reference Beginner’s Guide: www.memorymanagement.org/
articles/begin.html
Johnstone, Mark S., and Paul R. Wilson. “The Memory Fragmentation
Problem: Solved?” In Proceedings of the International Symposium on
Memory Management.ACM Press, 1998. pp. 26–36. www.cs.utexas.edu/users/wilson/papers/fragsolved.pdf
Knuth, Donald E. The Art of Computer Programming, vol. 1, Fundamental
Algorithms. Reading, Mass.: Addison-Wesley, 1973. pp. 435–444.
______________________________________________________
|
|
|
|
|
[Back
To] Effective
Memory Management
