Share 'Collections framework performance comparison' on Delicious Share 'Collections framework performance comparison' on Facebook Share 'Collections framework performance comparison' on Google Bookmarks Share 'Collections framework performance comparison' on Twitter

  1. Note to the performance tests in this article
  2. Linked list
  3. Map
  4. Set
  5. Binary search tree
  6. Priority queue
  7. Sorted list
  8. Comments (3)
  9. Leave a Comment

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.

+ add
+A addFirst
Z+ addLast
- remove
-A removeFirst
Z- removeLast
? has
?k hasKey
-k removeKey

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.

TestCase +A Z+ -A Z-
5000 Items
AS3Commons LinkedList 1 1 0 0
Dpdk LinkedList 1 1 0 0
Polygonal DLinkedList 5 3 0 0
10000 Items
AS3Commons LinkedList 4 2 0 0
Dpdk LinkedList 2 2 0 0
Polygonal DLinkedList 6 8 0 0
50000 Items
AS3Commons LinkedList 16 16 1 1
Dpdk LinkedList 17 17 1 1
Polygonal DLinkedList 34 34 1 1
100000 Items
AS3Commons LinkedList 28 28 3 3
Dpdk LinkedList 27 26 3 3
Polygonal DLinkedList 69 81 3 3

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.

TestCase + ?k -k
5000 Items
AS3Commons Map 2 0 3
Dpdk HashMap 15 6 6
Polygonal HashMap 3 1 3
10000 Items
AS3Commons Map 3 2 7
Dpdk HashMap 28 13 14
Polygonal HashMap 7 1 6
50000 Items
AS3Commons Map 20 8 54
Dpdk HashMap 186 70 91
Polygonal HashMap 36 4 69
100000 Items
AS3Commons Map 48 16 166
Dpdk HashMap 432 201 232
Polygonal HashMap 87 10 171

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.

TestCase + ? -
5000 Items
AS3Commons Set 1 1 2
Dpdk Set 1 0 1
Polygonal Set 1 0 1
10000 Items
AS3Commons Set 3 2 5
Dpdk Set 2 0 3
Polygonal Set 2 1 3
50000 Items
AS3Commons Set 16 7 28
Dpdk Set 10 2 30
Polygonal Set 13 4 30
100000 Items
AS3Commons Set 29 16 138
Dpdk Set 25 4 85
Polygonal Set 27 9 90

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.

TestCase + ? -
1000 Items
AS3Commons Treap 11 9 13
Dpdk BST 14 14 12
Polygonal BST 11 21 -
5000 Items
AS3Commons Treap 67 59 101
Dpdk BST 86 84 76
Polygonal BST 72 127 -
10000 Items
AS3Commons Treap 149 131 239
Dpdk BST 216 215 194
Polygonal BST 171 320 -

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.

TestCase + ? -
1000 Items sorted
AS3Commons Treap 7 8 15
Dpdk BST 602 592 285
Polygonal BST 477 468 -
5000 Items sorted
AS3Commons Treap 37 60 104
10000 Items sorted
AS3Commons Treap 84 131 259

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

TestCase + -A
5000 Items
AS3Commons Treap 65 3
Dpdk PriorityQueue 14 116
Polygonal Heap 12 99
10000 Items
AS3Commons Treap 142 7
Dpdk PriorityQueue 30 262
Polygonal Heap 24 221
50000 Items
AS3Commons Treap 896 38
Dpdk PriorityQueue 157 1658
Polygonal Heap 132 1351

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.

TestCase + ? - -A Z-
500 Items
AS3Commons SortedList 3 4 4 0 0
Dpdk OrderedList 195 4 3 0 0
1000 Items
AS3Commons SortedList 8 8 8 0 0
Dpdk OrderedList 783 8 8 1 1
2000 Items
AS3Commons SortedList 19 16 17 1 0
Dpdk OrderedList 3174 19 19 3 2
10000 Items
AS3Commons SortedList 123 104 114 25 0
50000 Items
AS3Commons SortedList 1015 620 998 777 1

AS3Commons SortedList tests source code
Dpdk OrderedList tests source code



3 Comments

  1. AS3Commons Collections framework - Flashforum

    4. Mai 2010

    [...] [...]

  2. rolf vreijdenberger

    13. Mai 2010

    Hi Jens,

    great work, thanks for doing this and for spreading this information. Guess we’ll have to do some work @ dpdk to see if we can shave off some milliseconds here and there :)

    cheers

  3. Glidias

    22. Juni 2011

    Nice, i’m using this as reference. You forgot that Polygonal’s PriorityQueue can run under Haxe as a Generic as well with inlining, allowing strictly typed data binding (and spill-out code generation) for faster performance. PriorityQueue could also do with testing for remove(data:*).

Leave a Comment

You have a question or have experienced an issue? Please post it in the forum: http://sibirjak.tenderapp.com/ in order to make the discussion available at a more central place.