generalrelativity

Arrays are memory hogs when compared to their strong-typed, faster, rich and handsome cousins, Vectors, for a whole bunch of reasons that you can read about elsewhere. I was surprised, though, to find how enormous the difference in their memory footprints were:

• (10000000 / 32) uints in a Vector (10000000 bits) = ~7k
• (10000000 / 32) uints in an Array (10000000 bits) = ~1228k

Yikes! But Booleans are far worse:

• 10000000 Booleans in a Vector = ~8k
• 10000000 Booleans in an Array = ~39070k

I didn’t do the math, but I’m fairly sure that’s like 3 terabytes per Boolean. Now, it makes sense that Booleans don’t get packed anywhere close to perfectly… does anyone know how much memory gets opened for a Boolean? Probably 4 bytes, but I don’t know, to be honest.

What’s interesting, however, is that it appears, based on ratio, that Booleans are being intelligently stored by the VM in the case of Vectors. Not as tightly as possible, and hence the probably masturbatory BitVector.

Michael, over at Polygonal Labs, posted a nice and as-usual informative article on bit vectors back when people still knew what AS2 was. There’s also an implementation in his data structures library. We can definitely get much better performance, though, using a Vector.<uint>. Here’s my implementation. The bitwise OR and AND are much faster than Boolean logic of the same case and obviously setting all bits on or off will be faster than iterating over a Boolean Vector. If anyone thinks they’d actually use it, I’d be happy to add all the bitwise operations.

So what would this be used for? Firstly, it naturally extends the ability to store Boolean logic via bitwise operations in an unsigned integer’s bits past its 32 threshold all the way… to n!

I used it recently in mapping key presses to emulate AS2’s Key.isDown convenience method. When a key is pressed, the bit sitting at that key’s code is switched on. When the key is released, the corresponding bit is switched off. Combinations could easily be stored as BitVector masks. Here’s the Key class.

Christer Ericson, in his awesome Real Time Collision Detection suggests using a bit vector in avoiding retesting 2 objects for collision detection. He shows that this can be stored in n(n - 1)/2 bits instead of n², where n is the number of objects. The unique index for any 2 objects is then:

bit = min(2n - min - 3)/2 + max - 1

Where min and max represent the indices of the objects being tested.

Using my BitVector class, the implementation would look something like this:

//offline
var n:uint = objects.length;
var bv:BitVector = new BitVector( null, n * ( n - 1 ) / 2 );
 
//test
function handleCollision( minObj:CollidableObject, maxObj:CollidableObject ) : void
{
 
   var bit:uint = minObj.index * ( 2 * n - minObj.index - 3 ) / 2 + maxObj.index - 1;
   if( !bv.getBit( bit ) )
   {
       //test for collision
      bv.setBit( bit, true );
   }
 
}

BitVector.as
Key.as

drew ActionScript 3.0, Flash Player 10