|
|
 |
 |
 | | | | |
 |
|||
 |
||||||
          |
 |
 |
||||
|
Gameboy Advance Resource Management General Purpose Memory Management Given the memory constraints of the AGB, and the lack of a swap device for memory, you need to be extremely careful about how you allocate main system memory. For most data structures in a game it makes sense to statically allocate all the structures you will need at compile time. This way you don't have to worry memory allocations failing during run-time. For some game systems however it really helps to have small pools of dynamically allocated memory. These pools can be quite small. For example, we use a tiny buffer of 4k as scratch memory for the AI routines of enemies that are on the screen. For these small general-purpose memory pools you cannot make too many assumptions about how the memory will be used. You want an allocator that will quickly give you memory chunks of any desired size. Because the pools are so small it is important that the memory overhead of dynamically managing these pools be very small as well. We present here a general-purpose memory manager that uses just three percent of the managed buffer for memory management overhead. This allocator must of course also coalesce adjacent free'd buffers and must choose the areas it allocates from carefully, to minimize dead space between allocated blocks (otherwise what is the point of getting the management overhead down to three percent?) It can manage buffers as small as 32 bytes and as large as 512k, twice the size of the AGB's main memory. In the version we present here the memory manager manages the memory using 8-byte memory blocks. Of course, you can use memory blocks of any size you want. Raising the block size will decrease the percentage of memory used for overhead, but will increase the amount of dead memory that cannot be allocated when the user asks for memory regions that are not multiples of the block size. Decreasing the block size does the reverse. Therefore, for a block size of 16, the overhead of the memory management data structures falls to 1.5%. The amount of "dead memory" will depend on the user's allocation pattern. When implementing a system like this you will want to consider the block size carefully. The trick to making a memory manager with low memory overhead is to store as much of the heap management data structures as possible in the unallocated memory blocks. In our memory manager we use two basic data structures: a memory map that indicates which blocks are allocated, and an ordered binary tree that keeps track of all the free blocks. The memory map is stored in the beginning of the allocated buffer and is not available for allocation. The binary tree, however, is stored in the free blocks themselves, and so costs us nothing. For each memory block in the buffer we need to store two pieces of information in the memory map:
To store these two pieces of information in the memory map we use two bits per block. So we can manage up to 32 bytes of data per byte of memory map. (This is where the three percent memory overhead comes from.) For free blocks we don't need to store any information in the memory map. Once we know its free we know that we can find out all we want to know about it from the binary tree node that is stored inside the free block itself. The memory manager also has a small 8-byte header that contains the total number of blocks being managed, an index into the root of the binary tree of free blocks, and a pointer to the first managed node. The memory map follows the header, which is of the right size to store two bits of information per node. Finally each free block may contain a node for the binary tree. The tree nodes hold a pointer to the parent node, a pointer to all that node's smaller children, a pointer to all of the node's larger children and the size of the node. Each free node structure is 8-bytes-just fitting into the block. The manager initializes all the bits in the memory map to free, with the binary tree holding a single node whose size is as big as all of the allocatable memory in the buffer. To allocate a block you round the memory requested to the next block size, and then you walk the binary tree searching for the smallest available block that is large enough to allocate the required memory. Once an appropriate tree node is found, we shrink the node by the requested size. If no memory is left over the node is removed from the tree, if there is memory left over the node is resized and re-linked to the appropriate place in the tree. Finally, you need to update the memory map to flag all of the allocated blocks as used, and you need to set the last block bit for the last block in the allocated region. To free a block you find its area in the memory map, which you can do arithmetically from the pointer passed in, and start clearing allocated bits until you find a map entry that is labeled as the last block in the region. Then you check in the memory map to see if the areas adjacent to this block are free. If they are, you merge the free'd block with its neighbors. For a reasonably well-balanced tree the allocation operation will average m + log(n) time where n is the number of free nodes, and m is the size of the block. The free operation is linear with the size of the block. Our current implementation uses just a sorted binary tree. We do not do any automatic rebalancing, so it is possible, though unlikely, for the tree to become extremely unbalanced and slow the allocator down significantly when there are large numbers of free nodes. If this becomes a problem it is straightforward to implement a rebalancing routine like red-black. We have not found it to be necessary. Random Number Generation with the Mersenne Twister And now for something completely different... The AGB's main CPU does not implement division and mod in hardware. They are implemented in software and are too slow to use for run time generation of random numbers. Most of the high quality random number generation routines require these operations. There is a relatively new random number generation routine called the Mersenne Twister developed by Makoto Matsumoto and Takuji Nishimura in 1997, which does not require mod or divide. This is an industrial strength generator with a period of 2^19937 and is 623-dimensionally equi-distributed. This is far more powerful than you are likely to need in a game—but it is simple to implement and fast to run, so why not use it? To implement the full generator as described in their paper you need to allocate an array of 2496 bytes to store the current state of the generator. It is possible to make this buffer smaller but this will reduce the period of the generator. But then again, this generator already has a period far greater than the number of stars in the universe, so cutting the period down a little bit won't hurt much if you need to get an extra kilobyte out of the generator's state buffer. Generating a new random number out of the state buffer is a matter of doing 4 XORs, 2 ANDs and 4 register shifts, so its fast enough for any purpose. I won't include any information on the theory of how the Mersenne Twister works. You can read about it in Matsumoto and Nishimura's paper (available on their web site http://www.math.keio.ac.jp/~matumoto/emt.html) Discuss this article in Gamasutra's discussion forum ________________________________________________________
|
||||||||||||||||
|
|
Features
