views:

90

answers:

4

I'm working on a Java Android game. Games here generally need to use memory pools to avoid garbage collection.

For the sake of argument, say I have the following classes:

// Enemy in the game
class Enemy { int x; int y; abstract void update(); }
// Enemy that just bounces around
class Roamer extends Enemy { int direction; ... }
// Enemy that chases a player
class Chaser extends Enemy { Player target; ... }
// maybe 20 more enemy types...

Making use of subclasses is a pain when using memory pools as you need to e.g. say how many Roamer and Chaser objects you want upfront and not just how many Enemy objects you might need. Also, the virtual function calls to update can be slow.

One alternative I've thought of is to just merge all these classes into one e.g.

class Enemy
{
    int direction;
    Player target;
    int type; // i.e. ROAMER_TYPE, CHASER_TYPE
}

I would then have an update function that checked the "type" variable and updated accordingly. This is obviously a more C-like approach. It feels hacky though because e.g. a roamer enemy will have a "target" variable it never uses. I'm unlikely to have more than a 100 enemies in memory at a time though so it really isn't a big deal memory wise. I just want some compromise between nice code and speed.

Does anyone have any comments on how best to structure this? Is merging classes like this going too far? Is this ever a good idea? Should I just use a regular class tree?

I know there are no right answers to this, but I'd like some different viewpoints.

A: 

Have you actually verified that you'll have performance issues without a memory pool?

Assuming you do need to use a memory pool, why not have one for each type of object and have them "grow" to the number of objects that you need? There is inefficiency if the balance between the type of objects changes drastically over time, but the approach you describe also has inefficiencies (unused fields) and seems like it wouldn't be fun to maintain.

Laurence Gonsalves
> Have you actually verified that you'll have performance issues without a memory pool?The Android GC can run at random times for about 300ms if you deallocate tool often so it's a no-brainer to use memory pools for most games if you want a consistent e.g. 30 fps.> There is inefficiency if the balance between the type of objects changes drastically over time, but the approach you describe also has inefficienciesHmm. I need to balance this too with the speed of the virtual function calls.
Bob Page
+1  A: 

Also, the virtual function calls to update can be slow.

Nonsense! The cost of making a virtual function call is a couple of instructions in a JIT compiled application. Even in interpreted mode, I would only expect it to take a dozen native instructions more. This is down in the noise ... unless you are making these calls tens millions of times a second.

I would second the gist of @Laurence's answer. Only spend time on performance hacks once you have verified (i.e. by measurement) that there really are performance issues that need to be addressed. If you ignore this, you risk making your code more complicated and harder to maintain than it needs to be. And you are likely to make performance worse in your naive attempts to make it better ... especially as the Android JIT compiler gets better.

Stephen C
Android only recently got JIT compilation in version 2.0. Even in that version it isn't enabled for normal users. It is just an option for developers to test with. Many phones will never be upgraded even that far anyway. That said, there is a graph re this in the Google I/O Real-Time Games talk, and virtual function calls weren't that bad. JNI and calling via interfaces were much worse: http://code.google.com/events/io/2009/sessions/WritingRealTimeGamesAndroid.html
Lance Nanek
"The cost of making a virtual function call is a couple of instructions in a JIT compiled application."And also potentially a cache miss, which is much worse on performance than simply a couple of extra instructions.
munificent
+2  A: 

Would composition work better than inheritance here? For example, something like this:

class Enemy {
    int direction;
    Player target;
    Strategy updater;
}
interface Strategy {
    void update(Enemy state);
}
class Roamer implements Strategy {
    public void update(Enemy state) {
        //Roamer logic.
    }
}
class Chaser implements Strategy {
    public void update(Enemy state) {
        //Chaser logic.
    }
}

Then you would only need one instance of each particular strategy. All Enemy objects from the pool currently acting as the Roamer would use the single Roamer instance for their updates, for example. This prevents having to keep all the logic in a single class, which might get unreasonably complex.

If this weren't an Android game you could then put a map in the Enemy class for keeping state re that enemy that one strategy needs, but that another doesn't. Since we have to avoid allocations, which can trigger the garbage collector, however, it may be better to just have all the members needed in the Enemy class like you said.

You could use preallocated arrays in the Enemy class for state. The Chaser would then always keep a reference to the Player it is chasing in a particular index of the state array, for example. That's getting awfully complex, however.

Lance Nanek
A: 

You could copy the memory pool that is internal to the framework from here (see Pool, Poolable, PoolableManager, Pools, FinitePool, SynchronizedPool):

http://android.git.kernel.org/?p=platform/frameworks/base.git;a=tree;f=core/java/android/util

If ou do so, be sure to put them in your own package namespace.

There is no need to lose object orientation for the sake of object pooling. If the code there is still so generic that it scares you, use the same idea to do a simplified generic pool for your objects.

hackbod