Dev-Picayune

This post discusses an object pool design pattern that is applicable in the following scenario:

• You have a list of objects whose state is continually updated.
• The objects are frequently added or deleted from the list, i.e. have limited lifetimes.
• You want to reuse the objects instead, to improve performance or simplify your code.

Introduction

When writing my game Asteroid Smash using Python, I used lists to keep track of on-screen objects like laser shots and asteroids. These objects all have limited lifetimes (for example, a laser shot that only goes a predetermined distance, or an asteroid that drifts across the screen until it gets destroyed). When it’s no longer needed, the object then gets deleted from its associated list. Here is a simplified example:

import random
 
MAX_SHOTS = 5
 
class Shot(object):
    def __init__(self, lifetime):
        self.lifetime = lifetime
 
    def update(self):
        self.lifetime -= 1
        return self.lifetime > 0
 
# create list of Shots with random lifetimes
lst = [Shot(random.randint(1,100)) for x in range(MAX_SHOTS)]
 
# update loop
while lst:
    delete_lst = []
    for i, x in enumerate(lst):
        if x.update(): # decrement object lifetime
            delete_lst.append(i)
 
    # delete any objects whose time count is 0
    for i in reversed(delete_lst):
        del lst[i]
print "Done!"

To summarize what’s going on, a list of 5 Shot objects gets created, each with random lifetime values, and added to a list. After that, a loop is started that calls an update method on each Shot that decrements its lifetime variable by 1. (This roughly simulates what would happen during each pass of a typical game loop.) Once the object’s lifetime value reaches zero, then the object is added to a delete list. Any objects in the delete list get destroyed after each pass of the update loop.

This code works, but it’s clumsy. Note all the bookkeeping that’s necessary. I can’t delete items while I’m iterating through the list, or I’ll invalidate the iterator. This means I have to keep track of the index of which items need to be deleted, and then actually delete them in a second loop. Also, I have to delete the items in reverse order, or I’ll throw off the indexes and delete the wrong items.

To improve the code, I decided to try list comprehensions to shorten the amount of code in the update loop.

# new update loop with list comp
while lst:
    lst = [x for x in lst if x.update()]

This is much more appealing, single-pass approach. However, the list comprehension, while tidy looking, has a big disadvantage: it constantly creates and destroys a list during each iteration of the loop. This makes it a big problem if we pass around a reference to the list within our program, as the reference is immediately invalidated when the list is recreated. If we need to keep the reference to our list constant, then we have to try another approach.

Rethinking the problem

Perhaps if we want to make a better design, then we need to recast the problem slightly. Notice that once all the objects have a lifetime count of 0, then they can all be deleted at one time, which is a straightforward problem. This means filtering the list by deleting the objects turns out to be unnecessary; what we want is a way to separate objects that still need to be updated in the list from those that do not. Then, once all of the objects fail the update call, the entire list can be deleted.

A little-known algorithm in the C++ Standard Template Library (STL) called partition does the separation of elements mentioned above. Given a sequence, partition will reorder items in the sequence so that all items that satisfy a certain condition (like an update call!) precede those that fail the condition. One other great thing about partition is that it works in linear time; assuming a list of N items, then each use of partition will apply the condition check N times and swap items in the list at most N/2 times. [1]

Here’s what partition looks like in Python (translated from SGI’s version of the STL algorithm [2]; comments added by me based on the SGI docs.)

def partition(pred, seq, first, last):
    """ Partition reorders the elements in seq in the range [first, last)
        based on the function pred, such that the elements
        that satisfy pred precede the elements that fail to satisfy it.
        The postcondition is that, for some index value middle in the
        range [first, last), pred(x) is true for every item x in the
        range [first, middle) and false for every item x in the range
        [middle, last). The return value of partition is middle. """
 
    # quick error check on the list indices
    if first > last:
        return 0
 
    # find first element that fails to satisfy the predicate
    for i in range(first, last):
        if not pred(seq[i]):
            break
    else:
        return last
 
    # for all remaining elements in the sequence, if we find one
    # that satisfies the predicate, swap it with one that is known
    # to have (possibly) failed the test. All swaps are necessary
    # to preserve the correct ordering upon exit.
    for j in range(i+1, last):
        if pred(seq[j]):
            seq[i], seq[j] = seq[j], seq[i]
            i += 1
    return i

