Bit shifting tricks and speeding up data structure

Report · Jan 22, 2013

I'm pretty new to working directly with bits, but it is a lot of fun. I'm converting a javascript data structure to Flash.

So I'm thinking that Math.floor(uint/32) is the same as uint >> 5, right?

And that uint % 32 is the same as uint & 31 ? Evidently this works for modulos that are powers of 2, what a cool trick.

Using both of those cut the time needed for storing and retrieving data about in half.

But it is still takes about three times longer that just using the native Object. This is in reference to my previous post http://forums.adobe.com/message/5001353#5001353 but that didn't get very far.

So if anybody has any suggestions on how else to speed this up it would be very helpful:

package {
          public class BloomFilter {
                    private var _m:uint;
                    private var _k:int;
                    private var _locations:Vector.<uint>;
                    public var _buckets:Vector.<uint>;
                    public function BloomFilter(m:uint,k:int) {
                              _m=m;
                              _k=k;
                              _locations=new Vector.<uint>  ;
                              _buckets=new Vector.<uint>  ;
                              var n:uint=Math.ceil(m/32);
                              var i:int=-1;
                              while (++i<n) {
                                        _buckets=0;
                              }
                    }
                    private function hash(v:String) {
                              var i:int=-1;
                              var X:uint;
                              var a,b:uint;
                              a=fnv_1a(v);
                              b=fnv_1a_b(a);
                              X=a%_m;
                              while (++i<_k) {
                                        _locations=X<0? (X+_m) : X;
                                        X=(X+b)%_m;
                              }
                    }
                    public function add(v:String) {
                              hash(v);
                              var i:int=-1;
                              while (++i<_k) {
                                        _buckets[_locations>>5]|=1<<(_locations&31);
                              }
                    }
                    public function test(v:String):Boolean {
                              hash(v);
                              var i:int=-1;
                              var b:uint;
                              while (++i<_k) {
                                        b=_locations;
                                         if ((_buckets[b>>5] & (1 << (b&31))) === 0) {
                                                  return false;
                                        }
                              }
                              return true;
                    }
                    // Fowler-Noll-Vo hash
                    private function fnv_1a(v:String):uint {
                              var n:int=v.length;
                              var a:uint=2166136261;
                              var c,d:uint;
                              var i:int=-1;
                              while (++i<n) {
                                        c=v.charCodeAt(i);
                                        if (d=c&0xff000000) {
                                                  a^=d>>24;
                                                  a+=(a<<1) + (a<<4) + (a<<7) + (a<<8)+ (a<<24);
                                        }
                                        if (d=c&0xff0000) {
                                                  a^=d>>16;
                                                  a+=(a<<1) + (a<<4) + (a<<7) + (a<<8)+ (a<<24);
                                        }
                                        if (d=c&0xff00) {
                                                  a^=d>>8;
                                                  a+=(a<<1) + (a<<4) + (a<<7) + (a<<8)+ (a<<24);
                                        }
                                        a^=c&0xff;
                                        a+=(a<<1) + (a<<4) + (a<<7) + (a<<8)+ (a<<24);
                              }
                              a+=a<<13;
                              a^=a>>7;
                              a+=a<<3;
                              a^=a>>17;
                              a+=a<<5;
                              return a&0xffffffff;
                    }
                    // One additional iteration of FNV
                    private function fnv_1a_b(a:uint):uint {
                              a+=(a<<1) + (a<<4) + (a<<7) + (a<<8)+ (a<<24);
                              a+=a<<13;
                              a^=a>>7;
                              a+=a<<3;
                              a^=a>>17;
                              a+=a<<5;
                              return a&0xffffffff;
                    }
           }
  }

Report · Jan 22, 2013

this is from a book being published this year:

Arithmetic Operations

There is efficiency to be gained using bitwise operators and shortcutting some of the Math class methods. But, unless you are performing many millions of operations none of the bitwise methods are worth the trouble.

Bitwise Operators

Bitwise operators can be most easily applied to any situation where you multiply or divide by a power of two. For example, instead of halving (frequently used for centering objects with a corner registration point), you can use a bitwise shift:

x/2 = x>>1

This makes almost no difference at all but is so widely repeated as a benefit that it seems to be an accepted fact. Maybe it was (and is) a greater benefit in some Flash Player versions but, while I have seen bitwise shifting touted on numerous web sites, none cited any test data to support the claim.

