Pinsave/counterstrike

1/* -*- Mode: js; js-indent-level: 2; -*- */2/*3 * Copyright 2011 Mozilla Foundation and contributors4 * Licensed under the New BSD license. See LICENSE or:5 * http://opensource.org/licenses/BSD-3-Clause6 */7 8// It turns out that some (most?) JavaScript engines don't self-host9// `Array.prototype.sort`. This makes sense because C++ will likely remain10// faster than JS when doing raw CPU-intensive sorting. However, when using a11// custom comparator function, calling back and forth between the VM's C++ and12// JIT'd JS is rather slow *and* loses JIT type information, resulting in13// worse generated code for the comparator function than would be optimal. In14// fact, when sorting with a comparator, these costs outweigh the benefits of15// sorting in C++. By using our own JS-implemented Quick Sort (below), we get16// a ~3500ms mean speed-up in `bench/bench.html`.17 18function SortTemplate(comparator) {19 20/**21 * Swap the elements indexed by `x` and `y` in the array `ary`.22 *23 * @param {Array} ary24 *        The array.25 * @param {Number} x26 *        The index of the first item.27 * @param {Number} y28 *        The index of the second item.29 */30function swap(ary, x, y) {31  var temp = ary[x];32  ary[x] = ary[y];33  ary[y] = temp;34}35 36/**37 * Returns a random integer within the range `low .. high` inclusive.38 *39 * @param {Number} low40 *        The lower bound on the range.41 * @param {Number} high42 *        The upper bound on the range.43 */44function randomIntInRange(low, high) {45  return Math.round(low + (Math.random() * (high - low)));46}47 48/**49 * The Quick Sort algorithm.50 *51 * @param {Array} ary52 *        An array to sort.53 * @param {function} comparator54 *        Function to use to compare two items.55 * @param {Number} p56 *        Start index of the array57 * @param {Number} r58 *        End index of the array59 */60function doQuickSort(ary, comparator, p, r) {61  // If our lower bound is less than our upper bound, we (1) partition the62  // array into two pieces and (2) recurse on each half. If it is not, this is63  // the empty array and our base case.64 65  if (p < r) {66    // (1) Partitioning.67    //68    // The partitioning chooses a pivot between `p` and `r` and moves all69    // elements that are less than or equal to the pivot to the before it, and70    // all the elements that are greater than it after it. The effect is that71    // once partition is done, the pivot is in the exact place it will be when72    // the array is put in sorted order, and it will not need to be moved73    // again. This runs in O(n) time.74 75    // Always choose a random pivot so that an input array which is reverse76    // sorted does not cause O(n^2) running time.77    var pivotIndex = randomIntInRange(p, r);78    var i = p - 1;79 80    swap(ary, pivotIndex, r);81    var pivot = ary[r];82 83    // Immediately after `j` is incremented in this loop, the following hold84    // true:85    //86    //   * Every element in `ary[p .. i]` is less than or equal to the pivot.87    //88    //   * Every element in `ary[i+1 .. j-1]` is greater than the pivot.89    for (var j = p; j < r; j++) {90      if (comparator(ary[j], pivot, false) <= 0) {91        i += 1;92        swap(ary, i, j);93      }94    }95 96    swap(ary, i + 1, j);97    var q = i + 1;98 99    // (2) Recurse on each half.100 101    doQuickSort(ary, comparator, p, q - 1);102    doQuickSort(ary, comparator, q + 1, r);103  }104}105 106  return doQuickSort;107}108 109function cloneSort(comparator) {110  let template = SortTemplate.toString();111  let templateFn = new Function(`return ${template}`)();112  return templateFn(comparator);113}114 115/**116 * Sort the given array in-place with the given comparator function.117 *118 * @param {Array} ary119 *        An array to sort.120 * @param {function} comparator121 *        Function to use to compare two items.122 */123 124let sortCache = new WeakMap();125exports.quickSort = function (ary, comparator, start = 0) {126  let doQuickSort = sortCache.get(comparator);127  if (doQuickSort === void 0) {128    doQuickSort = cloneSort(comparator);129    sortCache.set(comparator, doQuickSort);130  }131  doQuickSort(ary, comparator, start, ary.length - 1);132};133