JSTests/microbenchmarks/sorting-benchmark.js

   1 function log(s)
   2 {
   3 }
   4
   5 // FIXME: Clean up.
   6 // FIXME: Can't use global resolve or built-in functions by name.
   7 // FIXME: Rules about integer truncation.
   8 // FIXME: Need to support missing comparator.
   9 var bottom_up_merge_sort = (function () {
  10         return function bottom_up_merge_sort(comparator)
  11         {
  12                 var array = this;
  13                 var length = array.length;
  14                 var copy = [ ];
  15
  16                 // Remove holes and undefineds.
  17                 var undefinedCount = 0;
  18                 for (var p in array) {
  19                         var value = array[p];
  20                         if (value === undefined) {
  21                                 ++undefinedCount;
  22                                 continue;
  23                         }
  24                         copy[copy.length] = value;
  25                 }
  26
  27                 var n = copy.length;
  28                 var a = copy;
  29                 var b = array;
  30
  31                 for (var width = 1; width < n; width = 2 * width) {
  32                         for (var i = 0; i < n; i = i + 2 * width) {
  33                                 var iLeft = i;
  34                                 var iRight = Math.min(i + width, n);
  35                                 var iEnd = Math.min(i + 2 * width, n);
  36                                 var i0 = iLeft;
  37                                 var i1 = iRight;
  38                                 var j;
  39
  40                                 for (j = iLeft; j < iEnd; j++) {
  41                                         if (i0 < iRight && (i1 >= iEnd || comparator(a[i0], a[i1]) < 0)) {
  42                                                 b[j] = a[i0];
  43                                                 i0 = i0 + 1;
  44                                         } else {
  45                                                 b[j] = a[i1];
  46                                                 i1 = i1 + 1;
  47                                         }
  48                                 }
  49                         }
  50
  51                         var tmp = a;
  52                         a = b;
  53                         b = tmp;
  54                 }
  55
  56             if (a != array) {
  57                     for(var i = 0; i < a.length; i++)
  58                         array[i] = a[i];
  59             }
  60
  61                 // Restore holes and undefineds. Result should be [ values..., undefines..., holes... ].
  62                 for (var i = 0; i < undefinedCount; ++i)
  63                         array[array.length] = undefined;
  64                 array.length = length;
  65         }
  66 })();
  67
  68 function obfuscatedAMinusB(a, b)
  69 {
  70         var A = a;
  71         var B = b;
  72         return A - B;
  73 }
  74
  75 function aMinusB(a, b)
  76 {
  77         return a - b;
  78 }
  79
  80 var sortFunctions = [ Array.prototype.sort, bottom_up_merge_sort ];
  81 var comparators = [ aMinusB, obfuscatedAMinusB ];
  82
  83 function verify(reference, array)
  84 {
  85         for (var i in reference) {
  86                 if (array[i] !== reference[i]) {
  87                         log("SORT FAIL:");
  88                         log("reference: " + reference);
  89                         log("array: " + array);
  90                         return;
  91                 }
  92         }
  93
  94         if (reference.length != array.length) {
  95                         log("SORT FAIL:");
  96                         log("reference.length: " + reference.length);
  97                         log("array.length: " + array.length);
  98         }
  99 }
 100
 101 function benchmark(f, c, array)
 102 {
 103         var start = new Date;
 104         f.call(array, c);
 105         var end = new Date;
 106
 107         // Our time resolution is not very good, so we round down small numbers to
 108         // zero in order to show that they are not meaningful.
 109         var result = end - start;
 110         if (result < 2)
 111                 result = 0;
 112
 113         log(array.length / 1024 + "k:\t" + result + "ms");
 114 }
 115
 116 function makeArrays()
 117 {
 118         var arrays = [ ];
 119         var min = 1024;
 120         var max = 4 * 1024;
 121         for (var count = min; count <= max; count *= 2) {
 122                 var array = [ ];
 123                 for (var i = 0; i < count; ++i)
 124                         array[i] = Math.floor(Math.random() * count);
 125                 arrays.push(array);
 126         }
 127
 128         arrays.push(new Array(max));
 129
 130         arrays.push((function() {
 131                 var a = [ ];
 132                 a[max - 1] = 1;
 133                 return a;
 134         })());
 135
 136 //      arrays.push((function() {
 137 //              var a = [ ];
 138 //              a[Math.pow(2, 21) - 1] = 1;
 139 //              return a;
 140 //      })());
 141
 142         return arrays;
 143 }
 144
 145 (function main() {
 146         var arrays = makeArrays();
 147         for (var c of comparators) {
 148                 log("\n" + "===== " + c.name + " =====");
 149
 150                 for (var f of sortFunctions) {
 151                         log("\n" + f.name);
 152
 153                         for (var array of arrays) {
 154                                 var copy = array.slice();
 155                                 benchmark(f, c, copy);
 156                                 verify(Array.prototype.sort.call(array.slice(), c), copy);
 157                         }
 158                 }
 159         }
 160 })();