This is the result of this thread about particles.
So the question was which data structure is faster in AS3 when iterating through the entire set, the array or the list. Many, including me, where of the opinion that an array should be faster on account of the horrible system cache behaviour of lists, even though information theoretically they both have linear iteration time. The other opinion was that the ability to type values in lists would make them faster.
The test:
I started with two setups, timing first the precaching of the sets, and then iterating through them and getting the one number stored.
Those two sets where:
<ul>
<li>An array with objects
I chose to have an array with objects since that seems like the most useful and usual way to have things if I want to store more than a single value in each object.
The objects:
package {
public class SpeedTestObj {
public var nbr:Number;
}
}
</li> <li>A list with objects
package {
public class SpeedTestObjList {
public var nbr:Number;
public var next:SpeedTestObjList = null;
}
}
</li>
</ul>
With these I set up the follow testing code:
import flash.utils.getTimer;
var timer:uint;
var nbrOfObjects:uint = 1000000;
var i:int;
var s:Number;
timer = getTimer();
var objArr:Array = new Array(nbrOfObjects);
var obj:SpeedTestObj;
for (i=0; i<nbrOfObjects; i++) {
obj = new SpeedTestObj();
obj.nbr = i;
objArr[i] = obj;
}
trace("creating "+i+" object array: "+(getTimer()-timer));
timer = getTimer();
var objList:SpeedTestObjList = new SpeedTestObjList();
var first:SpeedTestObjList = objList;
first.nbr = 0;
for (i=1; i<nbrOfObjects; i++, objList = objList.next) {
objList.next = new SpeedTestObjList();
objList.next.nbr = i;
}
trace("creating "+i+" object list: "+(getTimer()-timer));
timer = getTimer();
for (i=0; i<nbrOfObjects; i++) {
s = objArr[i].nbr;
}
trace("getting Number from "+i+" objects in array: "+(getTimer()-timer));
timer = getTimer();
objList = first;
while (objList != null) {
s = objList.nbr;
objList = objList.next;
}
trace("getting Number from "+i+" objects in list: "+(getTimer()-timer));
The result? (times in ms)
creating 1000000 object array: 520
creating 1000000 object list: 472
getting Number from 1000000 objects in array: 129
getting Number from 1000000 objects in list: 16
Earth shattering victory for the list! There's no arguing against those numbers.
But wait a moment, the list is coded for this exact application while the array is übergeneric?
New hypothesis: The adding of objects to a list is actually the adding of pointers to other places in memory where the objects are, which then gives as bad space locality to the array as to the list, but with the overhead of the extra array look up this goes slower.
But what if but the numbers directly into the array? Numbers aren't pointers and should therefore allow better cache performance through space locality.
Testing:
timer = getTimer();
var nbrArr:Array = new Array(nbrOfObjects);
for (i=0; i<nbrOfObjects; i++) {
nbrArr[i] = i;
}
trace("creating "+i+" Numbers in array: "+(getTimer()-timer));
timer = getTimer();
for (i=0; i<nbrOfObjects; i++) {
s = nbrArr[i];
}
trace("getting Number from "+i+" Numbers in array: "+(getTimer()-timer));
Result: (in ms)
creating 1000000 Numbers in array: 67
getting Number from 1000000 Numbers in array: 36
The creation time is no suprise much lower since there is no need to find new memory space for a million objects.
But the getting time is still double the time of the list! Either the type checking cause by the array being generic is really heavy (on a relative scale of course), or the array implementation in the AVM2 is *strange*, maybe using some kind of number hashing?
Anyway, the list seems to walk victorious through my best tries of arrayiness, which is definitly something to remember when writing the next heavy AS3 application.
"But I want spacial locality!", you scream!
I actually came up with a way of further improving my test example:
// in separate file
package {
public class DualSpeedTestObjList {
public var nbr:Number;
public var nbr2:Number;
public var next:DualSpeedTestObjList = null;
}
}
// in .fla
timer = getTimer();
var objList2:DualSpeedTestObjList = new DualSpeedTestObjList();
var first2:DualSpeedTestObjList = objList2;
first2.nbr = 0;
first2.nbr2 = 1;
for (i=2; i<nbrOfObjects; i++, objList2 = objList2.next) {
objList2.next = new DualSpeedTestObjList();
objList2.next.nbr = i;
objList2.next.nbr2 = ++i;
}
trace("creating "+i+" dualobject list: "+(getTimer()-timer));
timer = getTimer();
objList2 = first2;
while (objList2 != null) {
s = objList2.nbr;
s = objList2.nbr2;
objList2 = objList2.next;
}
trace("getting Number from "+i+" dualobjects in list: "+(getTimer()-timer));
Results: (ms of course)
creating 1000000 dualobject list: 234
getting Number from 1000000 dualobjects in list: 10
Nuff ranting. Optimization is fun. There's always something more :D.
