January 15, 2005
C# memory manager for video games console platform
In a previous post I described a fully automatic memory manager that was guaranteed not to leak memory. It was based on reference counting, weak references and compile time analysis. I plan to use this in the runtime for my C# to C++ translator. Now in this post I will look into a possible allocation strategy.
When designing a memory manager, there is an important trade-off to be made between dealing with fragmentation, allocation / deallocation performance and utilization of available memory.
On certain platforms and for certain applications, fragmentation is the downfall of many C++ memory managers. Consider a video game on a console platform. Fragmentation is a serious concern. Console games sometimes run for days on end, for example when abandoned by the player or when running in attract mode in a retail store. Fragmentation must be the number one cause of crashes in long running console games.
It is not a premature optimization to try and maximize memory manager performance. It is not uncommon to see memory management burning 10% or more CPU time on console platforms.
It is always possible to use more memory in a console video game. I have never worked on a project where we haven't used absolutely all the memory available on the platform. Efficient use of memory means more content and better quality content.
Unfortunately, this is a trade-off. I just can't have a memory manager that does not fragment memory, has fast allocation / deallocation and at the same time makes 100% use of all available memory.
For example, a memory manager based on free lists or pools will not suffer from unpredictable fragmentation and will be super fast. But the programmer will have to work hard to use every last bit of memory and carefully tune the sizes of the pools.
On the other hand, consider best-fit memory managers. These do a reasonable job of dealing with fragmentation and are excellent for making use of as much memory as possible. But, especially if they do their best to minimize fragmentation, they are slower than free list based implementations.
There are memory manager designs that are fast and make very efficient use of memory. But because the trade-off always balances, they fragment more quickly, potentially leading to a crash. An example of this kind would be a free list based memory manager that allocates new pools on demand.
I think I know a way to side-step the trade-off. The trade-off still holds but I can design the memory manager so that fragmentation is not such a concern. By releasing myself from the fragmentation side of the trade-off, I am better able to ensure that my memory manager is fast and uses memory efficiently.
A game that crashes after a day is no good. A game that drops 10 frames once every 24 hours during long runs does not have a problem. During these 10 (or so) frames the game would be compacting its heap, thereby eliminating all fragmentation, allowing it to continue for another 24 hours until the next time it needs to compact. I pulled the numbers 10 and 24 hours out of the air. The actual numbers do not matter so long as they do not have a negative impact on the quality of the game.
A game can also force compactions at times when the player will not notice them, such as between frontend and gameplay, between levels and at checkpoints. If a game has been running for a long time without controller input, this probably means the player has abandoned it. They will not notice a compaction when they next pick up the controller and start playing again.
This approach would not be feasible without reflection or some other means of utilizing the program's metadata. In order to compact the heap, the memory manager must relocate the objects into a contiguous block of memory. It must also "fix up" all the fields that reference these relocated objects. This is where reflection comes in. Reflection makes it easy to find the fields that need to be fixed up.
It is possible to get close to this in a language without reflection through the use of a handle table, which avoids the need to fix up fields. But this does not side-step the trade-off. By introducing double-indirections whenever a field is dereferenced, the memory manager has reduced performance.
For my C# runtime's memory manager, I plan to do something along these lines. The first thing I will try will be based on free-lists and pools. The heap will actually be a stack of pools, each pool being able to satisfy allocations of a fixed size. Whenever an object is allocated, it will be satisfied from the first pool with a free slot available. If no pools have a free slot, a new pool will be pushed onto the stack. If the stack is too full to allocate a new pool, the stack will be compacted. If that fails, then the problem is not fragmentation. The heap has truly run out of memory. When an object is automatically deallocated because its reference count has reached zero, its pool's slot will be made available for a future allocation of the same size.
I still need to think about variable sized arrays because these do not pool well. Perhaps I will allocate arrays using best-fit and compact the heap whenever this fails. Array allocations should be less common so the lower performance of best-fit seems appropriate because it will reduce the number of compactions that are necessary.
Now I'm starting to optimize prematurely! I just want to make sure that I can think of a workable solution before I commit too much to my C# to C++ translator. The real memory manager will be designed based on profiling actual allocation patterns.
When designing a memory manager, there is an important trade-off to be made between dealing with fragmentation, allocation / deallocation performance and utilization of available memory.
On certain platforms and for certain applications, fragmentation is the downfall of many C++ memory managers. Consider a video game on a console platform. Fragmentation is a serious concern. Console games sometimes run for days on end, for example when abandoned by the player or when running in attract mode in a retail store. Fragmentation must be the number one cause of crashes in long running console games.
It is not a premature optimization to try and maximize memory manager performance. It is not uncommon to see memory management burning 10% or more CPU time on console platforms.
It is always possible to use more memory in a console video game. I have never worked on a project where we haven't used absolutely all the memory available on the platform. Efficient use of memory means more content and better quality content.
Unfortunately, this is a trade-off. I just can't have a memory manager that does not fragment memory, has fast allocation / deallocation and at the same time makes 100% use of all available memory.
For example, a memory manager based on free lists or pools will not suffer from unpredictable fragmentation and will be super fast. But the programmer will have to work hard to use every last bit of memory and carefully tune the sizes of the pools.
On the other hand, consider best-fit memory managers. These do a reasonable job of dealing with fragmentation and are excellent for making use of as much memory as possible. But, especially if they do their best to minimize fragmentation, they are slower than free list based implementations.
There are memory manager designs that are fast and make very efficient use of memory. But because the trade-off always balances, they fragment more quickly, potentially leading to a crash. An example of this kind would be a free list based memory manager that allocates new pools on demand.
I think I know a way to side-step the trade-off. The trade-off still holds but I can design the memory manager so that fragmentation is not such a concern. By releasing myself from the fragmentation side of the trade-off, I am better able to ensure that my memory manager is fast and uses memory efficiently.
A game that crashes after a day is no good. A game that drops 10 frames once every 24 hours during long runs does not have a problem. During these 10 (or so) frames the game would be compacting its heap, thereby eliminating all fragmentation, allowing it to continue for another 24 hours until the next time it needs to compact. I pulled the numbers 10 and 24 hours out of the air. The actual numbers do not matter so long as they do not have a negative impact on the quality of the game.
A game can also force compactions at times when the player will not notice them, such as between frontend and gameplay, between levels and at checkpoints. If a game has been running for a long time without controller input, this probably means the player has abandoned it. They will not notice a compaction when they next pick up the controller and start playing again.
This approach would not be feasible without reflection or some other means of utilizing the program's metadata. In order to compact the heap, the memory manager must relocate the objects into a contiguous block of memory. It must also "fix up" all the fields that reference these relocated objects. This is where reflection comes in. Reflection makes it easy to find the fields that need to be fixed up.
It is possible to get close to this in a language without reflection through the use of a handle table, which avoids the need to fix up fields. But this does not side-step the trade-off. By introducing double-indirections whenever a field is dereferenced, the memory manager has reduced performance.
For my C# runtime's memory manager, I plan to do something along these lines. The first thing I will try will be based on free-lists and pools. The heap will actually be a stack of pools, each pool being able to satisfy allocations of a fixed size. Whenever an object is allocated, it will be satisfied from the first pool with a free slot available. If no pools have a free slot, a new pool will be pushed onto the stack. If the stack is too full to allocate a new pool, the stack will be compacted. If that fails, then the problem is not fragmentation. The heap has truly run out of memory. When an object is automatically deallocated because its reference count has reached zero, its pool's slot will be made available for a future allocation of the same size.
I still need to think about variable sized arrays because these do not pool well. Perhaps I will allocate arrays using best-fit and compact the heap whenever this fails. Array allocations should be less common so the lower performance of best-fit seems appropriate because it will reduce the number of compactions that are necessary.
Now I'm starting to optimize prematurely! I just want to make sure that I can think of a workable solution before I commit too much to my C# to C++ translator. The real memory manager will be designed based on profiling actual allocation patterns.
# posted by Alastair Patrick : 1:03 PM
