Memory management for Android game

One of the biggest problem I had when converting Snorms from PC to Android was memory management.

Memory on Android is quite limited, usually you have around 32mb heap size available, and garbage collector is your worst enemy. Combining these two things might be quite tricky, even more if the game was first built for PC where memory and minor garbage collector are not a big issue.

I’ll try to explain in this small article what I did technically to get around this problem.

Environment

The best thing to do is of course to run the application directly on Android and use appropriate tools, but I am used to PC tools and it’s a lot easier to just launch my game from eclipse than sending it to Android (or Android simulator). So In order to have an environment similar to Android you need to adjust heap size of your VM, just set it to 32mb (in eclipse just use VM argument ‘-Xmx32m’)

The second important thing is to know when garbage collector occures, so we need the Java VM to be more verbose by using the VM argument ‘-verbose:gc’, it will tell you in the system out whenever major (Full GC) or minor (GC) garbage collector occures.

If you are planning to run the game only on PC you must avoid at all cost major GC, and have the lowest number of minor GC.

If you are planning to run the game on Android, then you must avoid all GC. Just be warned that when running the game on PC there can be some minor GC that occurs because of Java itself (objects created to handle system interaction).

JVisualVM

Capture du 2013-01-19 14:00:07

JVisualVM will be your best friend, this tool is shipped with Oracle JDK and Open JDK (visualvm package on debian based systems), when you launch it you can see list of Java applications running, just select yours.

  • 1st tab: summary of your application parameters
  • 2nd tab: you can see in real time the cpu usage, memory,… and you can also request Head dump from here
  • 3rd tab: detailed thread view, you can request Thread dump from here
  • 4th tab: sampler will allow you to see in real time which objects use CPU and memory, I didn’t use the CPU sampler yet, so I will just explain the memory sampler
  • 5th tab: I don’t know what the profiler does, it just crashes on my environment

Head dump

When requesting an head dump you will see all the Java objects that are currently in memory

Capture du 2013-01-19 14:08:20

You can sort by number of instances (or by total size) for each Java object type, when double clicking an object you will get the whole list of instance of this object, with references and such.

This tool is very very useful to find memory leaks, for example if you run multiple levels of your game and see the memory is always growing, then chances are there is a memory leak. By using the head dump you can find the objects that are using memory and particularly find which parent object holds a reference to it. If after finishing a level you see some game elements are still in memory, just use head dump, locate their references, and you know which object was not properly cleaned. Java will keep objects in memory if they have a reference somewhere. By properly cleaning the referees it will automatically clean the descendant.

I still don’t really know how to handle primitive types in this tool, for example in the screenshot you can see byte[] objects are using quite a lot of memory, but most of them don’t even have a reference. So basically I just ignore them, correct other objects, and usually those will also disappear.

Thread dump

I only use Thread dump in one case: finding dead locks.

Dead locks occurs when you use synchronization, for example let’s say there are 2 threads in your game, one for rendering, the other for game engine, and they both use some common objects. As they might use the same object at the same time, you must sometimes use synchronization. Let’s say (pretty bad example, but it’s just an example):

  • Object SpriteList: holds the sprite list in your game, you don’t want this list to be changed during rendering, so there is a lock mechanism inside
  • Object PathTools: used to get the path from a point to another (with obstacles and such), as you don’t want to manage dynamically created list, the result list is created only once at startup and all methods share it. So this tool is single threaded (lock mechanism) to avoid concurrent access to the list
  • Object Sprite: the draw method needs to know if player can see the sprite, so it calls the PathTools to check if path between player and itself is free
  • Object Sprite: the engine run method check if there’s other Sprites around to interact with (collision for example), it first uses the PathTools to get all points between both sprite, and then retrieve other Sprites using SpriteList for that purpose
  • Thread R: for rendering, retrieve the Sprite list and call their draw method
  • Thread E: for game engine, run the engine on all game elements

So what could occur in this example

  • Thread R begins rendering, it locks the sprite list
  • Thread E calls the sprite run method, it gets the path between two objects and begin looping through points
  • Thread R renders a sprite, draw method needs the PathTools so it just wait for it to complete, no problem at this point
  • Thread E the run method is going through the list, and call the SpriteList object to check if another sprite is in the path, so it just wait for SpriteList to be freed
  • Dead lock !

As you can see, what is happening :

  1. R locks SpriteList
  2. E locks PathTools
  3. R waits for PathTools
  4. E wait for SpriteList

