current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 3 down vote favorite

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

share|improve this question

migrated from stackoverflow.com Jul 16 '14 at 15:52

This question came from our site for professional and enthusiast programmers.
    
You're right that a TypedArray is generally much faster for such things. Have you tried using one and compared speeds? –  Mike C Jul 14 '14 at 14:16
    
No, one sec, i will create tests. –  Sukhanov Niсkolay Jul 14 '14 at 14:16
    
How are you using getBit (is there a way to process whole words at once more efficiently)? –  Cameron Jul 14 '14 at 14:19
2  
"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). –  T.J. Crowder Jul 14 '14 at 14:19
1  
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). –  Cameron Jul 14 '14 at 14:50

1 Answer 1

up vote 2 down vote accepted

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;
share|improve this answer
1  
I'm afraid that this checking will cost as much as all calculations. –  Sukhanov Niсkolay Jul 14 '14 at 15:06
    
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. –  GameAlchemist Jul 14 '14 at 15:17
    
Your solution is the fastest. (without caching) Tested in product code, render time decreased from 3s to 2500ms. See jsperf. –  Sukhanov Niсkolay Jul 14 '14 at 15:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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