We also need a predicate function to use with partition, since the update method is actually part of our Shot class and can’t be called directly. We could use a lambda function instead, but that is somewhat slower than a named function.

def update_object(x):
    return x.update()

Using our new partition and update_object functions, our update loop changes to:

end = len(lst)
while end:
    end = partition(update_object, lst, 0, end)

This is one line longer than our list comprehension version, but we also don’t invalidate our reference to the list on each pass since partition performs in-place modification to our list. This makes it better on both counts.

One other item of interest is the variable end. After each pass of the loop, the end index marks the separation between “live” and “dead” objects in the list. As we noted earlier, once end reaches 0, all the items in the list can then be deleted. Look closely though … we were only deleting objects from the list before in order to filter those that didn’t need updating, but partition already does the filtering for us. Since all the objects in the list are, in fact, still good, to reuse one of them we just need to reset the object pointed to by the end index and then increment end by one. If we try to reuse one of the objects in the list and end goes beyond the last item in the list, then we can either expand the list or just ignore the request, depending on what behavior we want.

Managing details

Here’s the interesting thing: by switching our code to use partition, what we’ve created is a simple object pool. At this point though, there are too many bookkeeping details, and it would be better to encapsulate the pool inside a class.

class ObjectPool:
    def __init__(self, **kwargs):
        self._clsname = kwargs['classname']
        self._args = kwargs.get('args') or []
        self._num_objects = max(kwargs['num'], 0)
        self._pred = kwargs['update_func']
        self._max_objects = kwargs.get('max', self._num_objects)
 
        # Create the objects
        self._objs = [apply(self._clsname, self._args)
                      for x in range(self._num_objects)]
        self._end = len(self._objs)
 
    def _extend_list(self, args):
        """ default policy is to add one object, up to max_objects ...
        override with different behavior if needed. """
        self._objs.append(apply(self._clsname, args))
        self._num_objects += 1
 
    def add(self, *args):
        """ Add one new (live) object to the pool. """
        newend = self._end + 1
        # if we reach our predefined maximum number of objects,
        # don't create any more.
        if newend > self._max_objects:
            return None
        # if we bump up against the end of our list but are below the
        # max number of objects, extend the list
        if newend > len(self._objs):
            self._extend_list(args)
        else:
            self._objs[self._end].reset(*args)
        self._end += 1
        return self._end - 1
 
    def update(self, *args):
        """ Update each object in the pool, using the pred function. """
        self._end = partition(self._pred, self._objs, 0, self._end, args)
        return self._end

That’s perhaps a lot to digest. Let’s look at a short code sample of how to use the new class that will make it easier to understand.

shots = ObjectPool(classname=Shot, update_func=update_object, num=5)
while shots.update():
    pass
print "Done!"

You can see here that the ObjectPool class takes keyword parameters. The first parameter, classname, specifies the name of each object’s class in the pool. The second parameter, update_func, specifies the predicate function used to update the objects. The third parameter, num, specifies the initial number of objects created. (There is also an optional fourth parameter, max, that specifies the maximum number of objects within the pool; if max isn’t explicitly specified, then it will default to num.)

Besides the update method we’ve already discussed, the add method will attempt to either insert a new object in the pool or reset an existing object whose lifetime has expired. (The add method assumes that each object in the pool has implemented a reset method that reinitializes the object.) If neither option is possible (the pool has reached its max or no objects have expired), then add will simply return None to indicate a failure. (You can override the _extend_list method if you wish to change this default behavior.)

A short demo of object pooling

To demonstrate the utility of this code, I’ve modified Alex Holkner’s Noisy demo in the pyglet 1.1.2 distribution to use my ObjectPool class. His example program displays balls bouncing around the edges of a windowed display. Normally the balls bounce indefinitely until the user presses a Delete key, but I changed the demo to have the balls exist for only a short time before they are deleted from the display. The sample also demonstrates how the ObjectPool prevents you from adding more than the max number of objects defined in its constructor. This demo, along with the provided unit tests, should give you a good starting point for using ObjectPool in your own games or applications.

Download op.zip (17 Kb)

References:
[1] http://www.sgi.com/tech/stl/partition.html
[2] http://www.sgi.com/tech/stl/stl_algo.h