What is the most efficient way to reverse an array in Javascript?

Question

I was asked recently what was the most efficient way to reverse an array in Javascript. At the moment, I suggested using a for loop and fiddling with the array but then realized there is a native Array.reverse() method.

For curiosity's sake, can anyone help me explore this by showing examples or pointing in the right direction so I can read into this? Any suggestions regarding how to measure performance would be awesome too.

Answer 1

Based on this setup:

var array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
var length = array.length;

Array.reverse(); is the first or second slowest!

The benchmarks are here:

https://jsperf.com/js-array-reverse-vs-while-loop/9

Across browsers, swap loops are faster. There are two common types of swap algorithms (see Wikipedia), each with two variations.

The two types of swap algorithms are temporary swap and XOR swap.

The two variations handle index calculations differently. The first variation compares the current left index and the right index and then decrements the right index of the array. The second variation compares the current left index and the length divided by half and then recalculates the right index for each iteration.

You may or may not see huge differences between the two variations. For example, in Chrome 18, the first variations of the temporary swap and XOR swap are over 60% slower than the second variations, but in Opera 12, both variations of the temporary swap and XOR swap have similar performance.

Temporary swap:

First variation:

function temporarySwap(array)
{
    var left = null;
    var right = null;
    var length = array.length;
    for (left = 0, right = length - 1; left < right; left += 1, right -= 1)
    {
        var temporary = array[left];
        array[left] = array[right];
        array[right] = temporary;
    }
    return array;
}

Second variation:

function temporarySwapHalf(array)
{
    var left = null;
    var right = null;
    var length = array.length;
    for (left = 0; left < length / 2; left += 1)
    {
        right = length - 1 - left;
        var temporary = array[left];
        array[left] = array[right];
        array[right] = temporary;
    }
    return array;
}

---

XOR swap:

First variation:

function xorSwap(array)
{
    var i = null;
    var r = null;
    var length = array.length;
    for (i = 0, r = length - 1; i < r; i += 1, r -= 1)
    {
        var left = array[i];
        var right = array[r];
        left ^= right;
        right ^= left;
        left ^= right;
        array[i] = left;
        array[r] = right;
    }
    return array;
}

Second variation:

function xorSwapHalf(array)
{
    var i = null;
    var r = null;
    var length = array.length;
    for (i = 0; i < length / 2; i += 1)
    {
        r = length - 1 - i;
        var left = array[i];
        var right = array[r];
        left ^= right;
        right ^= left;
        left ^= right;
        array[i] = left;
        array[r] = right;
    }
    return array;
}

---

There is another swap method called destructuring assignment: http://wiki.ecmascript.org/doku.php?id=harmony:destructuring

Destructuring assignment:

First variation:

function destructuringSwap(array)
{
    var left = null;
    var right = null;
    var length = array.length;
    for (left = 0, right = length - 1; left < right; left += 1, right -= 1)
    {
        [array[left], array[right]] = [array[right], array[left]];
    }
    return array;
}

Second variation:

function destructuringSwapHalf(array)
{
    var left = null;
    var right = null;
    var length = array.length;
    for (left = 0; left < length / 2; left += 1)
    {
        right = length - 1 - left;
        [array[left], array[right]] = [array[right], array[left]];
    }
    return array;
}

Right now, an algorithm using destructuring assignment is the slowest of them all. It is even slower than Array.reverse();. However, the algorithms using destructuring assignments and Array.reverse(); methods are the shortest examples, and they look the cleanest. I hope their performance gets better in the future.

---

Another mention is that modern browsers are improving their performance of array push and splice operations.

In Firefox 10, this for loop algorithm using array push and splice rivals the temporary swap and XOR swap loop algorithms.

for (length -= 2; length > -1; length -= 1)
{
    array.push(array[length]);
    array.splice(length, 1);
}

However, you should probably stick with the swap loop algorithms until many of the other browsers match or exceed their array push and splice performance.