Fragmentation is basically where you've got a something that's X big but all the wee tiny bits where you can place your something are too small even though your something would totally fit if the space weren't partitioned so badly. Consider me trying to park in Fell's Point (this is near the water in Baltimore for those wondering):
If you try to park on the street in Fell's Point, you will rapidly learn that there are no lines on the street. This means that people with giant SUVs getting less than 10 mpg highway have NO IDEA where to park their environment destroyingly inefficient vehicles. I drive a tiny Saturn which is mostly made of plastic. It does not ever fit in the spaces left. If only (heaven forbid) I could rearrange these parking challenged bozos' vehicles, I would have plenty of room!
This, friends, is fragmentation at its ugliest. It also happens in your computer's memory (among other places).
Backing Stores and Virtual Memory and Consoles, Oh My!
Memory fragmentation is basically like the two images above: you've got X amount free but it's all broken up into tiny bits that you can't really use. It's a Bad Thing (TM). Occasionally you need to allocate something big and contiguous like an image or something and those tiny bits just aren't going to cut it even though it would totally fit if you could add up all the tiny bits. This requires another chunk of memory to be grabbed from the free store to satisfy your request.
For a normal modern OS, this usually isn't a big deal because we have a) a backing store like a hard drive, and b) a good virtual memory system that can page things in and out if you get near the end of physical RAM a la your undergraduate OS course. The worst that usually happens is the program is a little more chuggy (or a lot more chuggy, depending on your system) and you get fragged more often because your framerate dips and you just can't dodge that guy's rail anymore (bastard).
On a console or embedded device (like the iPhone) it's a whole lot more catastrophic. We may or may not have a backing store. We may or may not even have a basic virtual memory system. It probably doesn't use the backing store that we may or may not have to page RAM even if it has the hardware to do so. So we may or may not be screwed when trying to allocate a giant piece of memory for the screen grab of your most recent death because railboy is totally hacking. By "screwed" here I mean "crash" because that's usually what such devices do. And, sadly, in this situation, we're usually screwed.
How It Be Happenin'
Consider the following horribly-contrived-yet-so-close-to-actual-production-code-I've-seen-recently-that-it-makes-me-shiver-just-typing-it example:
vectorStuffToLoad;
StuffToLoad.push_back( "some_prefs.xml" );
StuffToLoad.push_back( "a_texture.dds" );
StuffToLoad.push_back( "this_is_temp.dds" );
StuffToLoad.push_back( "big_honkin_asset.stuff" );
StuffToLoad.push_back( "another_asset.stuff" );
for ( uint ii=0; ii<stufftoload.size(); i++ )
{
LoadAsset( StuffToLoad[ii] );
}
The basic idea is that it's trying to load a bunch of stuff. During the loading of those assets, it really needs the "this_is_temp.dds" texture prior to loading "big_honking_asset.stuff" but then gets rid of both of it and the prefs XML file. Those of you who have dealt with this issue are probably headpalming right now (just play along). For this exercise, we'll assume that LoadAsset allocates exactly once per asset. and UnloadAsset properly deallocates that one allocation. So how swiss-cheeseified does this snippet make your memory?
That's the big blocks, certainly. What about the rest of it? The bad news is that depending on your particular compiler and the version of the Standard C++ Library you're using (otherwise known as the STL), it might be much, much worse. At the very least, the vector is going to allocate at least once but more likely two or three times. Each string pushed into the vector is probably going to allocate once for the string. If LoadAsset's prototype looks like this:
BOOL LoadAsset( string AssetToLoad );
it probably allocates once per function call for the pass by value (hooray for copy constructors!) as well. So by the time you get to allocating the one chunk for your optimzed LoadAsset, you've probably blown two tiny temporary allocations on strings! Load and unload a bunch of assets and you're nickling and diming your memory to screwedness!
For people not used to thinking about this kind of optimization, this often comes as a complete shock. This kind of thing usually requires someone (typically me), to go through piles of code to root these things out of them because memory is prodigiously perforated and the game crashes if you play it a lot. This is both tedious and error prone and a better solution is to not write it like this in the first place.
This is one way fragmentation happens and it's really, really painful to deal with after the fact. Such issues tend to not manifest themselves until the very end of the game which tends to only get played near the end of the project which is where disasters tend to collect leading to some very, very long work weeks. Don't ask how I know this. To make matters worse, it only takes one dood to sprinkle such gems throughout a significant portion of your codebase.
If You Were Looking For an Easy Fix, You Will Be Disappointed
WIthout going into a lot of gory details about How To Write A Memory Manager in C++, I'm going to have to gloss over some details (besides, that's for a different post). The basic gist of how to deal with fragmentation is to have a decent idea of how your program's memory is going to be used and be uber-careful with anything that might allocate.
For the example above, we know that both string and vector are going to allocate at least some memory. We can provide an allocator to it or remove them completely since, at least in this example, we don't actually need most of what they do and our list is hardcoded anyway. We can further make this better by having a temporary heap that we know is going to be churning a bunch and pass that into the LoadAsset function so our two temporary assets don't fragment the main heap either. At that point, we can optimize the heap function for the temp heap to prevent fragmentation since we're going to hammer it (and believe me, once you have such a heap, you will hammer it). Here's a somewhat less fragmenty version:
struct AssetLoadInfo
{
const char *mAssetName;
uint mHeapIndex;
};
AssetLoadInfo *c_StuffToLoad[] =
{
{ "some_prefs.xml", c_tempHeap },
{ "a_texture.dds", c_defaultHeap },
{ "this_is_temp.dds", c_tempHeap },
{ "big_honkin_asset.stuff", c_defaultHeap },
{ "another_asset.stuff", c_defaultHeap },
{ NULL, 0 }
};
BOOL LoadAsset( const AssetLoadInfo &rfAssetInfo );
BOOL UnloadAsset( const char *AssetName );
for ( uint ii=0; NULL != c_StuffToLoad[ii].mAssetName; ii++ )
{
LoadAsset( c_StuffToLoad[ii] );
}
UnloadAsset( "some_prefs.xml" );
UnloadAsset( "this_is_temp.jpg" );
We aren't talking rocket science here, but it does require programmers to carefully consider what they're doing. C++ makes it stupifyingly easy to make a mess of things and you just don't want to get yourself backed into a corner with fragmentation when your game is being released on a console. People don't like it when their games crash (believe me on this one).
There's WAY more to it than just small optimizations like the one above. Having a proper memory strategy, making sure that you have a proper memory budget, and making your own memory allocation devices are all super important in memory limited situations and can save you an awful lot of painful debugging. See you next time for the next installment of "Stuff They Never Tell You About Game Development"!
