Re: [Flashcoders] Attention Recursion Speed Experts
index = list.index;
len = list.length;
while (index length) {
It's a problem with len/gth, you overlooked the 'length' in the
while() when you renamed it to 'len'.
Below is the reworked testing class. It creates the array in the
beginning, then waits 30 frames before testing the two methods, taking
turns, one test per frame.
The result I'm getting is that recursion consistently is about 20%
faster than my iterative function (mtasc compiled, running in the
Linux plugin, which still is version 7). That's a bit of a surprise
since it was 10% slower in Danny's test, but then, it's different
compilers.
If you want to compile it in the Flash IDE to compare, take an empty
.fla, import TestArray, and call TestArray.main(). My version is at
http://www.snafoo.org/tmp/flatten.swf.
Mark
class TestArray extends Array {
public static var testarray : Array;
public static function main () : Void {
var ta = TestArray.testarray = TestArray.randomArray( 10 );
_root.createTextField( tf, 1, 0, 0, 1024, 768 );
var cntr = 0;
_root.onEnterFrame = function () {
if( cntr++ 30 ) {
var n = (cntr % 2);
var start = getTimer();
if( n ) {
ta.flatten2();
} else {
ta.flatten();
}
var dur = getTimer() - start;
_root.tf.text += \n + (n ? flatten2 : flatten) +
: + dur;
}
if( cntr 70 ) {
delete this.onEnterFrame;
}
};
}
public static function randomArray(p) : Array {
var a = new TestArray;
for (var i = 0; i p; i++) {
if (Math.random() * 2 Math.random() * 5) {
a.push(i);
} else {
a.push(TestArray.randomArray(Math.ceil(
Math.random() * 3 ) ));
}
}
_root.tf.text += length: + a.length;
return a;
}
public function flatten (r) : Array {
if (!r) r = [];
var n = this.length;
for (var a = 0; a n; a++) {
if (this[a] instanceof Array) {
r.push(this[a]);
} else {
this[a].flatten(r);
}
}
return r;
};
public function flatten2 () : Array {
var outArray : Array = [];
var list = this;
list.index = 0;
var item : Object;
var index : Number;
var length : Number;
do {
index = list.index;
length = list.length;
while( index length ) {
item = list[ index++ ];
if( item instanceof Array ) {
item.parent = list;
list.index = index;
list = item;
index = 0;
length = list.length;
} else {
outArray.push( item );
}
}
} while( list = list.parent );
return outArray;
}
}
___
Flashcoders@chattyfig.figleaf.com
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
Re: [Flashcoders] Attention Recursion Speed Experts
weird results!
I do get very different results from the IDE, but I am testing using
Flash 8 and Flash Player IDE is 8
could that (it should) explain the difference with results seen in
the browser (which has Flash Player 9) ?
Cedric
index = list.index;
len = list.length;
while (index length) {
It's a problem with len/gth, you overlooked the 'length' in the
while() when you renamed it to 'len'.
Below is the reworked testing class. It creates the array in the
beginning, then waits 30 frames before testing the two methods, taking
turns, one test per frame.
The result I'm getting is that recursion consistently is about 20%
faster than my iterative function (mtasc compiled, running in the
Linux plugin, which still is version 7). That's a bit of a surprise
since it was 10% slower in Danny's test, but then, it's different
compilers.
If you want to compile it in the Flash IDE to compare, take an empty
.fla, import TestArray, and call TestArray.main(). My version is at
http://www.snafoo.org/tmp/flatten.swf.
Mark
class TestArray extends Array {
public static var testarray : Array;
public static function main () : Void {
var ta = TestArray.testarray = TestArray.randomArray( 10 );
_root.createTextField( tf, 1, 0, 0, 1024, 768 );
var cntr = 0;
_root.onEnterFrame = function () {
if( cntr++ 30 ) {
var n = (cntr % 2);
var start = getTimer();
if( n ) {
ta.flatten2();
} else {
ta.flatten();
}
var dur = getTimer() - start;
_root.tf.text += \n + (n ? flatten2 : flatten) +
: + dur;
}
if( cntr 70 ) {
delete this.onEnterFrame;
}
};
}
public static function randomArray(p) : Array {
var a = new TestArray;
for (var i = 0; i p; i++) {
if (Math.random() * 2 Math.random() * 5) {
a.push(i);
} else {
a.push(TestArray.randomArray(Math.ceil( Math.random() *
3 ) ));
}
}
_root.tf.text += length: + a.length;
return a;
}
public function flatten (r) : Array {
if (!r) r = [];
var n = this.length;
for (var a = 0; a n; a++) {
if (this[a] instanceof Array) {
r.push(this[a]);
} else {
this[a].flatten(r);
}
}
return r;
};
public function flatten2 () : Array {
var outArray : Array = [];
var list = this;
list.index = 0;
var item : Object;
var index : Number;
var length : Number;
do {
index = list.index;
length = list.length;
while( index length ) {
item = list[ index++ ];
if( item instanceof Array ) {
item.parent = list;
list.index = index;
list = item;
index = 0;
length = list.length;
} else {
outArray.push( item );
}
}
} while( list = list.parent );
return outArray;
}
}
___
Flashcoders@chattyfig.figleaf.com
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
___
Flashcoders@chattyfig.figleaf.com
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
Re: [Flashcoders] Attention Recursion Speed Experts
Hey Cedric, What results are you getting? Which one is how much faster in what player? It would surprise me if there were different results for FP8 and FP9, because it runs in the old VM and I doubt they reworked it since it's there for backwards compatibility anyway. It's probably more of a standalone debug player vs. plugin thing. When I run it in the v9 debug standalone player it seems like recursion's speed advantage shrinks to 10%, but that's under Wine and the results aren't as consistent as in the browser. Could you or somebody else post a Flash IDE compiled version somewhere maybe? Mark ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
Re: [Flashcoders] Attention Recursion Speed Experts
Hey Cedric, What results are you getting? Which one is how much faster in what player? F8 IDE (FP 8 IDE): flatten: 1576 flatten2: 1554 flatten: 1451 flatten2: 1593 flatten: 1390 flatten2: 1437 flatten: 1526 flatten2: 1439 flatten: 1313 flatten2: 1528 flatten: 1368 flatten2: 1446 Safari (FP9): flatten: 970 flatten2: 1283 flatten: 804 flatten2: 1374 flatten: 946 flatten2: 1118 flatten: 911 flatten2: 1238 flatten: 805 flatten2: 1278 flatten: 784 flatten2: 1072 unfortunately I don't have more time right now, will try to post my Flash IDE compiled version later (or someone else) SORRYYY! It would surprise me if there were different results for FP8 and FP9, because it runs in the old VM and I doubt they reworked it since it's there for backwards compatibility anyway. It's probably more of a standalone debug player vs. plugin thing. When I run it in the v9 debug standalone player it seems like recursion's speed advantage shrinks to 10%, but that's under Wine and the results aren't as consistent as in the browser. Could you or somebody else post a Flash IDE compiled version somewhere maybe? Mark ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
Re: [Flashcoders] Attention Recursion Speed Experts
Thanks, Cedric. I assume those were results compiled by the Flash IDE, so we can conclude recursion *is* the fastest. It's also the most elegant solution, not requirements in this case, but nice to have anyway. I still don't understand why Danny got contrary results, but I like recursion better so let's just leave it like that :) Mark ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
Re: [Flashcoders] Attention Recursion Speed Experts
On 7/26/06, Mark Winterhalder [EMAIL PROTECTED] wrote:
I still don't understand why Danny got contrary results, but I like
recursion better so let's just leave it like that :)
OK, let's not -- I had another look, and found a ! was missing in the
recursive method. I've updated the test class below, test at
http://www.snafoo.org/tmp/flatten.swf, with the length of the result
now being traced as a simple check.
Iteration now is faster, confirming Danny's results.
As a note on the side, the recursion can be accelerated a bit by
storing the value of the array in a variable instead of looking it up
twice in each iteration. You can compare it here:
http://www.snafoo.org/tmp/flatten2.swf. Maybe I should have used
more descriptive names, but 'flatten' here means the original and
'flatten2' means it's like this:
public function flatten2 (r) : Array {
if (!r) r = [];
var n = this.length;
var foo;
for (var a = 0; a n; a++) {
if ( !((foo = this[a]) instanceof Array) ) {
r.push(foo);
} else {
foo.flatten2(r);
}
}
return r;
};
Anyway, iteration is still slightly faster -- this is just a general
hint. I found this after making the other test and am already late, I
might make one with iteration and both recursions later to make it
easier to compare.
Mark
class TestArray extends Array {
public static var testarray : Array;
public static function main () : Void {
var ta = TestArray.testarray = TestArray.randomArray( 10 );
_root.createTextField( tf, 1, 0, 0, 1024, 768 );
var cntr = 0;
_root.onEnterFrame = function () {
if( cntr++ 30 ) {
var n = (cntr % 2);
var res;
var start = getTimer();
if( n ) {
res = ta.flatten2();
} else {
res = ta.flatten();
}
var dur = getTimer() - start;
_root.tf.text += \n + res.length + , + (n ?
flatten2 :
flatten) + : + dur;
}
if( cntr 70 ) {
delete this.onEnterFrame;
}
};
}
public static function randomArray(p) : Array {
var a = new TestArray;
for (var i = 0; i p; i++) {
if (Math.random() * 2 Math.random() * 5) {
a.push(i);
} else {
a.push(TestArray.randomArray(Math.ceil(
Math.random() * 3 ) ));
}
}
_root.tf.text += length: + a.length;
return a;
}
public function flatten (r) : Array {
if (!r) r = [];
var n = this.length;
for (var a = 0; a n; a++) {
if ( !(this[a] instanceof Array) ) {
r.push(this[a]);
} else {
this[a].flatten(r);
}
}
return r;
};
public function flatten2 () : Array {
var outArray : Array = [];
var list = this;
list.index = 0;
var item : Object;
var index : Number;
var length : Number;
do {
index = list.index;
length = list.length;
while( index length ) {
item = list[ index++ ];
if( item instanceof Array ) {
item.parent = list;
list.index = index;
list = item;
index = 0;
length = list.length;
} else {
outArray.push( item );
}
}
} while( list = list.parent );
return outArray;
}
}
___
Flashcoders@chattyfig.figleaf.com
To change your subscription options or search the archive:
Re: [Flashcoders] Attention Recursion Speed Experts
OK, my final conclusion:
http://www.snafoo.org/tmp/flatten.swf
Iterative *is* faster than recursion. Run the test and examine the
test class below. (Use an empty .fla, import it, call TestArray.main()
)
Also, we learn that whenever you have to get the item at the same
position of an array twice, store it in a local variable. Plus, and
this lead to significant improvements, don't use Array.push(), but
maintain the index in a local variable.
The fastest is the new iterative, or flatten4 as it is called in
the class below. We're talking 25% improvement over recursion. I've
changed the original one so it stores the index and parent on a stack
instead of a property so it can be used in Steven's Array class if he
likes.
It ain't pretty to look at, but it's pretty fast.
Mark
class TestArray extends Array {
public static var testarray : Array;
public static function main () : Void {
var ta = TestArray.testarray = TestArray.randomArray( 10 );
var reference = ta.flatten().length;
_root.createTextField( tf, 1, 0, 0, 1024, 768 );
_root.tf.text = testing... will take a while, be patient.;
var cntr = 0;
var results = [ [], [], [], [] ];
var labels = [ recursive, new recursive, iterative, new
iterative ];
_root.onEnterFrame = function () {
if( cntr++ 30 ) {
var n = (cntr % 4);
var res;
var start;
switch( n ) {
case 0:
start = getTimer();
res = ta.flatten();
break;
case 1:
start = getTimer();
res = ta.flatten2();
break;
case 2:
start = getTimer();
res = ta.flatten3();
break;
case 3:
start = getTimer();
res = ta.flatten4();
break;
}
var dur = getTimer() - start;
results[ n ].push( dur );
if( res.length != reference ) {
_root.tf.text += \ncheck + labels[ n ] +
, gave result length
different from reference result.;
}
_root.tf.text = res.length + , + labels[ n ] + :
+ dur;
}
if( cntr 70 ) {
delete this.onEnterFrame;
var totals = [];
_root.tf.text = The fastest results
were...\n\n;
for( var i in results ) {
var result = results[ i ];
var min = Number.MAX_VALUE;
for( var k in result ) {
min = Math.min( min, result[ k
] );
}
_root.tf.text += \nfor + labels[ i ] +
:\t + min;
}
}
};
}
public static function randomArray(p) : Array {
var a = new TestArray;
for (var i = 0; i p; i++) {
if (Math.random() * 2 Math.random() * 5) {
a.push(i);
} else {
a.push(TestArray.randomArray(Math.ceil(
Math.random() * 3 ) ));
}
}
_root.tf.text += length: + a.length;
return a;
}
public function flatten (r) : Array {
if (!r) r = [];
var n = this.length;
for (var a = 0; a n; a++) {
if ( !(this[a] instanceof Array) ) {
RE: [Flashcoders] Attention Recursion Speed Experts
Sweet. The only other method that uses recursion is eql. -Steven ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
Re: [Flashcoders] Attention Recursion Speed Experts
On 7/25/06, Mark Winterhalder [EMAIL PROTECTED] wrote: On 7/25/06, Steven Sacks | BLITZ [EMAIL PROTECTED] wrote: It is iterating. It still needs to iterate through all nested arrays using the same method, which means recursion. Yes, but function calls aren't the only way to do recursion. What you're doing is essentially like a depth-first search, which can be done with a stack. Hmm... now that I'm having coffee and slowly waking up, I'm getting serious doubts about how to do depth-first without function calls. I'm probably wrong, sorry. Mark ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
Re: [Flashcoders] Attention Recursion Speed Experts
On 7/25/06, Mark Winterhalder [EMAIL PROTECTED] wrote:
Hmm... now that I'm having coffee and slowly waking up, I'm getting
serious doubts about how to do depth-first without function calls. I'm
probably wrong, sorry.
Interesting problem, though. Got me thinking.
So, here's my proposal for a function to flatten an array without
calling it recursively:
class Main {
public static function main () : Void {
var foo : Array = [0, [1, 2], 3, [4, [5, 6], 7], 8, [], 9];
var out : String = flatten( foo ).toString();
_root.createTextField( tf, 100, 0, 0, 1000, 100 );
_root.tf.text = out;
}
public static function flatten( inArray : Array ) : Array {
var outArray : Array = [];
var list = inArray;
list.index = 0;
var item : Object;
var index : Number;
var length : Number;
do {
index = list.index;
length = list.length;
while( index length ) {
item = list[ index++ ];
if( item.__proto__ == Array.prototype ) {
item.parent = list;
list.index = index;
list = item;
index = 0;
length = list.length;
} else {
outArray.push( item );
}
}
} while( list = list.parent );
return outArray;
}
}
I hope you have a big enough testcase to compare performance, it would
be interesting which one is faster.
Mark
___
Flashcoders@chattyfig.figleaf.com
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
RE: [Flashcoders] Attention Recursion Speed Experts
On 7/25/06, Mark Winterhalder [EMAIL PROTECTED] wrote:
On 7/25/06, Steven Sacks | BLITZ [EMAIL PROTECTED] wrote:
It is iterating. It still needs to iterate through all nested arrays
using the same method, which means recursion.
Yes, but function calls aren't the only way to do recursion.
What you're doing is essentially like a depth-first search, which can
be done with a stack.
Hmm... now that I'm having coffee and slowly waking up, I'm getting
serious doubts about how to do depth-first without function calls. I'm
probably wrong, sorry.
No, it's always possible to unroll a recursion, and usually faster. What
about this concept? (I'm sure it could be optimised some more!):
function flatten(a:Array) {
var r:Array = new Array(); // the flattened array
var p:Array = new Array(); // the index stack
var s:Array = new Array(); // the array stack
var c = a; // the currently evaluating array
var i = 0; // the current array index
var t:Boolean; // a flag to show if we've finished a level
while (true!Key.isDown(Key.SHIFT)) {
t = true;
for (var i; i c.length; i++) {
var e = c[i];
if (e instanceof Array) {
p.push(i+1);
i = 0;
s.push(c);
c = e;
t = false;
break;
}
r.push(e);
}
if (t) {
if (p.length) {
i = p.pop();
c = s.pop();
} else {
break;
}
}
}
return r;
};
Here's what I used to test it:
function randomArray(p) {
var l = random(5)
var a = new Array();
for (var i = 0; i l; i++) {
if (Math.random() p) {
a.push(i);
} else {
a.push(randomArray(p + 0.2));
}
}
return a;
}
var a:Array = randomArray(0.4);
trace(a+ +a.length)
var r:Array = flatten(a)
trace(r+ +r.length);
And here's the result:
,0,1,2,1,0,1,2,3,0,0,1,2 4
0,1,2,1,0,1,2,3,0,0,1,2 12
Note that it works fine even with empty arrays.
Danny
___
Flashcoders@chattyfig.figleaf.com
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
RE: [Flashcoders] Attention Recursion Speed Experts
Ha - you beat me to it...
public static function flatten( inArray : Array ) : Array {
var outArray : Array = [];
var list = inArray;
list.index = 0;
var item : Object;
var index : Number;
var length : Number;
do {
index = list.index;
length = list.length;
while( index length ) {
item = list[ index++ ];
if( item.__proto__ == Array.prototype ) {
item.parent = list;
list.index = index;
list = item;
index = 0;
length = list.length;
} else {
outArray.push( item );
}
}
} while( list = list.parent );
return outArray;
}
}
Just out of interest, I tried a speed test using the three methods - mine
was the fastest by a very long way:
iterative 3068 length: 343932
recursive 7865 length: 343932
Mark's version 6771 length: 343932
iterative 1814 length: 371470
recursive 7554 length: 371470
Mark's version 7607 length: 371470
iterative 1483 length: 312964
recursive 5822 length: 312964
Mark's version 5530 length: 312964
(the first number shows the time taken for the calculation, the second shows
the length of the flattened array)
This seemed a weird result, so I took a look for other differences. It turns
out that the test for array.__proto__ == Array.prototype is *way* slower
than using instanceof Array. When I replaced the two relevant lines in the
other two functions, mine was relegated to a rightful third place
iterative 2387 length: 264356
recursive 1175 length: 264356
Mark's version 1096 length: 264356
Danny
___
Flashcoders@chattyfig.figleaf.com
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
Re: [Flashcoders] Attention Recursion Speed Experts
On 7/25/06, Danny Kodicek [EMAIL PROTECTED] wrote: Just out of interest, I tried a speed test using the three methods - mine was the fastest by a very long way: Thanks -- I was hoping somebody would test it :) This seemed a weird result, so I took a look for other differences. It turns out that the test for array.__proto__ == Array.prototype is *way* slower than using instanceof Array. When I replaced the two relevant lines in the other two functions, mine was relegated to a rightful third place I thought about that when I saw yours. It kinda makes sense that it's faster when being handled internally (saves two getProperty's after all), but I would have never expected it to have such a huge effect. So we learn that instanceOf is very fast. iterative 2387 length: 264356 recursive 1175 length: 264356 Mark's version 1096 length: 264356 This seems to be extreme. Any chance something is going wrong with the test? Did you wait a few frames before doing the first test to ensure initialization has finished? Maybe switch the order to see if the first one always is the slowest? Frankly, I only had a quick look at yours, but it seemed to follow roughly the same principle as mine. So where is the bottleneck (if the test works correctly)? BTW, the reason I didn't have a detailed look were the shortened, non-descriptive variable names. This is most likely not necessary. It makes sense for properties, but variables usually are stored as registers (if the compiler chooses to use function2 instead of the old function tag, which it normally does for class methods), the names you give them in your source code are irrelevant and don't appear in the SWF. Given the minuscule performance difference, I'd go with the original (recursive) version for elegance and readability. Unless somebody feels like giving mine a work over with flasm, that is, it has more potential for bytecode optimizations because the recursive one's bottleneck is the function call, and that can't be changed. Mark ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
RE: [Flashcoders] Attention Recursion Speed Experts
BTW, the reason I didn't have a detailed look were the shortened, non-descriptive variable names. This is most likely not necessary. It makes sense for properties, but variables usually are stored as registers (if the compiler chooses to use function2 instead of the old function tag, which it normally does for class methods), the names you give them in your source code are irrelevant and don't appear in the SWF. I thought so too, but I was trying to follow Steve's version as closely as possible in order to limit the number of variables (in the experimental sense) being tested. Given the minuscule (but consistent!) performance difference, I'd go with the original (recursive) version for elegance and readability. Unless somebody feels like giving mine a work over with flasm, that is, it has more potential for bytecode optimizations because the recursive one's bottleneck is the function call, and that can't be changed. I think you're right. I think it's very rare that the kinds of millisecond-level performance gains you can get in a function have any serious impact on the average program. It's easy to get focused on tiny speed gains while ignoring the other places where there are more obvious bottlenecks, like the rendering engine. On the other hand, a five-fold speed increase by using instanceof was certainly worth noticing! Danny ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
Re: [Flashcoders] Attention Recursion Speed Experts
On 7/25/06, Mark Winterhalder [EMAIL PROTECTED] wrote: This seems to be extreme. Any chance something is going wrong with the test? Did you wait a few frames before doing the first test to ensure initialization has finished? Maybe switch the order to see if the first one always is the slowest? Frankly, I only had a quick look at yours, but it seemed to follow roughly the same principle as mine. So where is the bottleneck (if the test works correctly)? OK, had a (slightly) closer look after all. Avoid the Array.length property. Avoid properties in general (I have some, too, but only when the algorithm comes across another array). Also, while generally is faster than for(;;) for loops, especially in the while( i-- ) form (fastest loop possible when going through an array, but not usable in this case). Mark ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
RE: [Flashcoders] Attention Recursion Speed Experts
First off, thanks to everyone helping on this thread. I originally was using object == typeof(this[a]). Glad to see instanceof Array was fastest. What I'm trying to do here is write new methods for Array (and next up is String) that other languages have but Flash does not. Some of these methods are extremely useful. This is why I'm injecting them right into Array with prototype for now. This is also why I'm trying to squeeze the absolute fastest performance out of these methods. The fastest loop in flash is not while (i--). Pre-decrementing is faster than Post-decrementing. while (--i -(-1)) is actually the fastest because of what it compiles to in bytecode. For more information on this and other cool optimizations, check out the Flasm page. One thing I'm wondering is if a decrementing loop and then a reverse() at the end is faster than an incrementing loop. I'm working on compacting Danny's script at the moment. -Steven ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
RE: [Flashcoders] Attention Recursion Speed Experts
Oh, I just noticed that Mark's was fastest. But, I can't get it to work (freezes flash) There seems to be an error in the final while loop. It's a single = not a double ==. Is that a typo? ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
RE: [Flashcoders] Attention Recursion Speed Experts
Ok, I got Mark's to work however it does not work when turned into a prototype and I set list = this. Why it doesn't work may be the result of another problem, though, and I'm not sure yet what it is, but here's the behavior. I created a movie with 3 buttons. An new array is instantiated. ButtonA generates an array of 100,000 items. ButtonB does recursive, ButtonC does iterative. The first time I feed Mark's script a list of 100,000 items, it scores ~2135ms. The second and every subsequent time I run his script on the same list, it scores ~1250ms. That's a suspiciously huge jump. So, then I generate a new array and run the test again and again the first test runs much slower than subsequent tests. Somehow, Mark's script is cheating. ;) So, I decided to run his script on the empty array the first time and then feed it then 100,000 item array. I got 0ms on the empty array, as expected, but then I fed it the 100,000 item array and it scored 0ms every time. Something is amiss. I'm not sure what's wrong with his code, but the results I got with the recursive script were consistent every time and consistently faster than the iterative code's first run speed, especially the more items there were. At 10,000 items, it was close. At 100,000 items, it was almost a second difference (recursion scored ~1400ms to ~1700ms while iterative scored well over ~2000ms every time). Mark, please check your script to try and find out what's wrong with it. I'd like to run some more accurate comparisons. Thanks, Steven ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
Re: [Flashcoders] Attention Recursion Speed Experts
On 7/25/06, Steven Sacks | BLITZ [EMAIL PROTECTED] wrote:
Oh, I just noticed that Mark's was fastest. But, I can't get it to work
(freezes flash) There seems to be an error in the final while loop.
It's a single = not a double ==. Is that a typo?
No, not a typo. I know it's confusing, but since this is about speed...
'list' is the current array. Say we have array A containing array B.
'list' is A and we iterate through it. At some point, we come across
B, so the current index gets stored away in A.index, A itself is
stored as B.parent, B gets assigned to 'list' and index reset to
iterate through B. Once we're at the end of B, we continue where we
left off in A (B.parent == list.parent at this point). However, the
inArray we want to flatten is the outermost array and has no parent --
when it's finished the loop ends.
Put differently, it would have been possible to write it like this:
do {
// ...
list = list.parent;
} while ( list != undefined );
Better readable, but oh so slightly slower...
If you want to use it for a library, though, there would be some
changes required. Out of laziness I stored the index and parent as a
property of the array. You wouldn't want that in a library, especially
not with such common names. One way would of course be to hide it with
AsSetPropFlags, but a stack would be better.
Unless you have a ridiculously deep recursion depth, you could even
use the VM's stack directly. That would save some getMembers and you
could do some additional optimizations while you're at it.
Disadvantage would be that you'd have to do it in flasm, obviously.
I tested this option, it shaves off a few percent (depending on
recursion depth between, say, 1% and 5%), is nowhere near finished,
only almost-not tested, to be used at your own risk and so on, but
could quite possibly be improved further. Oh, and it needs proper
register and variable names -- sorry.
function2 (r:2='inArray') (r:1='this')
// begin init
// declare 'outArray'
push 0
initArray
setRegister r:3
pop
// put 'null' on stack to mark end
push NULL
// push 'length' of 'inArray' and 'index' of 0 on
// stack, followed by 'inArray'
push r:inArray, 'length'
getMember
push 0, r:2
// stack now looks like this:
// NULL, inArray.length, 0, inArray
// end init
branch label2
// check if something (should be an array) is on the
// stack, otherwise it's NULL and we're done
label1:
dup
not
branchIfTrue label7
// begin new loop: next array on stack
label2:
// take sub-array from stack
setRegister r:4
pop
// take 'index' from stack
setRegister r:6
pop
// take 'length' from stack
setRegister r:7
pop
// begin new loop: loop through current array
label3:
// condition: (index length)
push r:6, r:7
lessThan
not
branchIfTrue label1
push r:4, r:6, r:6 // stack: array, index, index
increment // index++
setRegister r:6
pop
// get array[ index ] (i.e., 'item')
getMember
setRegister r:5
// condition: ('item' instanceof 'Array')
push 'Array'
getVariable
instanceOf
not
branchIfTrue label4
// 'item' is an array
// put length, index and current array on stack
push r:7, r:6, r:4
// put new current array on stack and into register
push r:5
setRegister r:4
// get length and store in register
push 'length'
getMember
setRegister r:7
pop
// set 'index' to 0
push 0
setRegister r:6
pop
// continue with new array
branch label3
// 'item' is no array
label4:
// append 'item' to 'outArray'
push r:5, 1, r:3, 'push'
callMethod
pop
branch label3
// done going through the array
label7:
// remove NULL from stack
pop
// return 'outArray'
push r:3
return
end // of function
Mark
___
Flashcoders@chattyfig.figleaf.com
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
Re: [Flashcoders] Attention Recursion Speed Experts
On 7/25/06, Steven Sacks | BLITZ [EMAIL PROTECTED] wrote: Mark, please check your script to try and find out what's wrong with it. I'd like to run some more accurate comparisons. Ah, yes, just noticed I forgot to look into the freezing problem you mentioned in your last mail (also, I noticed I wrote that it needed proper variable names when I meant label names). It's strange, I didn't encounter this problem in my tests. I let it take turns with the flasm version to test how much could be gained by using the VM stack, each took the same array 20 times, taking turns, giving constant results. Could you post (or send me) the test script, please? (Not as .fla please, I don't have the Flash IDE. I use MTASC, but don't think this is causing the problem.) Also, I might not be able to look into it tonight, need to go to the park and drink wine. :) It's probably better that way, I haven't slept last night so I might make things worse if I fiddle with it right now, unless it's something obvious. Mark ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
Re: [Flashcoders] Attention Recursion Speed Experts
One thing I'm wondering is if a decrementing loop and then a reverse() at the end is faster than an incrementing loop. I'd be astounded if it was! I'm working on compacting Danny's script at the moment. Sounds like an odd idea to me: Mark's was way faster and was essentially the same idea anyway. Danny ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
Re: [Flashcoders] Attention Recursion Speed Experts
Oh, I just noticed that Mark's was fastest. Sorry, replied to an easlier mail before noticing the thread continued... Danny ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
RE: [Flashcoders] Attention Recursion Speed Experts
Could you post (or send me) the test script, please?
Sure, here you go.
---
function randomArray(p) {
var a = [];
for (var i = 0; i p; i++) {
if (random(2) random(5)) {
a.push(i);
} else {
a.push(randomArray(random(3) + 1));
}
}
return a;
}
function flatten(inArray:Array):Array {
var outArray:Array = [];
var list = inArray;
list.index = 0;
var item:Object;
var index:Number;
var len:Number;
do {
index = list.index;
len = list.length;
while (index length) {
item = list[index++];
if (item instanceof Array) {
item.parent = list;
list.index = index;
list = item;
index = 0;
len = list.length;
} else {
outArray.push(item);
}
}
} while (list = list.parent);
return outArray;
}
Array.prototype.flatten = function(r) {
if (!r) r = [];
var n = this.length;
for (var a = 0; a n; a++) {
if (this[a] instanceof Array) {
r.push(this[a]);
} else {
this[a].flatten(r);
}
}
return r;
};
p = 1000;
x = randomArray(p);
n = new Date().getTime();
z = x.flatten();
trace(recursive: + (new Date().getTime() - n) + ms);
n = new Date().getTime();
z = flatten(x);
trace(iterative: + (new Date().getTime() - n) + ms);
___
Flashcoders@chattyfig.figleaf.com
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
RE: [Flashcoders] Attention Recursion Speed Experts
I don't know if I understand this correctly, but is it making a array flat? Then this is the fastest way I think: var foo : Array = [a, b, c, [d, e,[d, e,[d, e,[d, e, f, [g, [h]], [[], i], j]; var fooString:String = foo.join(;); fooString = fooString.split(,).join(;); foo = fooString.split(;); output: a,b,c,d,e,d,e,d,e,d,e,f,g,h,,i,j Bernard -Oorspronkelijk bericht- Van: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Namens Danny Kodicek Verzonden: dinsdag 25 juli 2006 21:51 Aan: Flashcoders mailing list Onderwerp: Re: [Flashcoders] Attention Recursion Speed Experts Oh, I just noticed that Mark's was fastest. Sorry, replied to an easlier mail before noticing the thread continued... Danny ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
RE: [Flashcoders] Attention Recursion Speed Experts
Why have the step with the semicolon? You can just do this: var foo:Array = [a, b, c, [d, e, [d, e, [d, e, [d, e, f, [g, [h]], [[], i], j]; var fooFlat:Array = foo.toString().split(,); Potential problems with this approach: - It does not preserve the type of the elements, converting them all to string. - Any element that equates to a string with a comma in it will be evaluated as two elements. E.g, if foo is set to [a,b, c], it will flatten to a 3-element array. So it's only useful if the atomic elements are strings, and they are guaranteed not to include commas. I have no idea how efficient it is, processor-wise, although I would suspect it is rather slow. -- T. Michael Keesey -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Bernard Visscher Sent: Tuesday, July 25, 2006 2:05 PM To: 'Flashcoders mailing list' Subject: RE: [Flashcoders] Attention Recursion Speed Experts I don't know if I understand this correctly, but is it making a array flat? Then this is the fastest way I think: var foo : Array = [a, b, c, [d, e,[d, e,[d, e,[d, e, f, [g, [h]], [[], i], j]; var fooString:String = foo.join(;); fooString = fooString.split(,).join(;); foo = fooString.split(;); output: a,b,c,d,e,d,e,d,e,d,e,f,g,h,,i,j Bernard -Oorspronkelijk bericht- Van: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Namens Danny Kodicek Verzonden: dinsdag 25 juli 2006 21:51 Aan: Flashcoders mailing list Onderwerp: Re: [Flashcoders] Attention Recursion Speed Experts Oh, I just noticed that Mark's was fastest. Sorry, replied to an easlier mail before noticing the thread continued... Danny ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
Re: [Flashcoders] Attention Recursion Speed Experts
I am assuming this is for AS2 - right?
If you want speed that probably means you are dealing with a lot of data(?)
1- What is the typical recursion level?
2- What is the typical number of items?
3- What is the typical size of sub arrays?
In general making a function call is not fast at all. Better iterate than
recurse.
B.
2006/7/25, Steven Sacks | BLITZ [EMAIL PROTECTED]:
Is there a way to make this script any faster?
Array.prototype.flatten = function(r) {
if (!r) r = [];
var l = this.length;
for (var a = 0; a l; a++) {
if (this[a].__proto__ != Array.prototype) {
r.push(this[a]);
} else {
this[a].flatten(r);
}
}
return r;
}
This function takes an array and flattens it, meaning any nested arrays
will get flattened into a single array.
Example:
x = [a, b, c, [d, e], f, [g, [h]], [[], i], j];
y = x.flatten();
y [a,b,c,d,e,f,g,h,i,j]
Issues:
Array.reverse() and Array.unshift() are notoriously slow and any speed
gained from doing a reverse while loop would be lost.
I don't see how this script could be sped up, but I'm not a recursion
expert. The current speed increases I have are:
1) Single character variable names
2) this.length stored in a variable avoids computation every loop.
3) Most common if true (not a nested array) comes first
I'm not clear which, if either, is faster:
if (x != y) vs if (!(x == y))
That's the only other place I can see a spot for a possible speed
improvement.
Thanks!
___
Flashcoders@chattyfig.figleaf.com
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
___
Flashcoders@chattyfig.figleaf.com
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
RE: [Flashcoders] Attention Recursion Speed Experts
AS2 is no faster than AS1 (in some ways it is slower). Strict typing
has no effect on speed. In addition, this is not AS2 syntax, because
I'm not extending Array, I'm plugging directly into its prototype at the
moment.
It is iterating. It still needs to iterate through all nested arrays
using the same method, which means recursion.
BLITZ | Steven Sacks - 310-551-0200 x209
-Original Message-
From: [EMAIL PROTECTED] [mailto:flashcoders-
[EMAIL PROTECTED] On Behalf Of Bernard Poulin
Sent: Monday, July 24, 2006 9:56 PM
To: Flashcoders mailing list
Subject: Re: [Flashcoders] Attention Recursion Speed Experts
I am assuming this is for AS2 - right?
If you want speed that probably means you are dealing with a lot of
data(?)
1- What is the typical recursion level?
2- What is the typical number of items?
3- What is the typical size of sub arrays?
In general making a function call is not fast at all. Better iterate
than
recurse.
B.
2006/7/25, Steven Sacks | BLITZ [EMAIL PROTECTED]:
Is there a way to make this script any faster?
Array.prototype.flatten = function(r) {
if (!r) r = [];
var l = this.length;
for (var a = 0; a l; a++) {
if (this[a].__proto__ != Array.prototype) {
r.push(this[a]);
} else {
this[a].flatten(r);
}
}
return r;
}
This function takes an array and flattens it, meaning any nested
arrays
will get flattened into a single array.
Example:
x = [a, b, c, [d, e], f, [g, [h]], [[], i], j];
y = x.flatten();
y [a,b,c,d,e,f,g,h,i,j]
Issues:
Array.reverse() and Array.unshift() are notoriously slow and any
speed
gained from doing a reverse while loop would be lost.
I don't see how this script could be sped up, but I'm not a
recursion
expert. The current speed increases I have are:
1) Single character variable names
2) this.length stored in a variable avoids computation every loop.
3) Most common if true (not a nested array) comes first
I'm not clear which, if either, is faster:
if (x != y) vs if (!(x == y))
That's the only other place I can see a spot for a possible speed
improvement.
Thanks!
___
Flashcoders@chattyfig.figleaf.com
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
___
Flashcoders@chattyfig.figleaf.com
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
___
Flashcoders@chattyfig.figleaf.com
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
Re: [Flashcoders] Attention Recursion Speed Experts
On 7/25/06, Steven Sacks | BLITZ [EMAIL PROTECTED] wrote: It is iterating. It still needs to iterate through all nested arrays using the same method, which means recursion. Yes, but function calls aren't the only way to do recursion. What you're doing is essentially like a depth-first search, which can be done with a stack. HTH, Mark ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
