I was tidying up my laptop today and found the slides from a presentation I gave at Schematic a couple years ago on Bezier curves. I can’t find the demos unfortunately, but the slides are pretty funny on their own.
If I find the demos, I’ll post them here.
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:
Yikes! But Booleans are far worse:
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 ); } }