Rotating an array in an efficient way is a classical programming exercise.

It’s also one that’s ripe for over-engineering for funsies.

This article describes five approaches for rotating an array and ranks their performance against each other.

The Problem

We have some array of integers of length N, from zero to infinity and beyond.

We must rotate that array some K number of times.

If K is 3 then every element in the array will move three positions to the right, except the last three elements, which will move to the beginning.

For example, if we start with this array…

[0] [1] [2] [3] [4] [5]

…and rotate it by 3, we must end up with…

[3] [4] [5] [0] [1] [2]

Constraints

• No in-place rotation - return a new array.
• N can be of arbitrary size or even zero.
• K can be of arbitrary size or zero but not negative - only rotate right.

A Naive Solution

There isn’t really one for this exercise. Even brute-force in-place rotation does not make sense as we need to create a new array anyway.

An Efficient Solution

An obvious solution to this exercise is to move all items to the new array by:

• Calculating old index + distance
• Getting its remainder over the array length to account for overflow.

public static int[] RotateByRemainderIndexing(int[] input, int distance)
{
    // validate
    if (input == null) throw new ArgumentNullException(nameof(input));
    if (distance < 0) throw new ArgumentOutOfRangeException(nameof(distance));
    if (input.Length == 0) return new int[0];

    // rotate
    var result = new int[input.Length];
    for (int i = 0; i < input.Length; ++i)
    {
        int j = (i + distance) % input.Length;
        result[j] = input[i];
    }
    return result;
}

This is already fit for purpose.

It’s a simple O(n) approach, easy to understand and scales in a linear fashion.

That said, we are still iterating the array and performing arithmetic on every single step. Yet when you think about it, all we are doing is swapping two array segments, nothing more.

Is there a way to avoid this extra leg work and go straight to copying memory?

Well, it turns out there are a number of ways to do just that.

A More Efficient Solution? Array.Copy

As a more efficient approach, we can divide an array into two segments at distance % input.Length and then copy over those segments to the new array.

public static int[] RotateByArrayCopy(int[] input, int distance)
{
    // validate
    if (input == null) throw new ArgumentNullException(nameof(input));
    if (distance < 0) throw new ArgumentOutOfRangeException(nameof(distance));
    if (input.Length == 0) return new int[0];

    // rotate
    var result = new int[input.Length];
    int diff = distance % input.Length;
    Array.Copy(input, 0, result, diff, input.Length - diff);
    Array.Copy(input, input.Length - diff, result, 0, diff);
    return result;
}

This solution does away with iterations in favour of Array.Copy to copy the underlying array data in one go.

Array.Copy is general-use and works for both value and reference types, performing boxing, unboxing and casting as required.

A More Efficient Solution? Buffer.BlockCopy

Another way of copying underlying memory is with Buffer.BlockCopy.

public static int[] RotateByBufferCopy(int[] input, int distance)
{
    // validate
    if (input == null) throw new ArgumentNullException(nameof(input));
    if (distance < 0) throw new ArgumentOutOfRangeException(nameof(distance));
    if (input.Length == 0) return new int[0];

    // rotate
    var size = sizeof(int);
    var result = new int[input.Length];
    int diff = distance % input.Length;
    Buffer.BlockCopy(input, 0, result, diff * size, (input.Length - diff) * size);
    Buffer.BlockCopy(input, (input.Length - diff) * size, result, 0, diff * size);
    return result;
}

Buffer.BlockCopy is a bit more low-level than Array.Copy and will copy the underlying bytes without regards to the type they represent.

Because of that, we must include the type size in the slice calculations.

There is also a Buffer.MemoryCopy method that takes memory pointers but as it is not CLS-compliant, I have not included it in this comparison.

A More Efficient Solution? Span.Slice.CopyTo

Yet another way to slice and copy an array is to use a Span<T>.

public static int[] RotateBySpanCopy(int[] input, int distance)
{
    // validate
    if (input == null) throw new ArgumentNullException(nameof(input));
    if (distance < 0) throw new ArgumentOutOfRangeException(nameof(distance));
    if (input.Length == 0) return new int[0];

    // rotate
    var result = new int[input.Length];
    var target = new Span<int>(result);
    var diff = distance % input.Length;
    var source1 = new Span<int>(input, 0, input.Length - diff);
    source1.CopyTo(target.Slice(diff, input.Length - diff));
    var source2 = new Span<int>(input, input.Length - diff, diff);
    source2.CopyTo(target.Slice(0, diff));

    return result;
}

Span<T> lets us work with contiguous segments of memory and enables neat stuff like in-place casting without boxing and slicing without allocation.

This algorithm uses that exact slicing ability to copy the underlying memory from the two original segments to the two target segments.

Span<T> is aware of the size it is supposed to represent (that’s what the <T> is for) and therefore we do not need to include the type size in the slice calculations.

A More Efficient Solution? Unsafe.CopyBlock

The final contender in this over-engineering race is the new(ish) Unsafe.CopyBlock from the System.Runtime.CompilerServices (aka “shush, I know what I’m doing”) assembly.

public unsafe static int[] RotateByUnsafeCopy(int[] input, int distance)
{
    // validate
    if (input == null) throw new ArgumentNullException(nameof(input));
    if (distance < 0) throw new ArgumentOutOfRangeException(nameof(distance));
    if (input.Length == 0) return new int[0];

    // prepare to rotate
    var result = new int[input.Length];
    int size = Unsafe.SizeOf<int>();
    int diff = distance % input.Length;

    // pin memory locations
    fixed (int* target1 = result.AsSpan(diff, input.Length - diff))
    fixed (int* slice1 = input.AsSpan(0, input.Length - diff))
    fixed (int* target2 = result.AsSpan(0, diff))
    fixed (int* slice2 = input.AsSpan(input.Length - diff, diff))
    {
        // copy the underlying memory in the array
        Unsafe.CopyBlock(target1, slice1, (uint)((input.Length - diff) * size));
        Unsafe.CopyBlock(target2, slice2, (uint)(diff * size));
    }

    return result;
}

Unsafe.CopyBlock is as brute-force as it gets.

It will copy memory from one place to the other without regard to the runtime shufling memory as it goes. That’s why we need to pin any memory we need to touch, lest the runtime swipes it off our algorithm’s feet.

To use it, we need to mark the method as unsafe and build the assembly with /unsafe turned on, just to prove how desperate we are.

Performance

Here is how these algorithms stack against each other…

Tap here for the full benchmark data

Here are some interesting bits from this benchmark:

• Just about anything is better than remainder indexing.
• The mean time of the memory copy methods is an order of magnitude lower than remainder indexing up 100k array size.
• Said performance takes a hit at around 1M array size. The exact point may be specific to my own computer spec.
• Copy mean time appears to stabilize at around half of remainder indexing. Again, the exact point may be specific to my own computer spec.
• The garbage collector goes to sleep when we cross-over the 100M array size mark. That may be because we’re only allocating memory in the large object heap at this point, which goes straight into GC Generation 2.
• None of the memory copy methods stand-out on the long run - they all behave the same.

In this case, it does not make sense to create a hybrid algorithm… But it does make sense to use one of the copy methods - which one wins, I’ll leave it up to you.

Takeaway

Sometimes one can benefit from over-engineering… Sometimes not… Sometimes both!

Neither of the fancy memory copy methods was significantly more performance than trusty old Array.Copy. Yet even Array.Copy by itself provided significant performance benefits over a naive remainder indexing approach. Why index what you can clone?

Resources

You can find all the code for this post in the Quicker repository, including all the benchmarks.