0

I was writing a JavaScript implementation of merge sort in NodeJS, since the native V8 sort function uses quick sort, which is less efficient than merge sort in its worst case. In order to the test the performance, I made an array of 10000 elements, pre-sorted (worst-case for quick sort) and timed how long it took to sort this list with both functions. In a single execution, the native sort function takes about 16 milliseconds, where my implementation takes about 9 milliseconds. However, when executing both 100 times, the native sort takes about 2.1 milliseconds on average, and mine takes about 4.3 milliseconds. Here is my code:

const { performance } = require('perf_hooks');

function merge(a, b, func) {
    const array = new Array(a.length + b.length);
    let aIndex = 0;
    let bIndex = 0;
    while(aIndex + bIndex < array.length) {
        if(aIndex >= a.length || func(a[aIndex], b[bIndex]) > 0) {
            array[aIndex + bIndex] = b[bIndex++];
        } else {
            array[aIndex + bIndex] = a[aIndex++];
        }
    }
    return array;
}

function mergeSort(list, func) {
    if(list.length <= 1) {
        return list;
    }
    const half = list.length / 2;
    return merge(mergeSort(list.slice(0, half), func), mergeSort(list.slice(half), func), func);
}

function time(func, iters) {
    let sum = 0;
    for(let i = 0; i < iters; i++) {
        let startTime = performance.now();
        func();
        sum += performance.now() - startTime;
    }
    return sum / iters;
}

const arr = [...Array(10000).keys()];
const sortFunc = (a, b) => a - b;
console.log("JavaScript built-in sort execution time, one iteration:")
console.log(time(() => arr.sort(sortFunc), 1)); // ~16
console.log("Manually implemented merge sort execution time, one iteration:")
console.log(time(() => mergeSort(arr, sortFunc), 1)); // ~9
console.log();
console.log("JavaScript built-in sort average execution time, 100 iterations:")
console.log(time(() => arr.sort(sortFunc), 100)); // ~2.1
console.log("Manually implemented merge sort average execution time, 100 iterations:")
console.log(time(() => mergeSort(arr, sortFunc), 100)); // ~4.3

Why is it so much faster when executed repeatedly than only once, and why is this improvement more pronounced for the native sort function?

EDIT: I was able to make my algorithm more efficient by tracking array indices instead of using the slice method. My code now consistently beats v8's native sort when used on pre-sorted arrays, but loses on randomized arrays, as expected. Here is that code, for those interested:

const { performance } = require('perf_hooks');

function merge(a, b, func) {
    const array = new Array(a.length + b.length);
    let aIndex = 0;
    let bIndex = 0;
    while(aIndex + bIndex < array.length) {
        if(aIndex >= a.length || func(a[aIndex], b[bIndex]) > 0) {
            array[aIndex + bIndex] = b[bIndex++];
        } else {
            array[aIndex + bIndex] = a[aIndex++];
        }
    }
    return array;
}

function mergeSortRec(list, func, start, limit) {
    if (limit === 1) {
        return [list[start]];
    }
    const half = limit / 2 | 0;
    return merge(mergeSortRec(list, func, start, half), mergeSortRec(list, func, half + start, limit - half), func);
}

function mergeSort(list, func) {
    return mergeSortRec(list, func, 0, list.length);
}

function time(func) {
    let startTime = performance.now();
    func();
    return performance.now() - startTime;
}

const sortFunc = (a, b) => a - b;

console.log();
console.log("--- Sequential array ---");
console.log();
const sequenceArr = [...Array(10000).keys()];
console.log("JavaScript built-in sort execution time, one iteration:");
console.log(time(() => sequenceArr.slice(0).sort(sortFunc)));
console.log("Manually implemented merge sort execution time, one iteration:");
console.log(time(() => mergeSort(sequenceArr, sortFunc)));
let sum = 0;
for(let i = 0; i < 100; i++) {
    const array = sequenceArr.slice(0);
    sum += time(() => array.sort(sortFunc));
}
console.log("JavaScript built-in sort average execution time, 100 iterations:");
console.log(sum / 100);
sum = 0;
for(let i = 0; i < 100; i++) {
    sum += time(() => mergeSort(sequenceArr, sortFunc))
}
console.log("Manually implemented merge sort average execution time, 100 iterations:");
console.log(sum / 100);

console.log();
console.log("--- Randomized array ---");
console.log();
const randomArrays = new Array(101);
for(let i = 0; i < 101; i++) {
    randomArrays[i] = new Array(10000);
    for(let j = 0; j < 10000; j++) {
        randomArrays[i][j] = Math.random() * 5000 | 0;
    }
}
console.log("JavaScript built-in sort execution time, one iteration:");
console.log(time(() => randomArrays[100].slice(0).sort(sortFunc)));
console.log("Manually implemented merge sort execution time, one iteration:");
console.log(time(() => mergeSort(randomArrays[100], sortFunc)));
sum = 0;
for(let i = 0; i < 100; i++) {
    const array = randomArrays[i].slice(0)
    sum += time(() => array.sort(sortFunc));
}
console.log("JavaScript built-in sort average execution time, 100 iterations:");
console.log(sum / 100);
sum = 0;
for(let i = 0; i < 100; i++) {
    sum += time(() => mergeSort(randomArrays[i], sortFunc))
}
console.log("Manually implemented merge sort average execution time, 100 iterations:");
console.log(sum / 100);
timmcca-be
  • 188
  • 6
  • This is how V8's JIT compiler works. "hot" sections of code get micro-optimized based on a widening amount of assumptions the compiler can make about the function based on how it's called. Also, native functions have access to more tightly optimized code than non-native functions do. – Patrick Roberts Nov 06 '18 at 22:07
  • By the way, V8 `sort()` method does not use quicksort, it uses [Timsort](https://en.wikipedia.org/wiki/Timsort), which _is_ highly optimized for pre-sorted arrays. – Patrick Roberts Nov 06 '18 at 22:13
  • Interesting, thank you! Though I double checked, and according to the source code (found [here](https://github.com/v8/v8/blob/master/src/js/array.js#L239) thanks to [this answer](https://stackoverflow.com/a/37245185/10601037)), it looks like v8 uses quick sort for arrays larger than 10 elements and insertion sort when the array has 10 or fewer elements. – timmcca-be Nov 06 '18 at 23:30
  • [This source](https://mobile.twitter.com/mathias/status/1036626116654637057?lang=en) claims that the latest version of V8 will now use Timsort, as it used to. A stable sorting algorithm is not guaranteed by the ECMAScript specification, but it has been a sore spot for a few years that at least the implementors are willing to address. – Patrick Roberts Nov 07 '18 at 00:15
  • Huh, strange. I wonder why that's not in their repository yet. Thank you for letting me know! – timmcca-be Nov 07 '18 at 00:23

0 Answers0