Tamarin part I : AS3 Array

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

//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.
Bad.

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.

Conclusion:

• 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:

http://gskinner.com/talks/quick/#65
http://livedocs.adobe.com/flash/9.0/ActionScriptLangRefV3/Array.html
For even more information: read the Tamarin C++ source!

Coming soon: even more Tamarin advanced topics!