Systematic Gaming

August 25, 2008

Memory Management: Budgets, Tracking and Profiling

Filed under: game programming, memory management — Tags: , — systematicgaming @ 2:16 am

The last few entries in this series mostly focused on memory allocation. However allocation is only one part of memory management. To create a complete memory management system we need to do a lot more than allocate and free blocks of memory. We need to look at memory as a system wide resource. This involves

  • budgeting memory for the various game sub-systems
  • tracking memory use, to ensure budgets are honoured and memory doesn’t leak
  • profiling memory use to look for worst case spots in or program and trend memory usage over time

We’ll look into how we can enhance the allocation interface we’ve designed to help accomplish these goals. As well, we’ll see how these features aid us in managing memory system-wide.

Memory Budgets

Since memory is a limited and global resource we have to properly share that resource between different sub-systems of the game: AI, graphics, animation, etc. If you don’t budget memory, when you do run out (and you will), you’ll have a difficult time deciding which part of your game is using too much memory and needs to be reduced.

The usual approach is to give each sub-system a budget of the total memory it can use. So you simply divvy up the memory: AI gets 10MB, Graphics gets 200 MB, and so on.

The amount of memory budgeted for each system can be difficult to determine, and will likely change during development as various features are requested or cut. Generally data-heavy sections like graphics, sound and animation take up the lions share of the memory.

Physical memory types must be taken into account when budgeting, some sections may need more than one type of memory, where as some sections may not be able to use other memory types. It would be the rare AI system that utilized video memory, but graphics often requires both normal memory memory in addition to video memory.

Budget Policies

There are many ways you can choose to budget your memory. Each has their own pros and cons, and well as carrying certain design philosophies.  Budgeting by sub-system (AI, animation, graphics) is a common approach. However some sub-systems are too large or complex to simply assign a single chunk of memory.

Graphics for example requires textures and models for characters, texture and models for the background and level, textures for special effects and numerous frame buffers and command buffers to communicate with the GPU. So simply stating “200MB for graphics” won’t cut it, it’s just too simplified to work with.

It’s often to split up game sub-systems by major feature or logical separation. So we’d take our 200MB budget for graphics and split it up like so

  • 20 MB for the graphics system (frame buffers, etc)
  • 20 MB for effects
  • 90 MB for the background
  • 70 MB for characters

This makes it easier to manage the budget, and also makes it easier for other people to understand and work within a budget. It’s difficult for your art department to work make a game that uses 200MB of graphics for characters and environments.  If you tell them they have to fit the environment in 90MB and characters in 70MB, that’s something they can start working with.

You can of course budget memory to any detail you want, but as a systems programmer you’re more interested in the total picture of memory than how many bytes are taken up by normal maps and animation blend trees. Those details are best left to area specialists.

Managing Budgets

There are a number of ways to manage budgets, most dealing with how we allocate the memory used.

We could create separate heaps for each category and have each sub-system use separate allocators. I call this strict budget management. This lets us ensure that a section cannot use more memory than budgeted, because it will simply run out of memory. Also it prevents a very active sub-system with many small allocations from fragmenting the entire heap.  Strict management will waste some memory because it’s unlikely each sub-system will use every byte of memory, so each separate heap will have a little bit of unused memory.

Alternatively we can share a heaps between sub-systems, possibly only a single heap per physical memory type.  I call this relaxed budget management. It is less wasteful than multiple heaps, since you don’t have the unused memory in each heap going unused. However, since you’re sharing a single allocator for multiple sub-systems you increase the possibility of fragmentation and the speed issues with having many allocations in a single heap.

In reality we’d probably want a system with some elements of strict management and some elements of relaxed management. We can then balance wasted memory overhead vs speed and fragmentation issues.

If you remember the allocator interface from part three, you’ll see we already added some basic functionality to handle this type of management. We can extend the memory type in our Alloc method to represent a budged area of memory so we can allocate memory like so:

gAllocator.Alloc( size, align, MEM_GRAPHICS_TEXTURE );
gAllocator.Alloc( size, align, MEM_AI );
gAllocator.Alloc( size, align, MEM_ANIMATION );

