Sep
27
10
Come again?
For fun, I recently wrote the “asynchronous dependency graph” — it elegantly handles and executes asynchronous function calls with dependencies. In reality, though, it is little more than a dressed-up directed graph. But for those without a background in Computer Science or graph theory:
Some foundational concepts
AS3 is event-driven. A classic example for this is downloading an external file.
Say we have an external file sitting somewhere: “http://www.williamchou.com/file.txt”. To load the contents of that file in AS3, we’d do something like this:
var url:String = "http://www.williamchou.com/file.txt";
var loader:URLLoader = new URLLoader();
loader.addEventListener(Event.COMPLETE, loadComplete);
loader.load(new URLRequest(url));
function loadComplete(e:Event):void {
trace(e.target.data);
}
No problem. Now let’s say I want to parse the contents of “file.txt” and load another external file based on those contents (e.g. file.txt contains URLs to other files). This is still pretty simple to write:
// Load [A].
function loadedA(e:Event):void {
var loaderB:URLLoader = new URLLoader();
loaderB.addEventListener(Event.COMPLETE, loadedB);
loaderB.load(new URLRequest(e.target.data));
}
function loadedB(e:Event):void {
// ...
}
The problem at hand
Now, what if instead of parsing “file.txt” and loading the second file from the loadedA() callback, we want to cross-check this second URL with a value from another external file that we’ll call [C] (e.g. the URLs in the external files are time-stamped and we want the most recent one).
We can’t directly call the load in the callback for [A] since we need to make sure that [C] has been loaded a priori.
Serializing the calls into some sequential order is a solution that yields straightforward code, but comes with a high performance cost – you can only make one concurrent asynchronous call. The more performant solution considers that now there are two possibilities: either [A] loads first or [C] loads first, so we could duplicate the logic for [B] in both the callbacks for [A] and [C]:
var aHasLoaded:Boolean = false;
var cHasLoaded:Boolean = false;
function loadedA(e:Event):void {
// ...
aHasLoaded = true;
if (cHasLoaded) {
// Load [B].
}
}
function loadedC(e:Event):void {
// ...
cHasLoaded = true;
if (aHasLoaded) {
// Load [B].
}
}
Uhoh, this is getting ugly because:
1. Code duplication: since we’re not sure of the order of events, we duplicate the logic for [B].
2. Use of unwieldy boolean flags: needed to enforce the dependency of events, but not a very readable solution.
There’s a way to do this better!
A solution
Enter the asynchronous dependency graph. It does the work of checking and executing asynchronous function calls with dependencies for you with a little bit of graph theory.
We can represent an asynchronous function call as a node in a graph. A dependency between functions is represented as a directed edge between two nodes in the graph; a directed edge (n1, n2) means that node “n1″ is dependent on node “n2″. That is, the function call represented by “n1″ can only be executed after the function call represented by “n2″ has returned. In the prior example, we had function calls [A] and [C], both of which [B] were dependent on. We can represent this as a simple three-node graph:
It becomes apparent that nodes that are free to be immediately called are those without any outgoing edges. Then, an algorithm for graph traversal (or equivalently, calling all of the functions in some non-sequential order such that all dependencies are satisfied) too becomes apparent:
1. For a graph G, find all nodes that have no outgoing edges. Call this set of nodes S.
2. While S is not empty, do:
2.1. Pick any node N in S.
2.2. Remove N from G. Remove all edges (?, N) from G.
2.3. Add any nodes in N that now have no outgoing edges to S.
Note that this is exactly a topological sort.
An optional third step is to check for any nodes left in G – those nodes that still reside in G are part of a cycle. The asynchronous dependency graph also implements functionality to check for cycles prior to traversal (since nodes with cyclical dependencies will never get executed).
View the code – AsyncDependencyGraph.as and Node.as.
Footnote: if we’re writing AS3 for public consumption on some server, we would have to consider cross domain policy when performing HTTP requests to servers sitting on different domains.