AS3 arrays against linked lists performance benchmarking

0 Flares Twitter 0 Facebook 0 Google+ 0 Pin It Share 0 Email -- Filament.io 0 Flares ×

Let’s have a look at arrays vs. linked lists, and for what use.
Here, the assumption is that we need to access a property and/or call a function from a lot of objects in a list at the highest speed possible. Let’s say we are making a game and we want to go through all of our animated sprite objects.

Basically, we have two options:

  1. Arrays
  2. Linked lists

Arrays

Commonly used, arrays are easy to manipulate. You just need to iterate through it and access each object via its index in the list. For a loop performance test refer to this article.  In AS3, object access is supposedly faster than array access, which we will verify later.

Linked list

In a linked list, objects are linked together. Basically, there is no index to access data (even if that can be implemented) but each object in the list has a reference to the next object (single) or to the previous one as well (double). Well this is just the idea behind linked lists. You can have as many references as you want depending on the use of the objects.
Linked lists also allow us to add and remove objects from the list in a fast and easy way.

But let’s have a look at the results I got with an iteration of 1000000 :

Action

time

inserting new element (class instance, string passed to constructor) into array 969 ms
inserting new element (string passed to constructor) into linked list 645 ms
inserting new element (string passed to property) into linked list 757 ms
accessing text (string, property) from array element (class instance) 32 ms
accessing text (string, property) from linked list 28 ms
accessing text (string, function) from linked list 97 ms
writing into 4 properties (string) from array element (class instance) 55 ms
reading from 4 properties (string) from array element (class instance) 56 ms
writing into 4 properties in linked list 51 ms
reading from 4 properties in linked list 52 ms

My configuration is:
Intel Core2 6400  @ 2.13GHz, 3Go Ram, WinXP.

I ran the test multiple times. It is weird because sometimes, arrays are like 3 times faster than linked lists… but the results are too high compared to what I have “normally”. The results in the table above reflect what I get most of the time.

Conclusion

Well, linked lists seem to be slightly faster but no big difference here… and there are 1.000.000 objects, which is pretty big. So with less objects in the list, the difference would be even smaller.

The tool I used is right here for you to test. Keep in mind that the results might change from time to time and from computer to computer.

Get Adobe Flash player

0 Flares Twitter 0 Facebook 0 Google+ 0 Pin It Share 0 Email -- Filament.io 0 Flares ×