This allows you to handle memory budget policy at a global scope – through your main hierarchical memory manager. Memory types can be routed to whatever specialized allocator you choose or pooled into a single large one.

How to we go about enforcing budgets?  There’s not really any automatic way of doing so. Generally if you are over budget in some area you need to make it noticeable.  Either by displaying some information on screen or notifying the lead of whatever game area is over budget.

You also want to have the game continue without crashing if possible, as it’s very common to be over budget throughout the development cycle. Fortunately many consoles have extra memory for development purposes so you often use more more memory than available on a standard retail console. As features, data and code solidify then memory will be brought within budget.

Tracking Memory

If we don’t know how much memory we’re using there’s no way to really manage or budget it. So we need to come up with a way of tracking memory usage. For each bit of memory we want to track the following information:

  • type of memory allocated
  • size allocated
  • address of allocation

These are the minimum requirements and are already available to our allocator. Ideally we also want to capture some extra information

  • file name and line of allocation or the callstack
  • user supplied comment or tag

This information gives us the context of the allocation, which aids in analysis and debugging. We currently don’t supply the file name or line, callstack or any tag. To track our memory, let’s extend the global new operator, here’s a basic implementation

void* operator new(size_t size)
{
   return malloc(size);
}

First, let’s extend it to support our allocator interface

void* operator new(size_t size, size_t alignment, uint32_t type)
{
   return gAllocator.Alloc(size, alignment, type);
}

Now let’s add some basic tracking

void* operator new(size_t size, size_t alignment, uint32_t type)
{
   void *address = gAllocator.Alloc(size, alignment, type);
   TRACK_MEMORY( size, type, address );
   return address;
}

We use this new operator just like usual, passing the extra arguments like so

// allocate a texture from video memory
Texture *myTexture = new( 16, MEM_VIDEO ) Texture();

Notice the size is not passed, it’s implicit when using the new operator and inserted by the compiler.

Now what about adding the extra tracking information? We could extend our new operator like so

void* operator new(size_t size, size_t alignment, uint32_t type, 
                   int line, const char *file, const char *tag)
{
   void *address = gAllocator.Alloc(size, alignment, type);
   TRACK_MEMORY( size, type, address, line, file, tag, GetCallstack() );
   return address;
}

// allocate a texture from video memory
Texture *myTexture = new( 16, MEM_VIDEO, __LINE__, __FILE__, "Character head texture" ) Texture();

This would work, but look at that call to new, that’s a lot of stuff to pass around. Especially since we’d always need to pass those line and file macros each time. Also it means we’ll have hundreds of comment tags in our executable, all the time. Since we don’t need to track memory in the final version of our game we really don’t want to waste our global memory with a bunch of strings we don’t need. With these issues in mind, let’s use some macros to clean this up.

void* operator new(size_t size, size_t alignment, uint32_t type, 
                   int line, const char *file, const char *tag)
{
   void *address = gAllocator.Alloc(size, alignment, type);
   TRACK_MEMORY( size, type, address, line, file, tag, GetCallstack() );
   return address;
}

#if defined (TRACK_MEMORY)
#define NEW( align, type, text )    new( align, type, __LINE__, __FILE__ , text )
#else
#define NEW( align, type, text )    new( align, type, 0, NULL, NULL )
#define

// allocate a texture from video memory
Texture *myTexture = NEW( 16, MEM_VIDEO, "Character head texture" ) Texture();

We have a simpler call to new, and when not tracking memory our extra strings are removed. Also we can now enable or disable memory tracking with a define.

Now that we have as way of specifying the information we want to track, we have to decide how we want to actually track it. We basically have two options online tracking, where we track the memory withing the game, or offline tracking, where we log our allocations and analyze them later on another computer. Both methods have their own pros and cons.

Online tracking

Pros

  • Provides continuous and instant feedback about how much memory we’re using
  • Useful for data creators to know how much data assets use (load new model, check memory tracker)

Cons

  • Requires extra memory to manage tracking information (we need a way to match free’d pointers to allocated blocks to properly update our tracking data)
  • Information is only available when game is running (not after the game crashed)

Offline tracking

