A fast notification system for event-driven design

Back in 2009 I started to work on a custom solution for dispatching and listening to events. At this time I switched to the Haxe language, and so my main motivation was to write a cross-platform system. I also never really liked the event dispatcher in Flash – too java-ish and boilerplate heavy for my taste. I guess this is why other libraries like AS3 Signals, or HSL (Haxe Signaling Library) appeared.

In short, here are the key facts:

  1. I’m using the classic Observer pattern, because it’s simple and widely known.
  2. Instead of listening to single events, I’m registering with multiple related events at once (“event group“).
  3. Updates are not identified by strings, but are represented as integers.
  4. The observers are managed in a linked list.

Notice that in the following text, the terms event/update, listener/observer and event dispatcher/observable are used interchangeably. The source code is hosted on github.
Let’s break down each point:

1. The interface

My design follows the observer pattern – chances are good that it’s the first design pattern covered in many books so I won’t go into much detail.
Actually, it’s quite simple: An observable manages a list of observers. Whenever the state of the observable changes, the observable iterates over all observers and calls observer.update(). The entire system consists of three components:

  1. de.polygonal.core.event.IObservable, an interface which merely defines three methods:

    interface IObservable
    {
        function attach(o:IObserver, mask:Int = 0):Void;
    
        function detach(o:IObserver, mask:Int = 0):Void;
    
        function notify(type:Int, userData:Dynamic = null):Void;
    }
  2. de.polygonal.core.event.IObserver, an interface with a single update() method:

    interface IObserver
    {
        function update(type:Int, source:IObservable, userData:Dynamic):Void;
    }
  3. de.polygonal.core.event.Observable, a ready-to-use implementation of IObservable.

Thinking in flash terms, 2. and 3. correlate with flash.events.IEventDispatcher and flash.events.EventDispatcher. There is however, no flash.events.Event object. Instead the observer has to pull this information from the source (always points to the object that triggered the update) or use the userData parameter, which is often used for convenience (e.g. keyboard events store the current key code in it). Since I prefer short names, addEventListener(), removeEventListener() and dispatchEvent() are simply called attach(), detach() and notify().

2. Event groups

We often have to set up listeners for similar events. For example, let’s assume we want to download a file from a server – in most cases a simple “onLoadComplete” event is not enough: we also need to handle errors or visualize the download progress. So the main idea is to replace multiple calls to addEventListener() with a single call to attach(), as you need those events anyway. This drastically reduces boilerplate code.
A good example is the Resource class from my library, responsible for loading all kind of external assets. By attaching to a resource object, you get all important updates at once:

import de.polygonal.core.event.IObservable;
import de.polygonal.core.event.IObserver;
import de.polygonal.core.io.Resource;
import de.polygonal.core.io.ResourceEvent;
import de.polygonal.core.io.ResourceType;

/**
 * Example: loading an image using the Resource class.
 */
class Main implements IObserver {
    static function main() {
        new Main();
    }

    public function new() {
        var url = "http://polygonal.github.com/doc/ds/images/polygonal.png";
        var res = new Resource(new flash.net.URLRequest(url));
        res.attach(this); //listen to updates
        res.load();
    }

    public function update(type:Int, source:IObservable, userData:Dynamic):Void {
        trace("received event: " + ResourceEvent.getName(type));
        switch (type) {
            case ResourceEvent.COMPLETE:
                var res:Resource = cast source;
                var data:flash.display.Bitmap = source.content;
            
            case ResourceEvent.PROGRESS:
                var progress:Float = userData; //[0,1]
            ...
        }
    }
}

Compiling and running this example, the trace statement prints out all updates like this:

TestLoading.hx:23: received event: START
TestLoading.hx:23: received event: PROGRESS
TestLoading.hx:23: received event: PROGRESS
TestLoading.hx:23: received event: PROGRESS
TestLoading.hx:23: received event: PROGRESS
TestLoading.hx:23: received event: HTTP_STATUS
TestLoading.hx:23: received event: COMPLETE

So far, so good. But what about a situation where you don’t use all those updates? Let’s consider the case that we have tons of observers listening to user input events. We are only interested in keyboard updates, and both key and mouse events are defined in a single event group. Mouse position updates are fired at a high rate and might slow down your application. The solution is to register with a subset of events only by explicitly naming them:

myObserver.attach(myObservable, UIEvent.KEY_DOWN | UIEvent.KEY_UP);

This will only invoke myObserver.update() for those two event types. If we don’t need an event at all (usually application-wide), we can blacklist the event on the dispatcher and disable it completely, further improving performance:

myObservable.mute(UIEvent.MOUSE_MOVE);

3. Why integers?

Using integers for identifying events has some advantages:

  • We can pack multiple properties – in this case a group id and an update id.
  • We can efficiently check against multiple updates by combining them with bitwise OR or test if an update belongs to a particular group:

    public function update(type:Int, source:IObservable, userData:Dynamic):Void
    {
        if (UIEvent.has(type))
        {
            //handle ui updates
            if (type & (UIEvent.KEY_DOWN | UIEvent.KEY_UP) > 0)
            {
                //handle key updates
            }
        }
        if (ResourceEvent.has(type))
        {
            //handle resource updates
        }
    }
  • We can register with/unregister from multiple events at once in an elegant way:

    myObservable.attach(myObserver, Event.A | Event.B | Event.C); //register with A,B,C
    myObservable.detach(myObserver, Event.A | Event.B); //unregister from A,B only
  • Comparing integers is wickedly fast. It won’t make a big difference, but it’s good to know ;).

