Links to other parts:

Allocating dynamic memory can be a major slow down in any game.  A memory heap system that replaces the built-in allocation system can help to overcome many slow down situations.  Something I’ve used and seen used is to allocate as much memory as possible into one heap, and then rewrite malloc and free to use that heap; this requires tracking and a bit of memory, but the speed increase has proven well worth the effort.  Thanks to Lee Marshall, formerly of Locomotive Games, for leading me back to memory management concepts and pointing me towards Doug Lea’s work.

 Over the next few posts I’ll present the method I used, as well as the metrics to show the speed increase.  All my tests are run on an old laptop running Windows XP Pro Service Pack 3, with a Pentium-M 1.6GHz processor, 400MHz FSB, and 512MB of RAM.

 The first issue to be tackled is to setup the tracking.  Following the tracking will be a breakdown of malloc, and then free.  Afterwards a simple high performance timer, test and metrics will be discussed.

 In my code I use an array of tracking units, each element is an unsigned 32-bit integer with each bit representing a page of tracked memory.  The size of the array is determined by the amount of memory to be tracked and the page size.

 First the amount of memory to track must be chosen.  The current console systems range up to 512MB of memory, but most of my work was done on the PSP which only has 32MB, so 32MB is the size I choose to test with, even though the PSP only really allows use of about 20MB after the OS and volatile memory.

32 * 1024 * 1024 = 33554432 Bytes

Second the page size for each allocation of memory to track must be chosen.  This will be the minimum allocation size, so a balance must be struck that doesn’t require too many small allocations for large files, such that tracking becomes a heavy burden, and also doesn’t waste too much space for a reasonable number of small allocations.  In my code, the page size should also be made a power of 2, for speed of considerations to be explained later.  I’ve chosen 4096 Bytes.

 Since each page is represented by a bit in a tracking unit:

number of pages per tracking unit =
 
  4 Bytes per tracking unit * 8 bits (or pages) per Byte
 
  (32 pages per tracking unit)
 
   
 
  number of pages required to track the total memory =
 
  33554432 Bytes / 4096 Bytes per page
 
  (8192 pages)
 
   
 
  number of tracking units =
 
  8192 pages / 32 pages per tracking unit
 
  (256 tracking units)

 So at a cost of 256 tracking units, at 4 Bytes each, it will take 1KB to track 32MB with a 4KB page size.  Using a similar setup for 512MB would require 16KB to track, and for 2GB would require 65KB to track.  Pretty sweet, eh?

To aid in tracking a few constants are setup:

1
 
  2
 
  3
 
  4
 
  5
 
  6
 
  7
 
  8
 
  9
 
  10
 
  
#define _MB( size ) size * 1024 * 1024
 
  // Page Tracking
 
  #define TRACKING_UNIT   u32
 
  const TRACKING_UNIT kMemTrackingUnitAllPagesInUse = 0xFFFFFFFF; // All of a Tracking Unit's Pages in use bit mask
 
  const u32 kMemInUse = 0x01; // Page is in use
 
  const u32 kMemNumPagesPerUnit = ( sizeof( TRACKING_UNIT ) * 8 /* Bits per byte */ ); // Number of pages tracked per tracking unit
 
  const u32 kMemPageSize = 4096; // Size of each page to track
 
  const u32 kMemTotalTracked = _MB( 32 ); // Total amount of memory to track
 
  const u32 kMemNumPages = kMemTotalTracked / kMemPageSize + ( (kMemTotalTracked % kMemPageSize)? 1 : 0 ); // Number of pages required to track memory
 
  const u32 kMemNumTrackingUnits = kMemNumPages / kMemNumPagesPerUnit + ( (kMemNumPages % kMemNumPagesPerUnit)? 1 : 0 ); // Number of units required to track all pages

And finally the tracking array and memory to be tracked are allocated:

1
 
  2
 
  
TRACKING_UNIT aMemPageTrackingBits[ kMemNumTrackingUnits ]; // Array of tracking bits
 
  const void* kpMemory = malloc( kMemTotalTracked ); // This is it, the Memory

 Next time I’ll start covering malloc, which maintains and uses the tracking array.  At this point I’m thinking it’s looking a bit long for one post.  As for Mike’s challenge to “Show your Ignorance!” this entire series of posts is open season on me. ;)