Here are the results of my testing in support files/Chapter 07/bitwise_arithmetic/halving.fla.

Division

// To use, comment out two of the 3 for-loops.

// Time in milliseconds when tested on my computer is listed just above each for-loop.

var xx:Number;

var n:int = 10000000;

var i:int;

var startTime:int = getTimer();

/*

// 425ms

for(i=0;i<n;i++){

xx = i/2;

}

*/

/*

// 422ms

for(i=0;i<n;i++){

xx = i*.5;

}

*/

///*

// 420ms

for(i=0;i<n;i++){

xx = i>>1;

}

//*/

trace(getTimer()-startTime);

It makes even less sense to use bitwise arithmetic for doubling. (See support files/Chapter 07/bitwise_arithmetic/halving.fla):

Multiplication

// To use, comment out one of the for-loops.

// Time in milliseconds when tested on my computer is listed just above each for-loop.

var xx:int;

var n:int = 10000000;

var i:int;

var startTime:int = getTimer();

/*

// 414ms

for(i=0;i<n;i++){

xx = i*2;

}

*/

///*

// 413ms

for(i=0;i<n;i++){

xx = i<<1;

}

//*/

trace(getTimer()-startTime);

Likewise, using bitwise shifting instead of multiplying and dividing by other powers of two provides negligible benefit.

There is a small benefit to using bitwise arithmetic in place of the modulo operator. (See support files/Chapter 07/bitwise_arithmetic/modulo.fla.)

Modulo

// To use, comment out one of the for-loops.

// Time in milliseconds when tested on my computer is listed just above each for-loop.

var p:int = 37;

var i:int;

var n:int = 10000000;

var startTime:int = getTimer();

///*

// 556ms

