Introduction to ds

“Introduction to ds” is a slide presentation/manual about ds which I started last year. I never had enough time to finish it quickly so I wrote it now and then and just recently finished it.

The presentation explains the concepts and design decisions behind ds, provides short code examples to demonstrate basic usage and covers each data structure in a few words. I tried to squeeze in as much information as possible but due to the complexity of the topic it’s impossible to go into detail – each data structure alone could easily fill a presentation…

Code examples are all in haXe language, but converting to AS3 is simply a matter of removing type parameters <T> and renaming Int to int, Float to Number and so on.

“Introduction to ds” (pdf)

Or watch it on

I hope you find it useful! (if you are an experienced game programmer you will be probably bored ;))

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<T>
#if generic
implements haxe.rtti.Generic
    public var value:T;
    public function new() {}

If we create an object of type Container like so…

var myFloatContainer = new Container<Float>();

…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.