sort-bench.ts

// Dependencies: timsort2, mitata

import { bench, do_not_optimize, run, summary, type k_state } from "mitata";
import { sort } from "timsort2";

const tests = [
  function randomInt(n: number): number[] {
    const arr: number[] = new Array(n);
    for (let i = 0; i < n; i++) {
      arr[i] = (Math.random() * 9007199254740992) | 0;
    }
    return arr;
  },

  function descendingInt(n: number): number[] {
    const arr: number[] = new Array(n);
    for (let i = 0; i < n; i++) {
      arr[i] = n - i;
    }
    return arr;
  },

  function ascendingInt(n: number): number[] {
    const arr: number[] = new Array(n);
    for (let i = 0; i < n; i++) {
      arr[i] = i;
    }
    return arr;
  },

  function ascending3RandomExchangesInt(n: number): number[] {
    const arr: number[] = new Array(n);
    for (let i = 0; i < n; i++) {
      arr[i] = i;
    }
    for (let i = 0; i < 1; i++) {
      const first = (Math.random() * n) | 0;
      const second = (Math.random() * n) | 0;
      const tmp = arr[first];
      arr[first] = arr[second];
      arr[second] = tmp;
    }
    return arr;
  },

  function ascending10RandomEndInt(n: number): number[] {
    const arr: number[] = new Array(n);
    for (let i = 0; i < n; i++) {
      arr[i] = i;
    }
    const endStart: number = Math.max(0, n - 10);
    for (let i = endStart; i < n; i++) {
      arr[i] = (Math.random() * n) | 0;
    }
    return arr;
  },

  function allEqualInt(n: number): number[] {
    const arr: number[] = new Array(n);
    for (let i = 0, c = Math.random(); i < n; i++) {
      arr[i] = c;
    }
    return arr;
  },

  function manyDuplicateInt(n: number): number[] {
    const arr: number[] = new Array(n);
    for (let i = 0; i < n; i++) {
      arr[i] = (Math.random() * ((n / 2) * Math.log10(n))) | 0;
    }
    return arr;
  },

  function someDuplicateInt(n: number): number[] {
    const arr: number[] = new Array(n);
    for (let i = 0; i < n; i++) {
      arr[i] = (Math.random() * n) | 0;
    }
    return arr;
  },
];

for (const test of tests) {
  summary(() => {
    bench('timsort2 - ' + test.name, function* (state: k_state) {
      const size = state.get('size');

      yield {
        [0]() {
          return test(size);
        },
        bench(arr: number[]) {
          do_not_optimize(sort(arr));
        }
      }
    }).range('size', 1, 2 ** 15, 2).gc('inner');

    bench('native - ' + test.name, function* (state: k_state) {
      const size = state.get('size');

      yield {
        [0]() {
          return test(size);
        },
        bench(arr: number[]) {
          do_not_optimize(arr.sort());
        }
      }
    }).range('size', 1, 2 ** 15, 2).gc('inner');
  });
}

run();