Linked list performance

It’s a fact that haXe creates swf files running faster compared to mxmlc. Amazingly, haXe is also faster at compile time. But to which extent are haXe generated swf files faster? Optimizing code especially pays off for “low-level stuff” like data structures, the building blocks of many algorithms. With this in mind, I picked the doubly linked list class from my ds library (extensively used in almost all my projects) and played around with different optimization levels to figure out how those translate into run time improvements of the flash platform.

So, which options do we have?
First, we can create “true generic classes” at compile time by adding -D generic to the haXe command line. We gain almost 40%. Why? Because we get rid of dynamic access (*) – perfect for AVM2, which is a statically typed runtime. You can read more about this here.
Next, let’s turn on function inlining, so we don’t have to deal with the overhead of calling many small functions. Inlining is always enabled by default, but you can turn it off by compiling with --no-inline, just so you can see the difference. This increases performance by another 70%.
So far we have twice the performance, thanks to smart compiler optimizations. Regarding linked lists (and many other linked structures in ds) we have one secret weapon left: “node caching”, a feature that was introduced in ds version 1.12 back in 2010. By passing a size parameter to the constructor we can reserve additional memory to minimize costly instantiation of linked list nodes:

var reservedSize = 1000;
var list = new de.polygonal.ds.DLL(reservedSize);

From now on, every time you remove an element from the list, the node object storing that element is kept for later reuse – ready to store another incoming element. The resulting behavior is an incrementally filled object pool. And don’t worry if the size exceeds the predefined size – in this case objects are simply created on-the-fly. And here are the final numbers:

benchmark results

Notice that due to additional bytecode instructions for debugging, input validation and assert statements the debug build is awfully slow, so better not use it for deploying your application ;). The release build is effectively what you get when compiling ds_release.swc with mxmlc, on par with other libraries like the LinkedList class found in the as3commons Collection package. Actually, haXe compiled SWC files are a bit faster because the generated bytecode is more efficient and private methods are still inlined, but in order to unleash the full potential of the flash player there is currently no way around haXe.

About “-D generic”

This is a custom conditional compilation switch which is available in ds. If defined, classes defining linked structures will implement the marker interface haxe.rtti.Generic. This tells the compiler to create specialized classes for each type parameter. Here is a simplified example:

class Container
#if generic
implements haxe.rtti.Generic
#end
{
    public var value:T;
    public function new() {}
}

If we create an object of type Container like so…

var myFloatContainer = new Container();

…the compiled result will look like this…

class Container_Float
{
    public var value:Float;
    public function new() {}
}

…instead of:

class Container
{
    public var value:Dynamic;
    public function new() {}
}

Now everything is strictly typed and we don’t need slow dynamic access.

A* pathfinding with ds

I recently did a complete rewrite of my graph-based A* pathfinder example because I received a lot of questions on how to implement path-finding using the new ds library. So here is an updated demo that works with ds 1.32:

Interactive demo: A* pathfinding with ds

I’m transforming the point cloud with delaunay triangulation into a graph structure. Then the system computes and draws the shortest path between two selected points.

Compile instructions

Running and examining the example is really easy:

  1. Use the automated installer to install haXe from http://haxe.org/download.
  2. Download the latest haXe nightly build and overwrite the existing ‘haxe.exe’ and ‘std’ folder with the downloaded version.
  3. Install the polygonal library by opening the command prompt and typing:
    $ haxelib install polygonal.
  4. Sources should now be in {haxe_install_dir}/lib/polygonal/1,18/src/impl/sandbox/ds/astar, where {haxe_install_dir} is usually C:/Motion-Twin/haxe on Win7.
    The demo can be then compiled with:
    $ cd C:\Motion-Twin\haxe\lib\polygonal\1,18\build
    $ haxe.exe compile-ds-examples.hxml

Extending the Graph class

You have basically two options to extend the functionality of the Graph object: by composition or inheritance. While I highly recommend to use composition whenever possible, I’ve also included a version using inheritance – just so you see the difference.

The composition version looks like this:
A* using composition

The Graph object manages GraphNode objects, and each GraphNode holds a Waypoint object, which defines the world position of the waypoint as well as intermediate data used by the A* algorithm. Notice that GraphNode and Waypoint are cross-referencing each other as a Waypoint object has to query the graph for adjacent nodes. As a result, you have a clean separation between the data structure (Graph, GraphNode) and the algorithm (AStar, Waypoint) and don’t need object casting, which is good news because casting is a rather slow operation.

Now let’s look at the version using inheritance:
A* using inheritance
Here, Waypoint directly subclasses GraphNode. Since the Graph is defined to work with GraphNode objects, we need a lot of (unsafe) down-casts to access the Waypoint class. Furthermore, the use of haxe.rtti.Generic will be very restricted or even impossible (implementing this marker interface generates unique classes for each type to avoiding dynamic).