PerformanceTests/TailBench9000/merge-sort-cps.js

   1 "use strict";
   2
   3 function createRNG(seed)
   4 {
   5     return function() {
   6         // Robert Jenkins' 32 bit integer hash function.
   7         seed = ((seed + 0x7ed55d16) + (seed << 12))  & 0xffffffff;
   8         seed = ((seed ^ 0xc761c23c) ^ (seed >>> 19)) & 0xffffffff;
   9         seed = ((seed + 0x165667b1) + (seed << 5))   & 0xffffffff;
  10         seed = ((seed + 0xd3a2646c) ^ (seed << 9))   & 0xffffffff;
  11         seed = ((seed + 0xfd7046c5) + (seed << 3))   & 0xffffffff;
  12         seed = ((seed ^ 0xb55a4f09) ^ (seed >>> 16)) & 0xffffffff;
  13         return (seed & 0xfffffff) / 0x10000000;
  14     };
  15 }
  16
  17 let random = createRNG(0x7a11bec8);
  18
  19 function mergeSorted(array, cont)
  20 {
  21     if (array.length <= 1)
  22         return cont(array);
  23
  24     let midIndex = Math.floor(array.length / 2);
  25     return mergeSorted(array.slice(0, midIndex), (left) => {
  26     return mergeSorted(array.slice(midIndex), (right) => {
  27
  28     let result = [];
  29
  30     function finish(source, index)
  31     {
  32         if (index >= source.length)
  33             return;
  34         result.push(source[index]);
  35         return finish(source, index + 1);
  36     }
  37
  38     function merge(leftIndex, rightIndex)
  39     {
  40         if (leftIndex >= left.length)
  41             return finish(right, rightIndex);
  42         if (rightIndex >= right.length)
  43             return finish(left, leftIndex);
  44
  45         let leftValue = left[leftIndex];
  46         let rightValue = right[rightIndex];
  47         if (leftValue < rightValue) {
  48             result.push(leftValue);
  49             return merge(leftIndex + 1, rightIndex);
  50         }
  51         result.push(rightValue);
  52         return merge(leftIndex, rightIndex + 1);
  53     }
  54
  55     merge(0, 0);
  56
  57     return cont(result);
  58 }); }); }
  59
  60 function checkSorted(array)
  61 {
  62     function check(index)
  63     {
  64         if (index >= array.length - 1)
  65             return;
  66
  67         if (array[index] > array[index + 1])
  68             throw new Error("array not sorted at index " + index + ": " + array);
  69
  70         return check(index + 1);
  71     }
  72
  73     check(0);
  74 }
  75
  76 function checkSpectrum(a, b)
  77 {
  78     var aMap = new Map();
  79     var bMap = new Map();
  80
  81     function add(map, value)
  82     {
  83         let existing = map.get(value);
  84         if (existing == null)
  85             existing = 0;
  86         map.set(value, existing + 1);
  87     }
  88
  89     function build(map, array, index)
  90     {
  91         if (index >= array.length)
  92             return;
  93
  94         add(map, array[index]);
  95         return build(map, array, index + 1);
  96     }
  97
  98     build(aMap, a, 0);
  99     build(bMap, b, 0);
 100
 101     function compare(keys)
 102     {
 103         let entry = keys.next();
 104         if (entry.done)
 105             return;
 106         if (aMap.get(entry.value) != bMap.get(entry.value))
 107             throw new Error("arrays don't have the same number of: " + entry.value + " (a = " + a + ", b = " + b + ")");
 108         return compare(keys);
 109     }
 110
 111     compare(aMap.keys());
 112 }
 113
 114 function buildArray(length, value)
 115 {
 116     let array = [];
 117
 118     function build()
 119     {
 120         if (array.length >= length)
 121             return;
 122         array.push(value(array.length));
 123         return build();
 124     }
 125
 126     build();
 127
 128     return array;
 129 }
 130
 131 let arrays = [
 132     buildArray(10, x => x),
 133     buildArray(10, x => -x),
 134     buildArray(1000, x => random())
 135 ];
 136
 137 function test(index)
 138 {
 139     if (index >= arrays.length)
 140         return;
 141
 142     let array = arrays[index];
 143     mergeSorted(array, (sorted) => {
 144     checkSorted(sorted);
 145     checkSpectrum(array, sorted);
 146     test(index + 1);
 147 }); }
 148
 149 for (var i = 0; i < 100; ++i)
 150     test(0);