Using Memory Correctly
Did you ever hear the joke about the programmer trying to beat the Devil in a coding contest? Part of his solution involved overcoming a memory limitation by storing a few bytes in a chain of sound waves between the microphone and the speaker. That’s an interesting idea, and I’ll bet we would have tried that one on Ultima VII had someone on our team thought of it.
Memory comes in very different shapes, sizes, and speeds. If you know what you’re doing, you can write programs that make efficient use of these different memory blocks. If you believe that it doesn’t matter how you use memory, you’re in for a real shock. This includes assuming that the standard memory manager for your operating system is efficient; it usually isn’t, and you’ll have to think about writing your own.
Understanding the Different Kinds of Memory
The system RAM is the main warehouse for storage, as long as the system has power. Video RAM or VRAM is usually much smaller and is specifically used for storing objects that will be used by the video card. Some platforms, such as Xbox and Xbox360, have a unified memory architecture that makes no distinctions between RAM and VRAM. Desktop PCs run operating systems like Windows Vista, and have virtual memory that mimics much larger memory space by swapping blocks of little-used RAM to your hard disk. If you’re not careful, a simple memcpy() could cause the hard drive to seek, which to a computer is like waiting for the sun to cool off.
System RAM
Your system RAM is a series of memory sticks that are installed on the motherboard. Memory is actually stored in nine bits per byte, with the extra bit used to catch memory parity errors. Depending on the OS, you get to play with a certain addressable range of memory. The operating system keeps some to itself. Of the parts you get to play with, it is divided into three parts when your application loads:
-
Global memory: This memory never changes size. It is allocated when your program loads and stores global variables, text strings, and virtual function tables.
-
Stack: This memory grows as your code calls deeper into core code, and it shrinks as the code returns. The stack is used for parameters in function calls and local variables. The stack has a fixed size that can be changed with compiler settings.
-
Heap: This memory grows and shrinks with dynamic memory allocation. It is used for persistent objects and dynamic data structures.
Old-timers used to call global memory the DATA segment, harkening back to the days when there used to be near memory and far memory. It was called that because programmers used different pointers to get to it. What a disgusting practice! Everything is much cleaner these days because each pointer is a full 32 bits. (Don’t worry, I’m not going to bore you with the “When I went to school I used to load programs from a linear access tape cassette” story.)
Your compiler and linker will attempt to optimize the location of anything you put into the global memory space based on the type of variable. This includes constant text strings. Many compilers, including Visual Studio, will attempt to store text strings only once to save space:
const char *error1 = "Error";
const char *error2 = "Error";
int main()
{
printf ("%x\n", (int)error1);
// How quaint. A printf.
printf ("%x\n", (int)error2);
return 0;
}This code yields interesting results. You’ll notice that under Visual C++, the two pointers point to the same text string in the global address space. Even better than that, the text string is one that was already global and stuck in the CRT libraries. It’s as if we wasted our time typing “Error.” This trick only works for constant text strings, since the compiler knows they can never change. Everything else gets its own space. If you want the compiler to consolidate equivalent text strings, they must be constant text strings.
Don’t make the mistake of counting on some kind of rational order to the global addresses. You can’t count on anything the compiler or linker will do, especially if you are considering crossing platforms.
On most operating systems, the stack starts at high addresses and grows toward lower addresses. C and C++ parameters get pushed onto the stack from right to left—the last parameter is the first to get pushed onto the stack in a function call. Local parameters get pushed onto the stack in their order of appearance:
void testStack(int x, int y)
{
int a = 1;
int b = 2;
printf("&x= %-10x &y= %-10x\n", &x, &y);
printf("&a= %-10x &b= %-10x\n", &a, &b);
}This code produces the following output:
&x= 12fdf0 &y= 12fdf4 &a= 12fde0 &b= 12fdd4
Stack addresses grow downward to smaller memory addresses. Thus, it should be clear that the order in which the parameters and local variables were pushed was y, x, a, and b. Which turns out to be exactly the order in which you read them—a good mnemonic. The next time you’re debugging some assembler code, you’ll be glad to understand this, especially if you are setting your instruction pointer by hand.
C++ allows a high degree of control over the local scope. Every time you enclose code in a set of braces, you open a local scope with its own local variables:
int main()
{
int a = 0;
{ // start a local scope here...
int a = 1;
printf("%d\n", a);
}
printf("%d\n", a);
}This code compiles and runs just fine. The two integer variables are completely separate entities. I’ve written this example to make a clear point, but I’d never actually write code like this. Doing something like this in Texas is likely to get you shot. The real usefulness of this kind of code is for use with C++ objects that perform useful tasks when they are destroyed—you can control the exact moment a destructor is called by closing a local scope.
Video Memory (VRAM)
Video RAM is the memory installed on your video card, unless we’re talking about an Xbox. Xbox hardware has unified memory architecture or UMI, so there’s no difference between system RAM and VRAM. It would be nice if the rest of the world worked that way. Other hardware such as the Intel architectures must send any data between VRAM and system RAM over a bus. The PS2 has even more different kinds of memory. There are quite a few bus architectures and speeds out there, and it is wise to understand how reading and writing data across the bus affects your game’s speed.
As long as the CPU doesn’t have to read from VRAM, everything clicks along pretty fast. If you need to grab a piece of VRAM for something, the bits have to be sent across the bus to system RAM. Depending on your architecture, your CPU and GPU must argue for a moment about timing, stream the bits, and go their separate ways. While this painful process is occurring, your game has come to a complete halt.
This problem was pretty horrific back in the days of fixed function pipelines when anything not supported by the video card had to be done with the CPU, such as the first attempts at motion blur. With programmable pipelines, you can create shaders that can run directly on the bits stored in VRAM, making this kind of graphical effect extremely efficient.
The hard disk can’t write straight to VRAM, so every time a new texture is needed you’ll need to stop the presses, so to speak. The smart approach is to limit any communication needed between the CPU and the video card. If you are going to send anything to it, it is best to send it in batches.
If you’ve been paying attention, you’ll realize that the GPU in your video card is simply painting the screen using the components in VRAM. If it ever has to stop and ask system RAM for something, your game won’t run as fast as it could.
Optimizing Memory Access
Every access to system RAM uses a CPU cache. If the desired memory location is already in the cache, the contents of the memory location are presented to the CPU extremely quickly. If, on the other hand, the memory is not in the cache, a new block of system RAM must be fetched into the cache. This takes a lot longer than you’d think.
A good test bed for this problem uses multidimensional arrays. C++ defines its arrays in row major order. This ordering puts the members of the right-most index next to each other in memory.
TestData[0][0][0] and TestData[0][0][1] are stored in adjacent memory locations.
|
|
If you access an array in the wrong order, it will create a worst-case CPU cache scenario. Here’s an example of two functions that access the same array and do the same task. One will run much faster than the other:
const int g_n = 250;
float TestData[g_n][g_n][g_n];
inline void column_ordered()
{
for (int k=0; k<g_n; k++) // K
for (int j=0; j<g_n; j++) // J
for (int i=0; i<g_n; i++) // I
TestData[i][j][k] = 0.0f;
}
inline void row_ordered()
{
for (int i=0; i<g_n; i++) // I
for (int j=0; j<g_n; j++) // J
for (int k=0; k<g_n; k++) // K
TestData[i][j][k] = 0.0f;
}The timed output of running both functions on my test machine showed that accessing the array in row order was nearly nine times faster:
Column Ordered=2817 ms Row Ordered=298 ms Delta=2519 ms
Any code that accesses any largish data structure can benefit from this technique. If you have a multistep process that affects a large data set, try to arrange your code to perform as much work as possible in smaller memory blocks. You’ll optimize the use of the L2 cache and make a much faster piece of code. While you surely won’t have any piece of runtime game code do something this crazy, you might very well have a game editor or production tool that does.
Memory Alignment
The CPU reads and writes memory-aligned data much faster than other data. Any N-byte data type is memory aligned if the starting address is evenly divisible by N. For example, a 32-bit integer is memory aligned on a 32-bit architecture if the starting address is 0x04000000. The same 32-bit integer is unaligned if the starting address is 0x04000002, since the memory address is not evenly divisible by 4 bytes.
You can perform a little experiment in memory alignment and how it affects access time by using example code like this:
#pragma pack(push, 1)
struct ReallySlowStruct
{
char c : 6;
__int64 d : 64;
int b : 32;
char a : 8;
};
struct SlowStruct
{
char c;
__int64 d;
int b;
char a;
};
struct FastStruct
{
__int64 d;
int b;
char a;
char c;
char unused[2];
};
#pragma pack(pop)
I wrote a piece of code to perform some operations on the member variables in each structure. The difference in times is as follows:
Really slow=417 ms Slow=222 ms Fast=192 ms
Your penalty for using the SlowStruct over FastStruct is about 14 percent on my test machine. The penalty for using ReallySlowStruct is code that runs twice as slowly.
The first structure isn’t even aligned properly on bit boundaries, hence the name ReallySlowStruct. The definition of the 6-bit char variable throws the entire structure out of alignment. The second structure, SlowStruct, is also out of alignment, but at least the byte boundaries are aligned. The last structure, FastStruct, is completely aligned for each member. The last member, unused, ensures that the structure fills out to an 8-byte boundary in case someone declares an array of FastStruct.
Notice the #pragma pack(push, 1) at the top of the source example? It’s accompanied by a #pragma pack(pop) at the bottom. Without them, the compiler, depending on your project settings, will choose to spread out the member variables and place each one on an optimal byte boundary. When the member variables are spread out like that, the CPU can access each member quickly, but all that unused space can add up. If the compiler were left to optimize SlowStruct by adding unused bytes, each structure would be 24 bytes instead of just 14. Seven extra bytes are padded after the first char variable, and the remaining bytes are added at the end. This ensures that the entire structure always starts on an 8-byte boundary. That’s about 40 percent of wasted space, all due to a careless ordering of member variables.
Don’t let the compiler waste precious memory space. Put some of your brain cells to work and align your own member variables. You don’t get many opportunities to save memory and optimize CPU at the same time.
Virtual Memory
Virtual memory increases the addressable memory space by caching unused memory blocks to the hard disk. The scheme depends on the fact that even though you might have a 500MB data structure, you aren’t going to be playing with the whole thing at the same time. The unused bits are saved off to your hard disk until you need them again. You should be cheering and wincing at the same time. Cheering because every programmer likes having a big memory playground, and wincing because anything involving the hard disk wastes a lot of time.
Just to see how bad it can get, I took the code from the array access example and modified it to iterate through a three-dimensional array 500 elements cubed. The total size of the array would be 476MB, much bigger than the installed memory on the test machine. A data structure bigger than available memory is sometimes called out-of-core. I ran the column_ordered() function and went to lunch. When I got back about 30 minutes later, the test program was still chugging away. The hard drive was seeking like mad, and I began to wonder whether my hard disk would give out. I became impatient and re-ran the example and timed just one iteration of the inner loop. It took 379.75 seconds to run the inner loop. The entire thing would have taken over 50 hours to run. I’m glad I didn’t wait. Any game written badly can suffer the same fate, and as you can see, the difference between running quickly and paging constantly to your hard disk can be as small as a single byte.
Remember that the original array, 250 elements cubed, ran the test code in 298ms when the fast row_ordered() function was used. The large array is only eight times bigger, giving an expectation that the same code should have run in 2384ms, or just under two-and-a-half seconds.
Compare 2384ms with 50 hours, and you’ll see how virtual memory can work against you if your code accesses virtual memory incorrectly.
|
|
Writing Your Own Memory Manager
Most games extend the provided memory management system. The biggest reasons to do this are performance, efficiency, and improved debugging. Default memory managers in the C runtime are designed to run fairly well in a wide range of memory allocation scenarios. They tend to break down under the load of computer games, though, where allocations and deallocations of relatively tiny memory blocks can be fast and furious.
A standard memory manager, like the one in the C runtime, must support multithreading. Each time the memory manager’s data structures are accessed or changed, they must be protected with critical sections, allowing only one thread to allocate or deallocate memory at a time. All this extra code is time consuming, especially if you use malloc and free very frequently. Most games are multithreaded to support sound systems, but don’t necessarily need a multithreaded memory manager for every part of the game. A single threaded memory manager that you write yourself might be a good solution.
|
|
Simple memory managers can use a doubly-linked list as the basis for keeping track of allocated and free memory blocks. The C runtime uses a more complicated system to reduce the algorithmic complexity of searching through the allocated and free blocks that could be as small as a single byte. Your memory blocks might be either more regularly shaped, fewer in number, or both. This creates an opportunity to design a simpler, more efficient system.
Default memory managers must assume that deallocations happen approximately as often as allocations, and they might happen in any order and at any time. Their data structures have to keep track of a large number of blocks of available and used memory. Any time a piece of memory changes state from used to available, the data structures must be quickly traversed. When blocks become available again, the memory manager must detect adjacent available blocks and merge them to make a larger block. Finding free memory of an appropriate size to minimize wasted space can be extremely tricky. Since default memory managers solve these problems to a large extent, their performance isn’t as high as another memory manager that can make more assumptions about how and when memory allocations occur.
If your game can allocate and deallocate most of its dynamic memory space at once, you can write a memory manager based on a data structure no more complicated than a singly-linked list. You’d never use something this simple in a more general case, of course, because a singly-linked list has O(n) algorithmic complexity. That would cripple any memory management system used in the general case.
A good reason to extend a memory manager is to add some debugging features. Two features that are common include adding additional bytes before and after the allocation to track memory corruption or to track memory leaks. The C runtime adds only one byte before and after an allocated block, which might be fine to catch those pesky x+1 and x-1 errors, but doesn’t help for much else. If the memory corruption seems pretty random, and most of them sure seem that way, you can increase your odds of catching the culprit by writing a custom manager that adds more bytes to the beginning and ending of each block. In practice, the extra space is set to a small number, even one byte, in the release build.
|
|
Another common extension to memory managers is leak detection. It is a common practice to redefine the new operator to add __FILE__ and __LINE__ information to each allocated memory block in debug mode. When the memory manager is shut down, all the unfreed blocks are printed out in the output window in the debugger. This should give you a good place to start when you need to track down a memory leak.
If you decide to write your own memory manager, keep the following points in mind:
-
Data structures: Choose the data structure that matches your memory allocation scenario. If you traverse a large number of free and available blocks very frequently, choose a hash table or tree-based structure. If you hardly ever traverse it to find free blocks, you could get away with a list. Store the data structure separately from the memory pool; any corruption will keep your memory manager’s data structure intact.
-
Single/multithreaded access: Don’t forget to add appropriate code to protect your memory manager from multithreaded access if you need it. Eliminate the protections if you are sure that access to the memory manager will only happen from a single thread, and you’ll gain some performance.
-
Debug and testing: Allocate a little additional memory before and after the block to detect memory corruption. Add caller information to the debug memory blocks; at a minimum, you should use __FILE__ and __LINE__ to track where the allocation occurred.
One of the best reasons to extend the C runtime memory manager is to write a better system to manage small memory blocks. The memory managers supplied in the C runtime or MFC library are not meant for tiny allocations. You can prove it to yourself by allocating two integers and subtracting their memory addresses as shown here:
int *a = new int; int *b = new int; int delta1 = ((int)b - (int)a) - sizeof(int);
The wasted space for the C runtime library was 28 bytes for a release build and 60 bytes for the debug build under Visual Studio. Even with the release build, an integer takes eight times as much memory space as it would if it weren’t dynamically allocated.
Most games overload the new operator to allocate small blocks of memory from a reserved pool set aside for smaller allocations. Memory allocations that are larger than a set number of bytes can still use the C runtime. I recommend that you start with 128 bytes as the largest block your small allocator will handle and tweak the size until you are happy with the performance.
'Online Game' 카테고리의 다른 글
| Configuring ConTEXT (0) | 2011.12.27 |
|---|---|
| 코스프레? 귀엽다~~ (0) | 2011.03.04 |
| World of Warcraft adds another half million subscribers (0) | 2008.12.26 |
| Lunia Chronicle (0) | 2008.12.19 |
| Gunz Hack loltastic.dll (0) | 2008.12.16 |
