Optimizations for AS3 calculations
Well, I’m not the math whiz by any means, but thought enough of what I’ve been playing around with lately to throw this out there and see how it sticks to the flash wall (yes, Tink, i’m inviting you thrash this around a bit! )
Now, you’ve probably heard the tip about “use multiplication instead of division when dividing by 2”, right?
faster:
var n:Number = value *.5;
slower:
var n:Number = value / 2;
run it with a test:
[as]import flash.utils.getTimer;
var time:Number = getTimer();
function runDivisionTest():void
{
time = getTimer();
for(var i:Number=0;i<10000000;i++)
{
var test:Number = i/2;
}
trace(“DivisionTest: “, (getTimer()-time));
}
function runMultTest():void
{
time = getTimer();
for(var i:Number=0;i<10000000;i++)
{
var test:Number = i*.5;
}
trace(“MultTest: “, (getTimer()-time));
}
runDivisionTest();
runMultTest();
[/as]
traces out:
DivisionTest: 162
MultTest: 110
Alright, so it’s not miles faster, but in a 3D engine like Papervision3D, this becomes the difference between a fast engine and a slow engine real quickly.
Well, there’s one still that’s even faster: Bitwise shift operations
Divide by 2 with a right shift:
trace(10 >> 1);
// traces:
5
Multiply by 2 with a left shift:
trace(10 << 1);
// traces:
20
Now, run the test against the Division and Multiplication tests above:
[as]function runBitTest():void
{
time = getTimer();
for(var i:int=0;i> 1;
}
trace(“BitTest: “, (getTimer()-time));
}
runBitTest();[/as]
traces out:
DivisionTest: 152
MultTest: 112
BitTest: 63
HOLY CRAP Batman – that’s nearly 1/2 the speed?? or should I say, 1*.5 the speed 😉
So, I was looking at some other stuff with uint and this seems to be a real gem when it comes to Math.floor and Math.ceil operations. I was reading through Flash’s help (I have to say, I really enjoy the new help – I live in there) on uint and realized that, like int, when you pass a number, it strips everything passed the decimal (like Math.floor). So, I thought, what the hey, let’s give er’ a speed test.
Sure enough, it was much faster to use uint(n) than Math.floor(n) – nearly 10x’s as fast
*** UPDATE ***
After Paulius Uza’s comments about using int, I went back and added tests for int with the floor/ceil tests, and sure enough, they’re even faster than using uint. floor’s test wasn’t that drastic, but ceil’s was 1/2 the time of uint’s version
*** /UPDATE ***
fast:
var test:int = int(1.5);
//test equals 1
slow:
var test:Number = Math.floor(1.5);
//test equals 1
Now, I know what yer thinkin’: what about Math.ceil? +1? yes 😉
fast:
var test:int = int(1.5)+1;
//test equals 2
slow:
var test:Number = Math.ceil(1.5);
//test equals 2
Time for a test:
[as]function runFloorTest():void
{
time = getTimer();
for(var i:uint=0;i<10000000;i++)
{
var n:Number = 1.5;
var test:Number = Math.floor(n);
}
trace(“FloorTest: “, (getTimer()-time));
}
function runUintFloorTest():void
{
time = getTimer();
for(var i:uint=0;i<10000000;i++)
{
var n:Number = 1.5;
var test:uint = uint(n);
}
trace(“UintFloorTest: “, (getTimer()-time));
}
function runIntFloorTest():void
{
time = getTimer();
for(var i:uint=0;i<10000000;i++)
{
var n:Number = 1.5;
var test:int = int(n);
}
trace(“IntFloorTest: “, (getTimer()-time));
}
function runCeilTest():void
{
time = getTimer();
for(var i:uint=0;i<10000000;i++)
{
var n:Number = 1.5;
var test:Number = Math.ceil(n);
}
trace(“CeilTest: “, (getTimer()-time));
}
function runUintCeilTest():void
{
time = getTimer();
for(var i:uint=0;i<10000000;i++)
{
var n:Number = 1.5;
var test:uint = n == uint(n) ? n : uint(n)+1;
}
trace(“UintCeilTest: “, (getTimer()-time));
}
function runIntCeilTest():void
{
time = getTimer();
for(var i:uint=0;i<10000000;i++)
{
var n:Number = 1.5;
var test:int = n == int(n) ? n : int(n)+1;
}
trace(“IntCeilTest: “, (getTimer()-time));
}
runFloorTest();
runUintFloorTest();
runIntFloorTest();
runUintCeilTest();
runIntCeilTest();
[/as]
traces out:
FloorTest: 1733
UintFloorTest: 176
IntFloorTest: 157
UintCeilTest: 650
IntCeilTest: 384
**** New - Math.abs ****
I was thinking about another one that I use sometimes which was using *-1 instead of Math.abs on a number
faster:
var nn:Number = -23
var test:Number= nn < 0 ? nn * -1 : nn;
slower:
var nn:Number = -23
var test:Number = Math.abs(nn);
Lets test!
[as]function runABSTest():void
{
time = getTimer();
for(var i:uint=0;i<10000000;i++)
{
var n:Number = -1.5;
var test:Number = Math.abs(n);
}
trace(“ABSTest: “, (getTimer()-time));
}
function runABSMultTest():void
{
time = getTimer();
for(var i:uint=0;i<10000000;i++)
{
var n:Number = -1.5;
var test:Number = n < 0 ? n * -1 : n;
}
trace(“ABSMultTest: “, (getTimer()-time));
}
runABSTest();
runABSMultTest();
[/as]
traces out:
ABSTest: 1615
ABSMultTest: 153
Now, I know in alot of cases, the speed differences here are not going to matter. But in a game situation, or 3D engine – these types of changes in the render loop can make a HUGE difference in performance. The Papervision3D engine has really been scrutinized for details like this, and I firmly believe that’s why it’s one of the fastest engines out there.
I realize too, that not being a total math nut, some of this is probably very obvious to other people and some of you might think “well DUH”, but for the rest of us, this could be very handy 😉
Please let me know where I’ve gone horribly wrong on any of this !
Careful with this one: uint(1)+1 != Math.ceil(1)
uint(n)+1 could not be compared with Math.ceil(n). uint(n)+1 is not equivalent to Math.ceil(n) because when it comes to an integer values (i.e. 3), Math.ceil(n) does not change the value (it remains 3) while uint(n)+1 increases one (the result is 4).
Really interesting post. In critical cases, a little optimization can improve performance dramatically.
Nice man, I didn’t know this….. I am now learned 😉
John:
It’s awesome that you are starting up a body of experimental work on this topic. Keep up the great effort!
– jim
It would be really cool to see a cheatsheet on speed benchmarks for different operations.
Maybe we could start a site where benchmarks could be posted and then printed if the user wanted a hard copy.
[@ Claus] – Oops YES, you’re right! I should have thought about that last night. Ok, I’ve adjusted the Math.ceil test with an inline or statement, and it’s still much faster than Math.ceil:
var n:Number = 1.5;
var test:uint = n == uint(n) ? n : uint(n)+1;
//traces 2
But why uint? Wouldn’t an int do the same in this case?
[@Sascha] no real reason other than I was reading the help and uint has this nice table of what happens when you pass in certain types of arguments and int didn’t – uint sparked the idea, hence, why my tests were with uint
I realize that int does the same thing, but just didn’t go back and use it in my tests 😉
Thanks John, these are really useful!
I added it to my post about optimization: http://rozengain.com/?postid=35
Another nice one is for the % (modules) operator. This one can be handy, just as division by 2, 4, 8 etc…, when working with textures e.g. To get the modules of a division by 4 use x = y & 3 which equals to x = y % 4 only a bit faster, or at least it should be. I haven’t done any benchmarking in AS3 but I used this kinda stuff in the early ’90s a lot in many of my low level x86 assembler libraries (gfx/sound).
Ok thanks for the hint. I just keep hearing from all sides that uint is evil and should only be used for RGB color values. 😉
uint is 4 times, and Number is 3 times slower than int in comparison functions (a
Oh, and when testing, you have to use ideal conditions. In the ceil test variable named “test” has different types in different test functions (Number and uint).
In real world you would want to use the result from Math.ceil(n) in further calculations. For that your result will get converted to either int or Number (as uints are slow). So if you actually replace
“n == uint(n) ? n : uint(n)+1;”
with
“Number(n == uint(n) ? n : uint(n)+1);”
it becomes 15% slower than usual Math.ceil(n).
I was puzzled about my last comment, and looks that I made some mistakes. So after extensive testing I found that using int instead of uint
var test:int = int(n == int(n) ? n : int(n)+1);
the code executed up to 12% faster
and using
var test:Number = Number(n == int(n) ? n : int(n)+1);
code executed up to 18% faster than the usual Math.ceil(n)
For Math.floor, another option is n>>0 – which is even faster than uint() (for me about 100 ms). Something else i found while messing with this is that if you declare the variables outside the loop, the time triples.
//for example
var n=1.5;
var time = 0;
for(var i=0i
Thanks for a really helpful post.
Don’t know what happened to my answer, but I just tried to say that if you want to switch the values of two int variables, doing it with a^=b; b^=a; a^=b; is just a tad quicker (but more fun) than c=a; a=b; b=c;
I noticed that in your examples you declare variables inside your loops. It’s quite a bit of a speed increase when you declare the variables outside of your loop and reuse them within.
Thanks for putting the other examples here, really nice to have them on the web somewhere.
[@Andy & Erik] – ha yes, thanks! makes sense. I’ll have to make a note about that as well on the new page I’ll create with these and other speed enhancements
-_-” i know now it’s not too long but tag, let’s try again with code tag
thx john!, I heard that while is faster:
function runWhileUintFloorTest():void
{
var time = getTimer();
var n:Number = 1.5;
var i:uint=0;
var test:uint;
while (i<10000000)
{
test = uint(n);
i++;
}
trace("WhileUintFloorTest: ", (getTimer()-time));
}
runWhileUintFloorTest();
result is
FloorTest: 1256
UintFloorTest: 124
WhileUintFloorTest: 100
Thanks Katopz, yep – I ran your test here and sure enough, it’s slightly faster than the for loop version.
Although, when I put the var declarations outside the for loop like people had suggested, the intFloor test is actually slightly faster than the while loop:
IntFloorTest: 131
WhileUintFloorTest: 134
Something people might also not think about when worrying about time is how much declaring the variable type can affect performance. When i remove the type decleration from the variables in this test, for example, it takes about 16x longer to compute. (Declare your variable types!)
Hey John –
What you’re actually doing is what you’d like your compiler to do: recognize common simple operations and provide faster code. I’ve been using these tricks for decades and am always looking for more. When writing graphics engines back in the mid-80’s (before smart video cards), I’d tweak code for any little advantage such as adding conditional loops to get a 16% gain in a line-drawing routine. Basically, when it comes to engines (like PV3D) where such operations are common, you’ve just gotta be a speed freak.
The practical problems come with non-adepts trying to decipher your code and not comprehending that “n –bitshift- 2 + n” is equivalent to “n * 5” only much faster.
Morf, is that YOU?! gotta be the same guy from class…GOTTA BE!
Sorry to be a party breaker, but it looks like the current int vs floor optimization only works correctly for positive numbers. For negative numbers the it gives different results:
var n:Number = -1.5;
trace( int(n) ); // traces -1
trace( Math.floor(n) ); // traces -2
trace( int(n+1) ); // traces 0
trace( Math.ceil(n) ); // traces -1
But it looks like this does the trick and it is still fast:
floor: trace (int(n) + (n >> 31));
ceil: trace (int(n+1) + (n >> 31));
I just noticed that Andy’s n>>0 method works fine also with negative numbers.
John, maybe for most practical purposes int(n) + 0.999 will work just as well for that case as the conditional you throw at it. If you need more 9s, just tack them on to the end 🙂
Test it and try it out.
Thanks Mario! excellent find and solution!
Following up on my first post I began exploring your tests and more of my own. For one thing, successive tests gave different results. To get more reliable data, I ran them many times; I noticed was that I was not getting the same results for the bitshiftRight “division”.
In the code posted, in the first test, the iterator (i) is declared as Number in the runDivisionTest() and runMultTest() loops — but it’s declared as int in the runBitTest() loop. Then I noticed you did the same thing with “test”. You dog!
With the uniform declarations, there’s still a savings – and like I said before, that’s usually worthy. But it’s not as great as originally posted. Using code with i as int and test as Number gets these results:
Mean over 50 loops
DivisionTest: 82.86
MultTest: 61.78
BitTest: 58.02
This doesn’t shock me that much. Before graphics cards and co-processors, math coding cheats were the way to amaze your geek buddies, frustrate your nerd enemies, and glaze over the eyes of your nosy boss – I don’t expect to save massive clock cycles these days.
Wtihout getting into messy innards of microprocessor math, I delved further. What if I declared test as int as well – shouldn’t that make the operations faster? The results were rather ugly:
Mean over 10 loops
DivisionTest: 244.8
MultTest: 207
BitTest: 45.2
This could indicate several things: the AS3 compiler is converting ints to Numbers before * and / (and possibly other) math operations; that the compiler has the CPU handle math on floats but creates its own (slower) code for those operations on ints; that my computer is a piece of crap (please test this hypothesis on your own boxes!).
What’s interesting here is that the BitTest *was* much faster, so there may be some really good ways of speeding up our code. Naturally, this is compelling me to explore other nuances of AS3’s math operations. Lord help me, I’m a speed freak.
see, this is why I like you – YOU ROCK \m/ Morf!
So, what I got our of your second test is that by declaring “test” as an int inside the loop made things much faster:
function runBitTest():void
{
time = getTimer();
for(var i:int=0;i<10000000;i++)
{
var test:int = i>> 1;
}
trace("BitTest: ", (getTimer()-time));
}
runBitTest();
is that what you’re saying?
Yep – as long as we’re *only* talking about the bitshift operator, ints are more than 20% faster than Numbers. I’m testing other operations as well and will update.
You know, I suppose I could just read the AS3 technical documents, but what’s the fun in that? 🙂
(yay, I got my wings!)
Whew, been working on a bunch of these… John, is there someplace you these posted? (eMail me for details)
you *want these posted
http://osflash.org/as3_speed_optimizations
I just created it – this is where I had intended to put the optimization tests and information so that the community could add / maintain it
Try testing -x versus -1*x. In AS1 at least, the compiler turns the former into 0-x, I would expect subtraction to be faster than multiplication. You may be able to change the sign with bit manipulation as well.
Thanks Robert! Yep, as you pointed out, it IS faster:
var test:Number = n < 0 ? 0-n : n; I've added to the OSFlash page
Morf has done a great job in testing Robert’s suggestion with subtraction – it’s definitely faster.
He went a step further and tested with an if statement as opposed to an inline If and THAT was faster
Nice work Morf!
You shouldn’t have n be the same value every loop. That only tests half of your conditional. Randomize it so n covers a range of positive and negative numbers. Then you can also be certain that the compiler isn’t doing any optimization tricks by detecting that n isn’t changing.
I made some expierements, and i found that all these “10x speed ups” is because that function calls was stripped.
Here’s a sample.
runFloorTest and runIntFloorTest are the same.
runFloorTestFunc uses myFloor function, which implemets “fast int flooring”.
runFloorTestClasses uses the same function, but placed into class.
import flash.utils.getTimer;
import benchmark.MyMath;
var time:Number;
function myFloor(n:Number):int {
return int(n)
}
function runFloorTest():void
{
time = getTimer();
for(var i:uint=0;i
Here's results:
FloorTest: 2239
IntFloorTest: 244
IntFloorTestFunc: 1556
IntFloorTestClass: 2912
Conclusion: the best optimization strategy is to avoid function calls.
At least until perfect times when we will have inline functions or macroses in AS.
Alas, code was truncated…
[code]import flash.utils.getTimer;
import benchmark.MyMath;
var time:Number;
function myFloor(n:Number):int {
return int(n)
}
function runFloorTest():void
{
time = getTimer();
for(var i:uint=0;i
Thanks Dan! Yeah I’d been running some tests on just simply calling a function, calling a getter or referencing a property etc and function calls are much much slower than accessing a property
>> 1 is only dealing with integers. just in case anyone missed that
hi, in Math.abs test. use
“var test:Number = n
Alas, code was truncated…
[code]import flash.utils.getTimer;
import benchmark.MyMath;
var time:Number;
function myFloor(n:Number):int {
return int(n)
}
function runFloorTest():void
{
time = getTimer();
for(var i:uint=0;i
*update*:
About “use multiplication instead of division when dividing by 2”.
It seems with the new player it’s nothing big anymore.
I tested it and got division test: 841 multi: 837 Bittest: 827
Wonder if it’s because the quad core proc. or the new flash player ?
Hey,
I just ran the tests also. It seems that for small number division is way faster. But for larger numbers multiplication by 0.5 on Numbers are way faster.
Integers are still way faster to shift.
Another word of warning – I just had to discover that the x>>0 shortcut for Math.floor(x) does not work for any x > 0x7fffffff
you know, there is something ironic about having a blog post about optimization on a blog with a theme that lags out the scrolling on my browser.
But in all seriousness, thanks for the post, save me countless milliseconds of processing time.
This was really helpful, although I did not find the same results with bit shifting. Were you testing from a local flash player or embedded in a web page? I tested math, data structures, and graphics in my optimization article http://www.stephencalenderblog.com/?p=7
Best of Luck,
Stephen
Instead of:
var test:Number= nn < 0 ? nn * -1 : nn;
you can use:
var test:Number= nn < 0 ? -nn : nn;
I find it better readable and it is slightly faster.
Regards,
Marc
Hmm, after some more testing I found out that -nn is faster than nn*-1 when you’re working with numbers.
When you are working with integers nn*-1 is faster.
But if you are working with integers. A even faster method is:
~nn + 1;