bitwise and vs vanilla intersection

JavaScript performance comparison

Revision 2 of this test case created

Preparation code

 
<script>
Benchmark.prototype.setup = function() {
    var SET_SIZE = 500;
    var BIT_SET_SIZE = Math.ceil((SET_SIZE / 32));
    var idSet1 = [];
    var idSet2 = [];
    var idMap = [];
    var idName = parseInt("abc123", 16); // our ids are hex numbers
    var idBitSet1 = [];
    var idBitSet2 = [];
    var items = {};
    var bitIntersectedSet = [];
    var intersectedSet = [];
   
   
    // initialize bitSets
    for (var i = 0; i < BIT_SET_SIZE; i++) {
      idBitSet1.push(0);
      idBitSet2.push(0);
    }
   
    function setBit(idPosition, bitSet) {
      var bitSetIndex = parseInt((idPosition / 32), 10);
      bitSet[bitSetIndex] = bitSet[bitSetIndex] | (1 << (idPosition % 32));
      return bitSet;
    }
   
    for (var i = 0; i < SET_SIZE; i++) {
      var itemId = idName + i;
   
      if (i % 2 === 0) {
        idSet1.push(itemId);
        // Convert into idBitSet1
        // determine location in array
        idBitSet1 = setBit(i, idBitSet1);
   
      }
   
      if (i % 3 === 0) {
        idSet2.push(itemId);
        idBitSet2 = setBit(i, idBitSet2);
      }
   
      items[itemId] = {
        id: itemId
      }
   
      idMap.push(itemId);
    }
    idSet1.sort();
    idSet2.sort();
};
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
vanilla intersection
while (idSet1.length > 0 && idSet2.length > 0) {
  if (idSet1[0] < idSet2[0]) {
    idSet1.shift();
  } else if (idSet1[0] > idSet2[0]) {
    idSet2.shift();
  } else {
    items[idSet1[0]].visible = true;
    idSet1.shift();
    idSet2.shift();
  }
}
pending…
bitwise and
for (var i = 0; i < BIT_SET_SIZE; i++) {
  bitIntersectedSet.push(idBitSet1[i] & idBitSet2[i]);
  var currentBitSet = bitIntersectedSet[i];
  for (var p = 0; p < 32; p++) {
    // index is (i * 32) + whatever bit number is flipped
    var itemIndex = (i * 32) + p;
    if ( !! (1 & currentBitSet) && idMap[itemIndex]) {
      items[idMap[itemIndex]].isVisible = !! (1 & currentBitSet);
    }

    currentBitSet = currentBitSet >> 1;
  }
}
pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL. Here’s a list of current revisions for this page:

0 comments

Add a comment