However, there is a major drawback: one has to make sure integers are unique across the application! Assigning ids by hand is prone to errors and dangerous, so I hand it over to the compiler and let a macro do all the work. In short, a macro is a piece of code written in the Haxe language itself that modifies existing code or generates new one at compile-time. This way, creating an event boils down to this:

@:build(de.polygonal.core.event.ObserverMacro.create([
	KEY_DOWN
	KEY_UP,
	KEY_REPEAT,
	MOUSE_DOWN,
	MOUSE_UP,
	MOUSE_WHEEL,
	MOUSE_MOVE]))
class UIEvent {}

The syntax might look a bit strange at first, but it’s just an array of field names that gets passed to the build method. The macro then generates those fields, encodes and assigns integer values and adds some convenience methods, like for printing out the human readable name of an update. Before Nicolas added the macro-system, I defined them manually, which was a total mess.

Speaking about the format: each 32-bit integer stores a group id and an update type. 5 bits are reserved for the group id, while the remaining bits represent a bit field for the update type. Therefore, a total of 32 groups (2^5-1) and 27 individual types (32-5) can be encoded. In total the system supports 32×27=135 unique events which should be enough for any application. By sacrificing one update bit, we get over 1500 different types.

4. Observer storage

Another decision I made is to use linked lists instead of arrays for storing observers. This way there is no need to make a copy of the observer list before dispatching updates. Arrayed implementations do this, because the observer list can be modified by observers themselves:

public function update(type:Int, source:IObservable, userData:Dynamic):Void
{
    source.detach(this);
}

The above code updates the observer list instantly, but due to the nature of linked list, the update phase won’t break.
Notice that when an observer calls notify() on its observable, the current update stops while the new update is carried out to all observers, and resumed as soon as the nested iteration has been completed. Let’s assume we have 3 observers: [A, B, C] – when B invokes an update the order will be: [A, B, [A, B, C], C]. Now, when C detaches from its source (when C.update() is called for the first time), C will disappear from all “levels”, and the last C at the root level won’t receive an update. In practice this shouldn’t be a problem and it’s usually the desired behavior.

Using linked lists require that observer objects are “boxed”: a helper objects has to be allocated for storing the observer and list pointers. To help with performance, I allocate and reuse those helper structures once an observer gets detached from its observable:

myObservable.attach(myObserverA); //allocate helper structure for A
//...
myObservable.detach(myObserverA); //cache it
//...
myObservable.attach(myObserverB); //reuse helper structure for B
//...

The cache size is set to 10 by default, but you can easily customize this value by providing a different size to the constructor:

var x = new Observable(50);

Performance

First: I can’t imagine a situation where dispatching events could be the bottleneck of an application. That said, it still does not hurt to provide an efficient solution. The most important thing for Flash is to use typed function calls, which are roughly 10x faster. This is achieved by forcing each observer to implement the IObserver interface:
typed v untyped function calls
Also, iterating a linked-list is very fast in Flash. Compared to flash.events.EventDispatcher, the overall result is pretty good:
EventDispatcher v Observable

To sum it up, the system is optimized for updates fired at a high rate and listeners with a short live span, e.g.
an AI system, were lots of agents are interacting with other agents by sending messages.

Tips

  1. Observable.dump() prints out all observers in use along with their number of observers. Useful for profiling.
  2. Observable.release() destroys all observable objects and removes all observers to make sure that the garbage collector can free up all used resources.
  3. Observable.bind(func) can be used to bind a function to an update. The binding is active as long as the closure returns true:
    var f = function()
    {
         trace('update!');
         return true;
    }
    Observable.bind(f, myObservable);

5 Comments

  1. When you said “too java-ish”, did you mean to say “too javascript-ish” or maybe “too ECMAScript-ish”? Because Java is actually using observer pattern instead of event listeners. Pretty much the same thing for C++ as well.

    Great post by the way!

    1. Michael

      ECMAScript-ish because I don’t like the built-in AS3 event dispatcher. java-ish, because it often suffers from boilerplate code.

  2. Very elegant and clean model for events. I like that you avoided using anonymous callbacks in favor of typed interfaces, and the parameters to the callback make the data ‘flat’ so what a wrapper object (aka Event) is not needed. I’ll definitely be using this for any system that requires high performance frame-by-frame event dispatching.

    The uniqueness of the event IDs is a serious problem especially for AS3 programmers that don’t use macros, and equally bad for haxe developers that prefer to stay away from macros. You might want to create a static function to generate unique IDs or a better way to partition IDs (perhaps a category ID as a hack)?

    Best, Jonathan Dunlap

    1. Michael

      The problem with generating ids at run-time with a static function is that event types can’t be inlined because they are not constant anymore so the result will be much slower.

  3. hrmm.. good point. What about two identifiers for the event- a type Int and an event ID Int. While it’s an extra comparison, it does allow each class to ‘partition’ its own event space.

Get Adobe Flash player