3
\$\begingroup\$

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)?

\$\endgroup\$
7
  • \$\begingroup\$ You're right that a TypedArray is generally much faster for such things. Have you tried using one and compared speeds? \$\endgroup\$
    – Mike Cluck
    Commented Jul 14, 2014 at 14:16
  • \$\begingroup\$ No, one sec, i will create tests. \$\endgroup\$ Commented Jul 14, 2014 at 14:16
  • \$\begingroup\$ How are you using getBit (is there a way to process whole words at once more efficiently)? \$\endgroup\$
    – Cameron
    Commented Jul 14, 2014 at 14:19
  • 2
    \$\begingroup\$ "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). \$\endgroup\$ Commented Jul 14, 2014 at 14:19
  • 1
    \$\begingroup\$ 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). \$\endgroup\$
    – Cameron
    Commented Jul 14, 2014 at 14:50

1 Answer 1

2
\$\begingroup\$

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;
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I'm afraid that this checking will cost as much as all calculations. \$\endgroup\$ Commented Jul 14, 2014 at 15:06
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Jul 14, 2014 at 15:17
  • \$\begingroup\$ Your solution is the fastest. (without caching) Tested in product code, render time decreased from 3s to 2500ms. See jsperf. \$\endgroup\$ Commented Jul 14, 2014 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.