Nothing can ever happen again, game is locked. This is just a basic example, but Thread dump will tell you where dead locks are, and furthermore it will also let you see the full stack trace that conduct to deadlocks on both threads.

Memory sampler

 

Capture du 2013-01-19 14:16:17

The memory sample is also very very nice, this tool will allow you to see in real time the object instantiation/finalization, whenever an object is created you will see the number increase in this view. I mostly use the ‘Delta’ button, in order to see the instance count differences.

In this example you can see the Color object is a a lot instantiated, this is my next target, I will have to check every time a Color object is created if it is useful or not, and use Object pool where appropriate.

You can also see some strange Java objects such as DirectFloatBufferU, I did not instantiate that. As far as I know it’s only linked to Java X11 objects, X11 is the graphical engine used under Linux, so I guess Java needs some objects to interact with environment. So I think I can’t do anything about this one, except if I call some bad functions at some point, but it is not my priority.

Avoiding object instantiation

As I said, the main goal here is to get ride of object instantiation, in a perfect game there should not be any object instantiation from the moment player enters the level to the moment it quits it ! You don’t want the player to get stuck for 50-500ms just because of some garbage collectors.

When you begin writing a game with that in mind from the start, it makes things easier. But Snorms was my first game, and I had bad practices as I only worked on heavy Java server application before, where blocking for a few milliseconds is not a problem at all. And so typically 99% of the problems came from a few objects:

  • Point objects, these objects where just holding x/y/z coordinates
  • Vector objects, almost like Point
  • Color, holds the 4 color components (RGBA)
  • Particle, lots of particles are created during gameplay

So what I had to do is find where these objects where created, reuse them directly if possible otherwise use an object pool to recycle them.

Object pools

Object pools were very important in old versions of Java, because object instantiation was pretty slow, so developers had to use object pooling to avoid latency during object creation. Now the problem is different as instantiation is quite quick.

But finalization/garbage collector might be slow, and so we now need to use object pools to help reusing objects.

Basically, what a pool will do:

  • When you don’t need an object anymore, you send it to the pool
  • When you need to create an object, first you check in the pool if there’s one free to be used, else you just create it

So the pool will just be filled with objects that can be recycled. I made a very simple Pool system for Snorms, it might evolve in the future, but it’s currently doing a great job.

When I want an object to be recycled, I need it to implements a specific interface:

public interface PoolObject
{
    public void initialize();
    public void recycle();
    public void free();
}
  • Initialize will be called when an object is created and when it is recycled
  • Recycle will be called when the object is being inserted into the pool list
  • Free is a convenient method that I use to send an object to the pool, it is not mandatory to use that, usually you should do something such as Pool.free(myObject), but in Snorms I want to make sure a myObject.free() method always exists, as I think it is easier to read that code.

Then we need an object to hold the list of free elements and recycle them. I have used a fixed size array for that, so if there are too many objects to be recycled I just won’t recycle them, it’s best to avoid this case but no big deal here.

public class ObjectPool<T extends PoolObject>
{
    /** The list of objects that can be reused, empty at startup */
    private final T[]                   freeObjects;
    /** Current list size / index */
    public int                          freeIndex   = -1;
    /** Holds the list size, avoid calling freeObjects.length */
    private final int                   poolSize;
    /** Stores the class type, see below */
    private Class<? extends PoolObject> classType;
    /** Lock mechanism used to avoid concurrent access */
    public Boolean                      lock        = new Boolean(true);

    /**
     * @param classType must be the same class as the one used in the pool definition
     * @param poolSize maximum size of the pool
     */
    @SuppressWarnings("unchecked")
    public ObjectPool(Class<? extends PoolObject> classType, int poolSize)
    {
        this.poolSize = poolSize;
        this.classType = classType;
        freeObjects = (T[]) Array.newInstance(classType, poolSize);
    }

    /**
     * Create a new object, reuses one if available
     */
    @SuppressWarnings("unchecked")
    public T newObject()
    {
        synchronized (lock)
        {
            T result = null;
            if (freeIndex == -1)
            {
                try
                {
                    result = (T) classType.newInstance();
                }
                catch (Exception e)
                {
                    throw new RuntimeException(e);
                }
            }
            else
            {
                result = freeObjects[freeIndex];
                freeIndex--;
            }
            result.initialize();
            return result;
        }
    }