6 Comments

  1. intel core 2 6400

    50000 :

    inserting new element (class instance, string passed to constructor) into array: 20 ms – results :
    inserting new element (string passed to constructor) into linked list: 28 ms – results :
    inserting new element (string passed to property) into linked list: 23 ms – results :
    accessing text (string, property) from array element (class instance): 1 ms – results :
    accessing text (string, property) from linked list: 8 ms – results :
    accessing text (string, function) from linked list: 7 ms – results :
    writing into 4 properties (string) from array element (class instance): 14 ms – results :
    reading from 4 properties (string) from array element (class instance): 14 ms – results :
    writing into 4 properties in linked list: 2 ms – results :
    reading from 4 properties in linked list: 2 ms – results :
    accessing text (string, property) from array element (class instance) for each loop: 74 ms – results :

    100000 :

    inserting new element (class instance, string passed to constructor) into array: 57 ms – results :
    inserting new element (string passed to constructor) into linked list: 55 ms – results :
    inserting new element (string passed to property) into linked list: 51 ms – results :
    accessing text (string, property) from array element (class instance): 7 ms – results :
    accessing text (string, property) from linked list: 18 ms – results :
    accessing text (string, function) from linked list: 12 ms – results :
    writing into 4 properties (string) from array element (class instance): 22 ms – results :
    reading from 4 properties (string) from array element (class instance): 5 ms – results :
    writing into 4 properties in linked list: 4 ms – results :
    reading from 4 properties in linked list: 5 ms – results :
    accessing text (string, property) from array element (class instance) for each loop: 151 ms – results :

    1000000 :

    inserting new element (class instance, string passed to constructor) into array: 606 ms – results :
    inserting new element (string passed to constructor) into linked list: 581 ms – results :
    inserting new element (string passed to property) into linked list: 566 ms – results :
    accessing text (string, property) from array element (class instance): 27 ms – results :
    accessing text (string, property) from linked list: 24 ms – results :
    accessing text (string, function) from linked list: 27 ms – results :
    writing into 4 properties (string) from array element (class instance): 49 ms – results :
    reading from 4 properties (string) from array element (class instance): 50 ms – results :
    writing into 4 properties in linked list: 46 ms – results :
    reading from 4 properties in linked list: 47 ms – results :
    accessing text (string, property) from array element (class instance) for each loop: 1509 ms – results :

    5000000 :

    inserting new element (class instance, string passed to constructor) into array: 3935 ms – results :
    inserting new element (string passed to constructor) into linked list: 2401 ms – results :
    inserting new element (string passed to property) into linked list: 3518 ms – results :
    accessing text (string, property) from array element (class instance): 421 ms – results :
    accessing text (string, property) from linked list: 712 ms – results :
    accessing text (string, function) from linked list: 713 ms – results :
    writing into 4 properties (string) from array element (class instance): 1006 ms – results :
    reading from 4 properties (string) from array element (class instance): 1398 ms – results :
    writing into 4 properties in linked list: 1245 ms – results :
    reading from 4 properties in linked list: 1606 ms – results :
    accessing text (string, property) from array element (class instance) for each loop: 22817 ms – results :

  2. For my current project I need to be able to remove random items from random indexes in a large array. For this the use of LinkedList would be much more efficient than Arrays.

  3. Paul

    Intel Core 2 Duo P8400 @ 2.26 GHz and 4GB DDR3 RAM – Win 7

    inserting new element (class instance, string passed to constructor) into array: 37 ms – results :
    inserting new element (string passed to constructor) into linked list: 24 ms – results :
    inserting new element (string passed to property) into linked list: 50 ms – results :
    accessing text (string, property) from array element (class instance): 7 ms – results :
    accessing text (string, property) from linked list: 11 ms – results :
    accessing text (string, function) from linked list: 11 ms – results :
    writing into 4 properties (string) from array element (class instance): 18 ms – results :
    reading from 4 properties (string) from array element (class instance): 22 ms – results :
    writing into 4 properties in linked list: 21 ms – results :
    reading from 4 properties in linked list: 25 ms – results :
    accessing text (string, property) from array element (class instance) for each loop: 227 ms

  4. HP Compaq 8510W
    Intel Core 2 Duo CPU
    T9500 @2.6GHz
    2.59GHz 3GB RAM

    #100000
    ——-
    inserting new element (class instance, string passed to constructor) into array: 106 ms – results :
    inserting new element (string passed to constructor) into linked list: 154 ms – results :
    inserting new element (string passed to property) into linked list: 24 ms – results :
    accessing text (string, property) from array element (class instance): 7 ms – results :
    accessing text (string, property) from linked list: 7 ms – results :
    accessing text (string, function) from linked list: 8 ms – results :
    writing into 4 properties (string) from array element (class instance): 14 ms – results :
    reading from 4 properties (string) from array element (class instance): 15 ms – results :
    writing into 4 properties in linked list: 15 ms – results :
    reading from 4 properties in linked list: 13 ms – results :
    accessing text (string, property) from array element (class instance) for each loop: 227 ms – results

    #5000000
    inserting new element (class instance, string passed to constructor) into array: 2463 ms – results :
    inserting new element (string passed to constructor) into linked list: 2742 ms – results :
    inserting new element (string passed to property) into linked list: 2626 ms – results :
    accessing text (string, property) from array element (class instance): 343 ms – results :
    accessing text (string, property) from linked list: 817 ms – results :
    accessing text (string, function) from linked list: 494 ms – results :
    writing into 4 properties (string) from array element (class instance): 526 ms – results :
    reading from 4 properties (string) from array element (class instance): 900 ms – results :
    writing into 4 properties in linked list: 732 ms – results :
    reading from 4 properties in linked list: 1055 ms – results :
    accessing text (string, property) from array element (class instance) for each loop: 7956 ms – results :

  5. Paul

    It really depends on what you are doing with the array. Linked lists are faster to iterate and therefore are faster to populate & search. They are magnitudes faster at slicing or splicing. And they are just as fast at doing the simple push/pop stuff.

    For 1M class instances:

    arr init 459
    LL init 387
    for each 28
    for i 16
    LL each 9
    arr find last 159 (10 times)
    arr indexOf last 176 (10 times)
    LL find last 65 (10 times)
    arr remove mid 311 (1000 times)
    arr remove front 875 (1000 times)
    arr remove end 0 (1000 times)
    LL remove 0 (1000 times)

    Without seeing your code its difficult to see exactly what you are doing. If you are doing repeated array modification then use a linked list – and you\’ll get a speed boost across the board as well, as iterating is faster.

Leave a Comment

*