reordered binary search and cache-misses.js

/* Reordered binary search and cache-misses. Thanks for idea, http://www.linux.org.ru/people/ckotinko/profile. */

var n = 800000;
var ENABLE_TYPED_ARRAYS = 1;
var MAKE_SOLID = 1;

var $G = this;

var MyArray = 
  ENABLE_TYPED_ARRAYS && (
    /* $G.Float32Array || 
    $G.WebGLFloatArray || 
    $G.CanvasFloatArray */
    $G.Int32Array || 
    $G.WebGLIntArray || 
    $G.CanvasIntArray
  ) || 
  MAKE_SOLID && function(n) // make solid!
  {
    var a = Array(n);
    var i = n; while(i--)
      a[i] = 0;
    return a;  
  } ||
  Array
;  

var _reorderArray = function(a)
{
  var o = [];
  var _do = function(b, e, i)
  {
    //console.log(b, e, i);
    if(b >= e) return;
    var c = (b + e) >> 1;
    
    //console.log(c, '->', i - 1);
    o[i - 1] = a[c];
    //console.log(o);
    if(b < c)
    {
      _do(b, c, 2*i);
      _do(c + 1, e, 2*i + 1);
    }
  };
  
  _do(0, a.length, 1);
  
  // make array solid
  var o2 = new MyArray(o.length);
  var i = o.length; while(i--)
    if(o[i] != null) o2[i] = o[i];
  return o2;
};

var _bIndexOfClassic = function(a, v)
{
  var b = 0, e = a.length;
  
  if(a[b] == v) return 0;
  if(a[e - 1] == v) return e - 1;
  
  while(e - b > 2)
  {
    var c = (b + e) >> 1;
    var v2 = a[c];
    if(v2 == v) return c;
    else if(v2 < v) b = c;
    else e = c;
  }
  
  while(b < e && a[b] != v)
    ++b;
    
  return b;  
};


var _bIndexOfNew = function(a, v)
{
  var i = 1, v2;
  
  while((v2 = a[i - 1]) != v)
  {
    //console.log(i - 1, a[i - 1]);
    i <<= 1;
    if(v2 < v) ++i;
  }
  
  return i - 1;
};

var _bIndexOfNew2 = function(a, v)
{
  var i = 1, v2;
  
  while(a[i - 1] != v)
  {
    //console.log(i - 1, a[i - 1]);
    //i <<= 1;
    if(a[i - 1] < v) 
      i = (i << 1) + 1;
    else
      i <<= 1;
  }
  
  return i - 1;
};


var a = new MyArray(n);
var i = a.length; while(i--) 
  a[i] = i|0; // fix for stupid FF4
  
//console.log(_bIndexOfClassic(a, 1));
//console.log(_bIndexOfClassic(a, 8));
//console.log(_bIndexOfClassic(a, 5));

var reorderedA = _reorderArray(a);
//console.log(reorderedA); 
//var i = a.length; while(i-- && reorderedA[_bIndexOfNew(reorderedA, i)] == i)
//  ;
//console.log(i);
//  console.log(a[_bIndexOfClassic(a, i)]);
//console.log(_bIndexOfNew(reorderedA, 8));
//console.log(_bIndexOfNew(a, 8));
//console.log(_bIndexOfNew(a, 5));

//return;

_speedTest({
  '_bIndexOfClassic': function(k)
  {
    var sum = 0;
    while(k--)
    {
      var i = n; while(i--)
        sum += _bIndexOfClassic(a, i);
    }
    return sum;
  },
  '_bIndexOfNew': function(k)
  {
    var sum = 0;
    while(k--)
    {
      var i = n; while(i--)
        sum += _bIndexOfNew(reorderedA, i);
    }
    return sum;
  },
  '_bIndexOfNew2': null && function(k)
  {
    var sum = 0;
    while(k--)
    {
      var i = n; while(i--)
        sum += _bIndexOfNew2(reorderedA, i);
    }
    return sum;
  }
}, 1);  


/*
  chrome 11 2000000
    +typed S32
      _bIndexOfClassic: 2*1871 ms
      _bIndexOfNew: 2*1277 ms
    +typed F32
      _bIndexOfClassic: 2*3901 ms
      _bIndexOfNew: 2*3184 ms    
    -typed +solid
      _bIndexOfClassic: 1222 ms
      _bIndexOfNew: 1173 ms
    -typed -solid
      _bIndexOfClassic: 1054 ms
      _bIndexOfNew: 992 ms
  opera 10.52 1000000
    +solid
      _bIndexOfClassic: 1070 ms
      _bIndexOfNew: 1073 ms
    -solid
      _bIndexOfClassic: 1067 ms
      _bIndexOfNew: 1060 ms
  opera 11 100000
    +solid  
      _bIndexOfClassic: 1916 ms
      _bIndexOfNew: 1499 ms
    -solid
      _bIndexOfClassic: 1895 ms
      _bIndexOfNew: 1425 ms  
  ff3.6 40000
    +solid
      _bIndexOfClassic: 787 ms
      _bIndexOfNew: 492 ms
    -solid
      _bIndexOfClassic: 795 ms
      _bIndexOfNew: 502 ms    
  ff4 1000000
    +typed S32
      _bIndexOfClassic: 1075 ms
      _bIndexOfNew: 866 ms
    +typed F32
      _bIndexOfClassic: 8695 ms
      _bIndexOfNew: 1179 ms
    -typed +solid
      _bIndexOfClassic: 4350 ms
      _bIndexOfNew: 3710 ms  
    -typed -solid
      _bIndexOfClassic: 4190 ms
      _bIndexOfNew: 3760 ms    
  ie8 40000
    +solid
      _bIndexOfClassic: 981 ms
      _bIndexOfNew: 491 ms    
    -solid
      _bIndexOfClassic: 962 ms
      _bIndexOfNew: 490 ms
  safari5 500000
    +solid
      _bIndexOfClassic: 834 ms
      _bIndexOfNew: 619 ms
    -solid
      _bIndexOfClassic: 4123 ms
      _bIndexOfNew: 1626 ms
*/

/* 
  Conclusion
    1) reordered binary search is better than ordinary in all engines. Cache-misses in js has pronounced effect.
    2) typed array is efficient only on ff4 and only S32, F32 has big fail in random access. I'll investigate varios typed arrays later.
    3) great advantage of solid arrays in JSC(safari5). ff4 has this optimization too but it doesnt works. In v8 holed is slightly faster.
*/