lets try to replace the slow
abs = Math.abs(integerVal);
The obvious way,
abs = j<0 ? -j : j;
The twiddling way with a subtract:
abs = ((j>>31)^j)-(j>>31);
here why it works:
when j>0, j>>31 gives 0, so (0)^j gives j, and j-0 is j
when j<0, j>>31 gives -1, and (-1)^j invert all bits on j,
so if the value was -5 , or 1111.1111.1111.1111.1111.1111.1111.1011 , ~5 gives 100, or 4, so we are just 1 below the result
and we just need to add 1 to the result , which explains the -(j>>31) in the formula, so with -5, we get +5, perfect !
We could also do +(j>>>31) instead of -(j>>31), so an alternate similar version:
abs = ((j>>31)^j)+(j>>>31);
With some assembly, we can easily avoid recomputing twice the j>>31 without introducing a temp local variable:
__asm( GetLocal(j), PushInt(31), ShiftRight, Dup, GetLocal(j), BitXor, Swap, SubtractInt, SetLocal(abs) );
And here a patented method by Sun, which use an add instead of subtract:
abs = (j>>31)^((j>>31)+j);
it can be re-written in assembly to avoid the double >>31 computation:
__asm( GetLocal(j), PushInt(31), ShiftRight, Dup, GetLocal(j), AddInt, BitXor, SetLocal(abs) );
My results:
The code:
protected function intabsTest():void { var i:int = 0; var j:int = 0; var abs:int; const REPS:int = 2000; var time1:uint = getTimer(); for(i= -REPS;i<REPS;i++) { for(j= -REPS;j<REPS;j++) { abs = Math.abs(j); } } var time2:uint = getTimer(); for(i= -REPS;i<REPS;i++) { for(j= -REPS;j<REPS;j++) { abs = j<0 ? -j : j; // if(abs != Math.abs(j)) // throw("error"); } } var time3:uint = getTimer(); for(i= -REPS;i<REPS;i++) { for(j= -REPS;j<REPS;j++) { abs = ((j>>31)^j)-(j>>31); // if(abs != Math.abs(j)) // throw("error"); } } var time4:uint = getTimer(); for(i= -REPS;i<REPS;i++) { for(j= -REPS;j<REPS;j++) { __asm( GetLocal(j), PushInt(31), ShiftRight, Dup, GetLocal(j), BitXor, Swap, SubtractInt, SetLocal(abs) ); // if(abs != Math.abs(j)) // throw("error"); } } var time5:uint = getTimer(); for(i= -REPS;i<REPS;i++) { for(j= -REPS;j<REPS;j++) { abs = (j>>31)^((j>>31)+j); // if(abs != Math.abs(j)) // throw("error"); } } var time6:uint = getTimer(); for(i= -REPS;i<REPS;i++) { for(j= -REPS;j<REPS;j++) {__asm( GetLocal(j), PushInt(31), ShiftRight, Dup, GetLocal(j), AddInt, BitXor, SetLocal(abs) ); } } var time7:uint = getTimer(); startTest(); setTest( "Math.abs" , "int abs", time2-time1 ); setTest( "i<0?-i:i" , "int abs", time3-time2 ); setTest( "abs - bit twiddling" , "int abs", time4-time3 ); setTest( "abs - asm twiddling" , "int abs", time5-time4 ); setTest( "abs + bit twiddling" , "int abs", time6-time5 ); setTest( "abs + asm twiddling" , "int abs", time7-time6 ); endTest(); }
Leave a Reply