Friday, November 2, 2012

Free Lists For Predictable Game Performance


Games need predictable frame performance. Frequent memory allocations interacting with the garbage collector can make this difficult to achieve. A free list is a data structure that helps relieve pressure on the memory allocator and garbage collector, giving you predictable frame times. Read on to find out more about free lists.

A common pattern in games is to create an object, use it for a frame or two, and then delete the object. Shortly after deleting the object, an object of the same type is created. This repeats every frame and it has a performance cost. (I’ve seen some professional engines which do this 10,000 times in a single frame! They never managed to get a 16ms frame time.)


In languages that require manual memory management, like C++, the cost of frequent construction / deletion of objects can be high but the programmer can control when it happens in the frame. Good programmers go a step further and use pool or fixed block allocators, further reducing the cost of frequent object creation. In languages which automatically manage memory through garbage collection, like Dart, there is no explicit “delete this object now” mechanism— it happens whenever the virtual machine decides is a good time. If it happens at the wrong time the game may miss a frame and appear janky. In order to create high performance games in languages like Dart, you must avoid creating garbage.

The Free List


Key points:
  1. It can be constructed empty or given a list of objects that are already allocated and unused.
  2. When an object is no longer being used, you return it to the free list by calling the add method.
  3. When you need an object of type E instead of calling new E you call getNextFree.

What to do when the free list is empty?

It is possible that when your program first starts or suddenly needs many objects that the free list becomes empty. At this point getNextFree returns null and you have to construct a new instance of type E. Later on, when this new instance is no longer needed, this new instance can be added to the free list. Transparent support for this could be added to the FreeList class which now looks like:



Constructors

Because the objects returned from the free list are already constructed you must be careful to decouple your constructor logic from your actual constructors. You can do this easily in Dart by having all constructors call separate object initialization functions, like this:


Now objects returned from the free list can be initialized using the same logic that is used when “new” is called.


Care Required

Free lists make it easy to shoot yourself in the foot. If some code holds a reference to an object that was added to the free list you’ll have an object that is being manipulated from two places that should only be manipulated from one. Closures make this even trickier because your callback function may not be called until much later, possibly after the object was added to the free list. Be careful.

One solution here is to hide the object references themselves behind a proxy object or integer handle.

Statistics!

Free lists come with a side benefit of being able to track the current allocation count, high water mark and other statistics. If the current allocation count keeps climbing, you may have a leak.

These statistics can be used to tune how many free objects should be kept around and how many objects should be pre-allocated and used to initialize the free list.

Conclusion

Free lists are an important tool to use in your quest for predictable performance. They avoid unnecessary allocation load, provide a central location to track object life cycle statistics, and force you to decouple your object initialization logic from the constructors themselves.