Skip to content

Tamarin part I : AS3 Array

December 2, 2009

Here is a little experiment:

private function InitializeArray() : void
var i:int = 0, myArray:Array = new Array();
for (i = 0; i < 100000; i++) { myArray[i] = i; }
private function InitializeArrayBackward() : void
var i:int = 0, myArray:Array = new Array();
for (i = 100000; i >=0; i--) { myArray[i] = i; }

When testing those two functions in GSkinner PerformanceTest, I get this:
InitializeArray : 11 ms
InitializeArrayBackward : 44 ms

There is something very important to understand when using the Array class.
If you read the Tamarin source code you will discover that Array is made of multiple things:

  • ArrayObject is using two data structure at the same time
  • 1: A dense array (like Vector class)
  • 2: A HashTable (like Object class)

To simplify this text, lets use “DA” for “dense array” and “HT” for “HashTable”

The DA is from index zero to X (X being the first index where there is no element). After that, its all HT.

so if you do:

myArray = new Array();
myArray[0] = 1;
myArray[1] = 1;
myArray[3] = 1;

The first two values are stored in DA, and the third one is put in a HT.
Basically, flash is saying:

If the index lower than the DA size
Put data in DA
if index = DA size
Grow DA and add it to the end
if index is bigger than DA size
Put in HT

But, the code also implements a mechanism to optimize the array when possible. It’s called: “checkForSparseToDenseConversion”. This process take a look at the index next to the one we just added and verify if there is a index stored in the HT that match this new DA length. If there is (index+1) in the HT, get it back to the DA, and remove it from HT. Any operation that will add to the end of the DA will have to do this check.

What does it mean? It means that if you insert element from 10000 to 0, it’s going to call “checkForSparseToDenseConversion” 9999 times doing nothing, and then at the last call, it’s going to see that index 0 can be added to an empty DA! Then it will add it as the first element of the DA, and will loop “checkForSparseToDenseConversion” until there is no (index+1) element in the HT (…but they all do). So it’s going to transfer each value (one at a time) from the HT to the DA. GREAT! A nice 23 ms operation well spared (for a single pass!).

But the problem is not only for insertion of value, it’s for reading them too. Reading values in a HT is much slower than direct indexation (in the DA).

//Initializing all value from 0 to 100000
myArray = new Array();
for (i = 0; i < 100000; i++) { myArray[i] = i; }

Then do a PerformanceTest like this one:

//Read all value of the array (but do nothing with them)
private function TestIterationSpeed() : void {
var len:int = myArray.length, val:int = 0;
while (len-->=0) { val = myArray[len]; }

PerformanceTest result: 2.7ms

If you change a bit the initialization to exclude the first element (0) then the whole array won’t be eligible for the DA.

//Skipping index 0
myArray = new Array();
for (i = 1; i < 100000; i++) { myArray[i] = i; }

PerformanceTest result:: 5.9 ms !!
That’s 2.18x more for each read!

But then again, the DA versus HT of the Array is not only limited to insertion of values at specific index.  If you “delete” an index, its going to do the same thing: keep the low part in DA, and put the upper part in the HT.
So again:

//full initialization
for (i = 0; i < 100000; i++) { myArray[i] = i; }

And then: delete myArray[3];

So now we have a DA of 3 element (0,1,2) and a hash table of 99997 element.

So now if you say “use the constructor argument to specify the length”.
Never saw any difference.

And if you say use “myArray.length = 100000”.
Doesn’t change a thing.


  • The goal of the Array class is to take a minimum amount of memory for a sparse array.
  • Using HT is a good way to do that, but access speed is affected.
  • Since “most” arrays are from 0 to X, the DA is doing a good job.
  • The “checkForSparseToDenseConversion” is a bit tricky and could cause lag for very big arrays.
  • Deleting an element of an array is a bad idea! (better nulling it off)
  • Pushing, Poping and splicing elements never cause problem.
  • For a faster read/write use typed vector class. (always DA)

For more on AS3 Arrays:
For even more information: read the Tamarin C++ source!

Coming soon: even more Tamarin advanced topics!

add to del.icio.usAdd to Blinkslistadd to furlDigg itadd to ma.gnoliaStumble It!add to simpyseed the vineTailRankpost to facebook

From → actionscript

  1. Jean-Philippe,

    Thanks for the interesting article. It got me thinking, and as a confirmation of your work I thought it’d be interesting to consider the case where you use an Object as an Array. Since there would be no DA it should run faster. On the performance harness, mapTest runs twice as quickly as arrayTest:

    public function arrayTest():void
    var arr:Array = [];

    var i:int = 100000;
    while (–i > -1)
    arr[i] = “test”;

    public function mapTest():void
    var obj:Object = {};

    var i:int = 100000;
    while (–i > -1)
    obj[i] = “test”;

    • try the same thing but stop at index=1
      while (–-i > 1)

      There should be no or almost no difference. maybee the object will be a bit faster.

      the “twice as fast” is due to the checkForSparseToDenseConversion wich is REALLY slow for a backward array!

  2. When running the test here you are comparing a single operator conditional loop (i=0). Although usually negligible, with an identical for-loop, say: i<100000 and i-1; i–) { myArray[i] = i; }

  3. This is an excellent article and a real eye-opener too. It’s inspired me to write an article elaborating on the subject. It’ll be available tomorrow (Monday) on my site here:

    Thanks for the article and the blog. Although you’ve just begun, you already have three killer articles. Keep up the great work!

  4. Arwid permalink

    Hey, great stuff, really interesting.

    But.. Im getting a very very very annoying runtime error from your code highlight thingy everytime I drag my mouse over them.

    Error #2044: Unhandled IOErrorEvent:. text=Error #2036: Load Never Completed.

    Regards, Arwid.

  5. Great article. I did not know AS3 Arrays were implemented internally in this way. This will definitely influence my design decisions when architecting Flex apps.

Trackbacks & Pingbacks

  1. Reverse engineering AMF3 Vector for Java « jpauclair
  2. Tamarin part II – More on Array and Vector « jpauclair
  3. AS3 hidden treasure in the mm.cfg file. Revealing and documenting many Flash secrets! « jpauclair
  4. 6 Months – Articles recap. « jpauclair

Comments are closed.

%d bloggers like this: