Parentheticals & Excursions

Reading posts on the android developer group prompted me to reread the Java Language Specification and confirmed that I had forgotten something very important about Java, specifically:

Thread contention for Java synchronized blocks is not guaranteed to be fair.

This matters, because if you have a situation where a ‘producer’ is delivering data to a ‘consumer’ via a synchronized data structure, the producer may be permanently blocked while the consumer polls for data even though the consumer is repeatedly taking and releasing the lock.

In the context of an Android application: if the producer is the event thread delivering events to an application created thread for processing, then it’s a potential (and surprising!) source of ANRs. This is exactly what was happening to me when I filed an issue I titled: “ANR arising from touch event dispatch”. If only I’d remembered that Java threads aren’t guaranteed to be fair, I wouldn’t have wasted hours producing a (mostly) reproducible test case.

You can avoid the problem by using a fair lock, but this is relatively expensive if you’re aiming to create a high performance application, like a game say, which I was (and still am). So instead I wrote a simple event queue for delivering motion events to a thread other than the main application thread based on a synchronization-free fixed-size circular buffer that uses volatiles to manage concurrency.

I’ve been using the class below, for a while now and haven’t encountered any issues with it. Then again, I could once have said that of the code it replaced…

import android.view.MotionEvent;

/**
 * <p>
 * A simple event queue for delivering motion events to a thread other
 * than the main application thread. The implementation is based on a
 * synchronization-free fixed-size circular buffer that uses volatiles
 * to manage concurrency. Adding an event to the queue is allocation
 * free. Removing an event from the queue is only allocation free if
 * the event object has been recycled.
 * </p> 
 * 
 * <p>
 * The implementation assumes that calls to the add (resp. next) method
 * are single threaded (ie. made on just one thread, or externally
 * synchronized).
 * </p>
 * 
 * <p>
 * NOTE: Mapping of the MotionEvent fields is incomplete and does not
 * include historical data; this is easily addressed by modifying the
 * implementation.
 * </p> 
 * 
 * @author Tom Gibara
 */

// NOTE: The safe concurrency reliability of this implementation is based on:
// 1. Calls to the add and next methods are single threaded.
// 2. The mHead and mTail fields are volatile.
// 3. The mHead (resp. mTail) field is only modified in the next (resp. add) method.
// 4. Updates to the mHead and mTail methods are the last operations in any method.  

public class MotionEventQueue {

    private final int mSize;

    private final long[] mDownTimes;
    private final long[] mEventTimes;
    private final int[] mActions;
    private final float[] mXs;
    private final float[] mYs;

    private volatile int mHead;
    private volatile int mTail;

    public MotionEventQueue(int size) {
        mSize = size;
        mDownTimes = new long[size];
        mEventTimes = new long[size];
        mActions = new int[size];
        mXs = new float[size];
        mYs = new float[size];
        mHead = 0;
        mTail = 0;
    }

    public boolean addEvent(MotionEvent event) {
        final int head = mHead;
        final int tail = mTail;
        int nextTail = tail + 1;
        if (nextTail == mSize) nextTail = 0;
        if (nextTail == head) return false;
        mDownTimes[tail] = event.getDownTime();
        mEventTimes[tail] = event.getEventTime();
        mActions[tail] = event.getAction();
        mXs[tail] = event.getX();
        mYs[tail] = event.getY();
        mTail = nextTail;
        return true;
    }

    public MotionEvent nextEvent() {
        int head = mHead;
        if (head == mTail) return null;
        MotionEvent event = MotionEvent.obtain(mDownTimes[head], mEventTimes[head], mActions[head], mXs[head], mYs[head], 0);
        mHead = head == mSize - 1 ? 0 : head + 1;
        return event;
    }

}