Pros

  • Requires no extra memory to track
  • Allows various tools and analysis to be used

Cons

  • Requires a way of outputting from a console (possible, but now always simple or efficient)
  • Logging can add a lot of overhead and slow down the game and alter timing

In actuality you’ll want to be able to track memory both online and offline. I recommend tracking memory online by type and logging more detailed information to an external source. Again, you’ll want to be able to enable or disable each type of tracking.

Memory Profiling

Now that we can track our memory, we can create a memory profile of our game. A memory profile represents the state of our memory resources during our game. You can think of it as a summary of the stats we’ve been tracking. When we profile or memory we’re looking for a few key data points:

  • Are we within our memory budgets?
  • What is our memory high watermark?
  • Do we have any memory leaks?
  • Do we have too much memory fragmentation?

Within Budget

With our tracking information, knowing if we’re in budget is pretty easy. We’ve tracked the size and type of each allocation, so we simply sum them up and report the total. If we want, if we display memory usage on screen we can colour it appropriately.

However it’s important to bring up that when you’re over budget in an area it can mean two things: you’re using too much memory of that type or your budget is simply wrong. At the start of development, often it’s the budget that’s wrong and needs to be tuned, however later in development cycle the budgets are often more strict and possibly unchangeable.

High Watermark

The high watermark is the is the highest level of memory used at any point in our program. So if we allocate 10MB and then free 5MB, our high watermark is 10MB. The high watermark is very important, because it’s the high watermark that determines if we’re using too much memory or not. So knowing the high watermark is critical, it’s also critical to know when the high watermark occurs.

One of the best ways to look at memory and to identify the high watermark is to chart memory usage over time.

Memory Usage Over Time

Memory Usage Over Time

With a chart like this you can clearly see the high watermark at 1600. With a log of the memory tracking data it’s trivial to create this kind of graph. Also, if you add a time stamp to the log and add events to the log (like START_LOAD, END_LOAD, ENTER_GAME, EXIT_GAME, etc) it will help you identify when your high watermarks occur.

It’s common to have the high watermark occur where extra processing occurs, such as when loading a level, or during special game modes like multiplayer. Also in game events like in-engine cinematics and such often require some extra memory above and beyond the standard game modes. So these are all good areas of you game to check, but there’s no way to know for sure when memory usage peaks without tracking it through all modes and levels.

Memory Leaks

Memory leaks, where you allocate memory but don’t free it, are unfortunately a problem of working with a non-garbage collected environment like C/C++. Certain coding conventions and techniques, such as smart pointers, can help reduce the chance of leaking memory. But how do you know for sure? Well, it’s pretty simple to check if you’re tracking your memory allocations.

One way is to simply leave the game running, without really doing anything, and see if the amount of memory used is increasing. However this only catches the simplest of leaks.

A better way is to use your allocation log to ensure that all memory between two points in time is properly freed. For example if you take a snap shot of memory from the main menu, load a level, and go back to the main menu, you should expect the profile of memory to be the identical. If not you may have a leak. Of course that doesn’t guarantee you don’t have a leak while playing the game, only that you properly clean up when a level is unloaded.

Fragmentation

We can also examine memory fragmentation with our log of memory allocations. Because we tracked the address and size of each allocation we can create a picture of what our memory layout looks like. We can also colour code each block by type, and identify physical heaps of memory by address.

Visualization of allocations and fragmentation

Visualization of allocations and fragmentation

The above screen shot shows the state of a game’s various heaps and allocations, coded by colour. You can clearly see that there’s very little fragmentation if most of the heaps, and this is actually near the start of the application, so most memory is still unused. Simply put viewing a programs memory this way is a simple and quick way to visualize the application’s memory profile.

Data visualization is key.  Once you have a tool like this that allows you to visualize memory logs you can use it so step through your logs, one allocation at a time to get a good feel for how your game uses memory over time.

Summary

We’ve budged, tracked and know how to profile our memory, combined with our custom allocators we now have the basics of a proper memory management system. While I haven’t provided a full implementation of each component you should now have an understanding of what’s required to manage memory in a modern console game.

In the next part we’ll go over more advanced problems encountered and I’ll provide a few links for further reading.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: