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.

No comments: