Bit compressing in JavaScript

Question

I have an bit array var data = []; ... and I have the following function:

jsPerf

function getBit(n) {
 return (data[~~(n / 32)] >> (n % 32)) & 1;
}

Because this is a bottleneck, I need the fastest cross-browser solution in my code, can anybody help make it any faster?

Also, ~~(n / 32) === Math.floor(n / 32)

It can be algorithm optimization or syntax optimization (such as asm.js) or something else. Should I change the array type (typedArray or similar)?

• Mike Cluck: You're right that a TypedArray is generally much faster for such things. Have you tried using one and compared speeds?
• Sukhanov Niсkolay: No, one sec, i will create tests.
• Cameron: How are you using getBit (is there a way to process whole words at once more efficiently)?
• T.J. Crowder: "PS: ~~(n / 32) === Math.floor(n / 32)" Only if n isn't negative. ;-) And only if n / 32 is also <= 32,767 (e.g., won't get truncated when it does its round-trip through being a 32-bit integer).
• Cameron: The JS optimizers are really quite good. They certainly do constant expression folding (use a random number in your tests, not 3), and seem to simplify based on type information too, probably resulting in the same assembly code for all of the tested versions so far (which is why the timing is so close).

Answer 1

I tried to speed up your formula :

return (data[n >> 5] >> (n & 31)) & 1;

.... All results are very close anyway : jsperf.com/fastest-bit-compressing/7.

• notice that you can inline the function by yourself (replace function call by direct computation).

• you might wan to cache latest array access by yourself during your computations.

• Or you might want to do the caching in the function. Efficiency will depends on the 'randomness' of your use of the bits.

function getBit(n) {
 var itemIndex = n >> 5;
 if (itemIndex != lastItemIndex ) {
 lastItem = data[itemIndex];
 lastItemIndex = itemIndex ;
 }
 return lastItem >> (n & 31)) & 1;
}
var lastItemIndex = -1, lastItem = 0;

• Sukhanov Niсkolay: I'm afraid that this checking will cost as much as all calculations.
• GameAlchemist: Yes the last function might be faster for a big array / continuos access, but i doubt a bit also. Useless to test it with jsperf so not that easy / fast to test as other ways.
• Sukhanov Niсkolay: Your solution is the fastest. (without caching) Tested in product code, render time decreased from 3s to 2500ms. See jsperf.