Wednesday, July 7, 2010

Performance-Improving Techniques Employed in CJSignals

CJSignals project homepage

CJSignals is an observer framework I released a couple of days ago, based on Robert Penner's AS3 Signals.

For some performance comparison of the native event system, CJSignals, and AS3 Signals, you may check out my previous post. Here I'm going to describe the performance-improving techniques employed in CJSignals.

This technique can also be employed elsewhere when massive objects are added and removed from an array very rapidly, where the array must be sorted and performance is vital. Rusher also uses this technique to manage prioritized active components.

Listener Array

For each listener functions added, a corresponding ListenerData object is created and stored in the internal array, which contains a reference to the listener, a boolean variable indicating whether the listener is a one-time listener, and an integer variable for keeping track of the index of the ListenerData object in the array. Also, a mapping relation between the listener and the ListenerData object is added to an internal dictionary for fast lookup.

Adding Listeners

CJSignals keeps track of the index of the first empty cell of the listener array with an integer variable, i.e. keeping track of the first null element. When a new listener is added, its corresponding ListenerData object is inserted to the array cell corresponding to the index, and then the index is incremented by 1. If the array is full, then its size is doubled. This approach assigns elements directly to an array cell by index, instead of invoking Array.push() every time a new listener is added.

Removing Listeners

Listeners can be removed from the array very efficiently. When a listener is removed from a signal, the listener dictionary is used to quickly retrieve the listener's corresponding ListenerData object. From the ListenerData object, the index of the object in the array can then be obtained (A). The index of the first empty cell is decremented by 1, thus pointing to the last non-null element (B). Cell A's content is replaced by cell B's, and cell B's content is replaced with a null value, so the first-null-element index is now keeping track of the new first null element.

Priority Sorting

Adding and removing listeners sets a listener-array-dirty flag to true, indicating the necessity to sort the listener array according to the listener priorities. The sorting is not necessary until the next signal dispatch or retrieval of the internal listener array through the public getter method get listeners(), the flag set back to false afterwards. Thus, multiple calls to the Signal.add() and Signals.remove() methods do not cause the array to be re-sorted; it is deferred to the point when the sorting is really necessary. After the array is sorted, the ListenerData objects are informed of and updated with their new indices.

I guess the native event system sorts the array every time a new listener is added, resulting in the huge performance difference between the system and CJSignals.

One good thing about the Array.sort() method is that it always pushes null elements to the tail of the array, so it's okay to keep a sparse array, as long as the index of the first null element is kept track of.

Sunday, July 4, 2010

CJSignals - My New Observer Framework

CJSignals project homepage

You might be able to tell from the project name that this project is inspired by Robert Penner's AS3 Signals. Yes, this is the case, indeed.

I've studied C# before, and played with Qt in the last semester. I felt the same thing Robert felt about the Event System in C# and the Signals/Slots System in Qt. It makes much more sense to extend an observer framework with composition rather than inheritance, and it makes code cleaner and more comprehensible if an object dispatches events of just one type, which is not the case for the ActionScript 3.0 native event dispatchers, for they can dispatch multiple types of events.

With CJSignals, each type of event corresponds to a Signal object "owned", a term for composition, by the subject. For instance, you can write code like this.

The parameter types of the listener matches those specified in the signal constructor. For information on the actual usage, you may check out the tutorial wiki page.

I built CJSignals from the ground up, using my own implementation of signals to boost performance, mainly performance concerning listener priority management and listener removal. I used the fast-splicing array technique I mentioned in this post, which is also employed by Rusher for active component priority management. And the priority sorting is only executed upon signal dispatch and if necessary.

Here's a comparison chart of the performance for the native event system, CJSignals, and AS3 Signals. Although CJSignals places second or third in some tests, the actual numerical results do not pose as bottleneck. What is more important is that CJSignals has the best worst-case performance: the worst test result for CJSignals is merely 13ms, whereas that for the native event system is 681ms, and AS3 Signals 5717ms.