    /**
     * Free the specified object so that it can be reused later
     * @param object the object to be freed
     * @return true if the object has been recycled, false otherwise
     */
    public boolean free(T object)
    {
        synchronized (lock)
        {
            if (object != null)
            {
                object.recycle();
                if (freeIndex < poolSize - 1)
                {
                    freeIndex++;
                    freeObjects[freeIndex] = object;
                    return true;
                }
                else
                {
                    //You can use a warn message here, the list should be bigger
                }
            }
            return false;
        }
    }
}

This class is far from being perfect, I had some problems creating the array given the T object, so you have to specify the class type during list creation (Point2d is just a class from Snorms, replace it by what you want):

ObjectPool<Point2d>            poolPoint2d            = new ObjectPool<Point2d>(Point2d.class, 1000);

This is not perfect, but it works :) the Pool object MUST have an empty constructor in order for this code to work

Then to create a new object you just use:

Point2d p2d=poolPoint2d.newObject();
// Call a method an the object that will be similar to the constructor

And to free it:

poolPoint2d.free(p2d);

This is a very simple object factory I did in a few hours, I didn’t look into apache commons pool yet, maybe I’ll switch to that latter.

I also did a dirty way to change existing code, what I did is create a static function for each of the constructor of the object, that will call the newObject method, for example:

public static Point2d create(int x, int y)
{
    Point2d result = Game.poolPoint2d.newObject();
    result.x = x;
    result.y = y;
    return result;
}

Then I called the search/replace function of my editor to replace all ‘new Point2d(‘ to ‘Point2d.create(‘, so it took me only a few seconds to get my code working with the new instantiation process. But of course now the biggest problem is to call the free method every time needed. There’s no magical solution, you have to check all the code and insert free methods where appropriate.

But I used another dirty process to help me, so that I can easily find objects that where not properly disposed.

Finding the bad boys – finalize method

As I said the problem now is to find every occurrence of the pooled objects, and reycle them. The thing is that these objects are usually small objects that are used a lot, which makes things a lot harder. So I find a dirty solution that helped me A LOT.

First you must have some kind of methods to reproduce easily the same game scenario all the time. What I did in my case is that I used the fact that a game is being runned in the background when you launch the game and just stay in the menu screen. So I lock the random number algorithm, I launch a few hundreds of game cycles and exit when I reach cycle 3000.

Every time I reach cycle 3000 I take a screenshot of the game, this will allow me to check if changes I did do not impact the game scenario. this is very useful because sometimes objects you want to free might be used by other unsuspected objects, so you must make sure that there’s no regression after using object pools.

Now I also have to know what objects where not properly cleaned during these cycles. To do so I have to override the finalize method of the pooled object, the finalize method is called when garbage collector is cleaning memory, and warn the user that the object was not properly cleaned, problem is there can be thousands of objects, and in the finalize method you don’t really know how this object was created.

So, we will modify the object constructor and the initialize method, to store the stack trace of the constructor. Getting the stack trace is pretty easy using ‘Thread.currentThread().getStackTrace()’, just parse the result, remove useless stacks, and just get the ONE line you want:

public static String getRevelantStackTrace()
{
    for (StackTraceElement ste : Thread.currentThread().getStackTrace())
    {
        if (!ste.getClassName().startsWith("java."))
            if (!ste.getClassName().startsWith("sun."))
                if (!ste.getClassName().startsWith("your.useless.packages"))
                {
                    return ste.toString();
                }
    }
    return "";
}

In the pooled object just store this information at initialize/constructor (don’t forget to remove it when releasing the game !), and use a HashMap in the finalize method to count occurences

public static final HashMap<String, Integer>    stackCount    = new HashMap<String, Integer>();
@Override
protected void finalize() throws Throwable
{
    super.finalize();
    int cnt = 0;
    if (stackCount.containsKey(stackTrace))
    {
        cnt = stackCount.get(stackTrace);
    }
    cnt++;
    stackCount.put(stackTrace, cnt);
}

When the game reaches the 3000 cycles, just print the content of the stackCount object, and you can see where and who created those. In order to get better result, you should call the garbage collector manually every few cycles ‘System.gc();’

You will get the stack relevant object/line that created the bad object, reuse or recycle it, and you’re done !

*edit*
Sorry, comments are disabled since a long time as I was getting too much spam, I will think of a way to re-enable them someday

License

Creative Commons License
This page is licensed under a Creative Commons Attribution 4.0 International License.

Basically you can do almost anything you want as long as you give the correct attribution (link to my domain, my twitter, or this page for example)

The code itself (classes, functions,…) is not copyrighted (CC0), you can do whatever you want with it

Comments are closed.