Event Planning

I recently had an interesting challenge and I thought I’d share my solution. I’d love to hear what you all think of it and how you’ve solved similar puzzles.

I work on Android and I have to write a notification system that will potentially notify many times each second. This seems like a simple thing to do: write a listener interface, add notifications to a list and then notify when an event happens:

public interface SomethingListener {
  void onSomething(SomethingNotifier sender, Object arg);
}

private ArrayList<SomethingListener> mListeners
    = new ArrayList<SomethingListener>();

public void addListener(SomethingListener listener) {
    if (!mListeners.contains(listener)) {
        mListeners.add(listener);
    }
}

public void removeListener(SomethingListener listener) {
    mListeners.remove(listener);
}

public void somethingHappened(Object arg) {
    for (SomethingListener listener : mListeners) {
        listener.onSomething(this, arg);
    }
}

easy! Let’s write our first listener:

SomethingListener listener = new SomethingListener() {
    @Override
    public void onSomething(SomethingNotifier source, Object arg) {
        source.removeListener(this);
    }
}

Oh no! This is a common pattern: removing a listener in the listener itself. During somethingHappened(), the listener is called, removes itself, which modifies mListeners. Unfortunately, somethingHappened() is in the middle of iterating over mListeners and an Exception will be thrown.

You may consider using the ArrayList index, but that just means that the following listener will be skipped — remember i++ in your for loop! Hacky solutions involving the size of the list are just begging for hard-to-track-down bugs. The first listener that removes a one listener and adds another will break assumptions.

On Android, we have a nice system for handling this type of problem:

private CopyOnWriteArrayList<SomethingListener> mListeners
    = new CopyOnWriteArrayList<SomethingListener>();

public void somethingHappened(Object arg) {
    for (SomethingListener listener : mListeners) {
        listener.onSomething(this, arg);
    }
}

This works great! Each time somethingHappened is called, the iterator from mListeners keeps a local copy list. Only in this case where a reentrant call is made to remove a listener will the list of listeners be modified. You may be notified on a listener that was removed, but that is considered safe.

However, there is a problem with this: memory allocation. In my case, notifications can be made potentially hundreds of times each second. This pattern uses a newly-generated Iterator object on every notification and, if the listeners are modified, can allocate a second list of listeners. I need to guarantee close to zero allocations on notification.

Think… think… thunk.

private ArrayList<SomethingListener> mListeners
    = new ArrayList<SomethingListener>();
private BitSet mRemoved = new BitSet();
private int mNotificationLevel;

public void add(SomethingListener listener) {
    int index = mListeners.lastIndexOf(listener);
    if (index < 0 || mRemoved.get(index)) {
        mListeners.add(listener);
    }
}

public void remove(SomethingListener listener) {
    if (mNotificationLevel == 0) {
        mListeners.remove(listener);
    } else {
        int index = mListeners.lastIndexOf(listener);
        if (index >= 0) {
            mRemoved.set(index);
        }
    }
}

public void somethingHappened(Object arg) {
    mNotificationLevel++;
    int size = mListeners.size();
    for (int i = 0; i < size; i++) {
        if (!mRemoved.get(i)) {
            mListeners.get(i).onSomething(this, arg);
        }
    }
    mNotificationLevel--;
    if (mNotificationLevel == 0) {
        // Now that notifications have been complete,
        // remove listeners.
        int numRemoved = 0;
        int i = -1;
        // previousSetBit is introduced in JDK 1.7
        while ((i = mRemoved.nextSetBit(i + 1)) >= 0) {
            mListeners.remove(i - numRemoved);
            numRemoved++;
        }
        mRemoved.clear();
    }
}

This is quite a bit more complex. Let’s break this up and see how it works.

The main difference is that this keeps track of removed listeners via a BitSet, mRemoved:

private BitSet mRemoved = new BitSet();

Along with this is an integer tracking the recursion of notifications. Recursion is common during notifications where a notification can lead to another notification. mNotificationLevel tracks the depth of the recursion:

private int mNotificationLevel;

When adding, we still need to check to see if the current listener exists before adding it to prevent duplicates:

public void add(SomethingListener listener) {
    int index = mListeners.lastIndexOf(listener);
    if (index < 0 || mRemoved.get(index)) {
        mListeners.add(listener);
    }
}

But now we must check the mRemoved BitSet as well. Here, we’re counting on the ordering in mListeners — the last listener will always be the active one. If there are multiple, the earlier ones will have been marked removed:

public void remove(SomethingListener listener) {
    if (mNotificationLevel == 0) {
        mListeners.remove(listener);
    } else {
        int index = mListeners.lastIndexOf(listener);
        if (index >= 0) {
            mRemoved.set(index);
        }
    }
}

In the remove, we must check the recursion and remove straight from the list if not currently notifying. If a notification is currently occurring, we must mark the listener as removed instead. It will be removed later in somethingHappened().

Now it is time to look at the meat in somethingHappened():

    mNotificationLevel++;
    int size = mListeners.size();
    for (int i = 0; i < size; i++) {
        if (!mRemoved.get(i)) {
            mListeners.get(i).onSomething(this, arg);
        }
    }
    mNotificationLevel--;

This is very similar to our first notification system. There are still a few differences. First, we’re tracking the recursion with mNotificationLevel. Second, we’re capturing the size of the listeners instead of capturing the list of listeners itself. This avoids the iterator allocation, but still captures which listeners are active at the time of notification. It doesn’t notify removed listeners, but I consider that an improvement.

If you were paying attention to the removeListener code, you saw that it doesn’t modify mListeners when notifications are happening. We must do that now:

    if (mNotificationLevel == 0) {
        // Now that notifications have been complete,
        // remove listeners.
        int numRemoved = 0;
        int i = -1;
        // previousSetBit is introduced in JDK 1.7
        while ((i = mRemoved.nextSetBit(i + 1)) >= 0) {
            mListeners.remove(i - numRemoved);
            numRemoved++;
        }
        mRemoved.clear();
    }

Only when all notifications are complete does it remove the listeners from the list. I would have preferred iterating backward and removing listeners from the tail end, but previousBitSet() isn’t available on Android yet — it is in JDK 1.7. C’est la vie.

All-in-all, I’m pretty happy with this solution. We’ve solved the problem of reentrant listeners and there are no new allocations on notification.

There are several improvements that can be made, including not pre-allocating the mRemoved BitSet and making the calls thread safe. This may be sufficient for your use or you may just slap a few “synchronized” on the methods to fix the thread safety. I hope you find it helpful.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s