In the last article I have shown how custom collections handle specific programmig problems more efficiently than the built-in data containers Array and Dictionary. I have named a number of common collections which are part of almost every collections library. In this post I am going to compare the performance of such collections from 3 different libraries.

• AS3Commons Collections Version 1.0.0
• Dpdk open source Revision 272
• Polygonal datastructures Version 1.04
  The ActionScript version of the polygonal data structures is not further developed and has been ported to the haXe language with the claim to be faster. However, some of the haXe structures did not support primitive values (Heap, BST), so I test here the last ActionScript version.

Note to the performance tests in this article

This article contains a number of performance test results. The tests have been executed using a small testing harness which can be found at the sibirjak google code page. The column header of the tables showing those results use the following abbreviations. The measured time is displayed in milliseconds.

Linked list

The performance of the A3Commons and Dpdk lists is nearly equal. Adding to the polygonal list takes twice the time than to the others.

AS3Commons LinkedList tests source code
Dpdk LinkedList tests source code
Polygonal DLinkedList tests source code

Map

The AS3Commons and polygonal maps use an internal Dictionary. The dpdk map instead implements a custom hash table (which is of course slower). The dpdk map only allows literal keys. The AS3Commons map consideres mixed typed primitive keys (1 != “1″) which the polygonal map treats as equal. The polygonal map stores its items additionally in a linked list to create an iterator in constant time. The other maps populate an array and return then an iterator over that array (linear time).

The Dictionary key type issue is described in the Dictionary discussion.

AS3Commons Map tests source code
Dpdk HashMap tests source code
Polygonal HashMap tests source code

Set

All sets are backed by a Dictionary instance. In difference to the others, the AS3Commons set distinguishes between numeric and literal keys of the same value (1 != “1″) wich makes it slightly slower.

The Dictionary key type issue is described in the Dictionary discussion.

AS3Commons Set tests source code
Dpdk Set tests source code
Polygonal Set tests source code

Binary search tree

The polygonal tree did throw errors when trying to remove items. The performance of removals could therefore not be tested.

The AS3Commons Treap is a randomised tree with a weak addiction to degenerate. Both other trees are neither randomised nor balanced. Adding already sorted data causes here the tree to make up a sequence where each node has only one child.

AS3Commons Treap tests source code
Dpdk BST tests source code
Polygonal BST tests source code

Priority queue

A priority queue provides fast access to the lowest (or highest) item. Dpdk and polygonal contain a arrayed heap implementation. A heap is probably the fastest way to solve the problem. Using an arrayed heap has to consider the time to shift all succeeding array elements when removing the first. The AS3Commons Treap is expensive in adding items but fast in removing (and has a better cumulative performance).

AS3Commons Treap tests source code
Dpdk PriorityQueue tests source code
Polygonal Heap tests source code

Sorted list

Both tested lists use an array with a binary search algorithm. However, the dpdk list applies a full sort after each insertion operation which is exeptional slow.

AS3Commons SortedList tests source code
Dpdk OrderedList tests source code