for(i=38;i<n;i++){

if(i%p==0){

}

//*/

/*

//445ms

for(i=38;i<n;i++){

if((i&(p-1))==0){

}

*/

trace(getTimer()-startTime);

Math Class Shortcuts

These methods actually do provide a benefit and that benefit can be significant even without needing millions of operations to realize. They are listed in alphabetical order starting with Math.abs. (See support files/Chapter 07/math_class/abs.fla, support files/Chapter 07/math_class/floor.fla etc.)

Report · Jan 22, 2013

Interesting. Is this something you are working on? Congrats if so.

I wasn't reallly expecting it to help me all that much, but it did. For the add method of my BloomFilter, changing the one line gave these times for adding about 23,000 words to my filter:

// 129 ms

_buckets[Math.floor(_locations/32)]|=1<<(_locations%32);

// 88 ms

_buckets[_locations>>5]|=1<<(_locations&31);

So not quite in half, but there were some other things I did as well. Maybe it comes from getting rid of the Math.floor()? It seems expensive to me. When I use your test with Math.floor(i/2) vs. i<<2 I get 908 ms vs 60 ms. Which seems like it could really make some differences.

As for your modulo example wouldn't it matter that you are having the & example perform an extra subtraction? On my machine I get 175 ms for the modulo and if I take away the -1 I get 66 ms. Also I thought that trick only worked for values of 2.

I don't know why my times are so different from yours, but the relationships between the values seem to be significant. I'm testing AS3 in CS5.5 publishing for 10.2 on a Mac. But in any event I think some of these tricks definately help with some of the things I'm trying to do.

Report · Jan 22, 2013

the math shortcuts, as mentioned above, have a greater benefit. (and thanks. yes, that's from a book i wrote,

Flash Game Development: In A Social, Mobile and 3D World

)

Math Class Shortcuts

These methods actually do provide a benefit and that benefit can be significant even without needing millions of operations to realize. They are listed in alphabetical order starting with Math.abs. (See support files/Chapter 07/math_class/Math.abs_v_conditional.fla, support files/Chapter 07/math_class/Math.floor_v_int.fla etc.)

Math.abs

Using

x = (y<0) ? -y: y;

instead of

x = Math.abs(y)

is about twice as fast. Unless you are using millions of Math.abs operations, you should not expect a noticeable benefit from using the inline code. In addition, the inline code is cumbersome.

var xx:int;

var n:int = 10000000;

var n2:int = n/2;

var i:int;

var startTime:int = getTimer();

//// Math.abs duration: 1016

for(i=0;i<n;i++){

xx = Math.abs(n2-i);

}

//*/

trace("Math.abs duration:",getTimer()-startTime);

///*

// conditional duration: 445

startTime = getTimer();

for(i=0;i<n;i++){

xx = (n2-i<0) ? i-n2 : n2-i;

}

//*/

trace("conditional duration:",getTimer()-startTime);

Math.ceil and Math.floor

Using

x = int(y);

Instead of

x = Math.floor(y); // y>=0

x = Math.ceil(y); // y<=0

Is about twice as fast. Unless you are using millions of Math.floor operations (with non-negative numbers), you should not expect a noticeable benefit.

var i:int;

var n:int = 10000000;

var xx:int;

var startTime:int = getTimer();

///*

// Math.floor duration: 1105

for(i=0;i<n;i++){

xx = Math.floor(i/n);

}

trace("Math.floor duration:",getTimer()-startTime);

//*/

///*

// int duration: 479

startTime = getTimer();

for(i=0;i<n;i++){

xx = int(i/n);

}

//*/

trace("int duration:",getTimer()-startTime);

Math.max

Using

x = (i>j) ? i : j;

instead of

x = Math.max(i,j);

is about twice as fast.

This shortcut is also cumbersome but has the greatest benefit (along with Math.min) of all those listed in this section. Notice the difference in time required to execute the code blocks and how few iterations are needed to demonstrate that difference.

var xx:int;

var n:int = 1000;

var i:int;

var j:int;

var startTime:int;

///*

// Math.max duration: 109

startTime = getTimer();

for(i=n-1;i>=0;i--){

for(j=n-1;j>-0;j--){

xx = Math.max(i,j);

}

trace("Math.max duration:",getTimer()-startTime);

//*/

///*

// conditional duration 43

startTime = getTimer();

for(i=n-1;i>=0;i--){

for(j=n-1;j>-0;j--){

xx = (i>j) ? i : j;

}

//*/

trace("conditional duration",getTimer()-startTime);

Math.min

Using

x = (i<j) ? i : j;

instead of

x = Math.min(i,j);

is about twice as fast.

This shortcut is also cumbersome but has the greatest benefit (along with Math.max) of all those listed in this section. Notice the difference in time required to execute the code blocks and how few iterations are needed to demonstrate that difference.

var xx:int;

var n:int = 1000;

var i:int;

var j:int;

var startTime:int;

///*

// Duration Math.min 121

startTime = getTimer();

for(i=0;i<n;i++){

for(j=0;j<n;j++){

xx = Math.min(i,j);

}

//*/

trace("Duration Math.min",getTimer()-startTime);

///*

// Duration conditional 43

startTime = getTimer();

for(i=0;i<n;i++){

for(j=0;j<n;j++){

xx = (i<j) ? i : j;

}

//*/

trace("Duration conditional",getTimer()-startTime);

Math.pow

It is two to three times faster to explicitly multiply a number variable compared to using Math.pow. That benefit even extends a little beyond integer exponents because Math.sqrt(i) is about twice as fast as Math.pow(i,.5).

var i:int;

var n:int = 10000000;

var xx:int;

var startTime:int;

///*

// exp .5: 2020, exp 2: 1533, exp 3: 1617, exp 4: 1427, exp 5: 1381, exp 10: 1391

startTime = getTimer();

for(i=0;i<n;i++){

xx = Math.pow(i,.5);

}

trace("Duration Math.pow",getTimer()-startTime);

//*/

///*

// exp .5: 1064, exp 2: 427, exp 3: 778, exp 4: 557, exp 5: 501, exp 10: 586

startTime = getTimer();

for(i=0;i<n;i++){

xx = Math.sqrt(i);

}

trace("Duration iteration",getTimer()-startTime);

//*/

Report · Jan 23, 2013

Tell me when that book comes out kglad, I'd love to read it!

Report · Jan 23, 2013

will do.

(but you'd be a better tech editor than casual reader.)

Report · Jan 23, 2013

I'm not quitting my day job . Just let me know and I'll buy!

Report · Jan 23, 2013

Here are a couple of posts that document the performance of various methods:

http://jacksondunstan.com/articles/2052#more-2052

http://jacksondunstan.com/articles/1946

http://jacksondunstan.com/articles/1341