Fastest way to move a part of an array to the right

Question

I need to "insert" an element at the given index in a small array. That is, to move all elements with greater indices 1 place to the right. What is the fastest way to do that in .NET?

NOTE: I added my own answer, but I am still looking for an explanation and faster alternatives.

EDIT: I do need an array, not a List<T> and not a linked list.

UPDATE: Since I didn't get an explanation of strange performance results, I've asked that question separately: Why is copying references to strings much slower than copying ints (but vice versa for Array.Copy())?

Answer 1

There are two obvious approaches: use Array.Copy and copy elements one by one:

private static void ElementByElement<T>(T[] arg, int start) {
    for (int i = arg.Length - 1; i > start; i--) {
        arg[i] = arg[i - 1];
    }
}

private static T BuiltInCopy<T>(T[] arg, int start) {
    Array.Copy(arg, start, arg, start + 1, arg.Length - start - 1);
    return arg[0];            
}

On one hand, List<T> insert uses Array.Copy. On the other, Array.Copy is non-generic and can do a lot of extra work: http://msdn.microsoft.com/en-us/library/z50k9bft.aspx

I expected Array.Copy to be faster. However, the results of this MiniBench test surprised me.

internal class Program {
    private static int smallArraySize = 32;

    public static void Main(string[] args) {
        BenchArrayCopy();
    }

    private static void BenchArrayCopy() {
        var smallArrayInt = new int[smallArraySize];
        for (int i = 0; i < smallArraySize; i++)
            smallArrayInt[i] = i;

        var smallArrayString = new string[smallArraySize];
        for (int i = 0; i < smallArraySize; i++)
            smallArrayString[i] = i.ToString();

        var smallArrayDateTime = new DateTime[smallArraySize];
        for (int i = 0; i < smallArraySize; i++)
            smallArrayDateTime[i] = DateTime.Now;

        var moveInt = new TestSuite<int[], int>("Move part of array right by 1: int")
            .Plus(BuiltInCopy, "Array.Copy()")
            .Plus(ElementByElement, "Element by element in a for loop")
            .RunTests(smallArrayInt, 0);

        var moveString = new TestSuite<string[], string>("Move part of array right by 1: string")
            .Plus(BuiltInCopy, "Array.Copy()")
            .Plus(ElementByElement, "Element by element in a for loop")
            .RunTests(smallArrayString, "0");

        var moveDT = new TestSuite<DateTime[], DateTime>("Move part of array right by 1: DateTime")
            .Plus(BuiltInCopy, "Array.Copy()")
            .Plus(ElementByElement, "Element by element in a for loop")
            .RunTests(smallArrayDateTime, smallArrayDateTime[0]);

        moveInt.Display(ResultColumns.All, moveInt.FindBest());
        moveString.Display(ResultColumns.All, moveInt.FindBest());
        moveDT.Display(ResultColumns.All, moveInt.FindBest());
    }

    private static T ElementByElement<T>(T[] arg) {
        int start = 8;
        for (int i = smallArraySize - 1; i > start; i--) {
            arg[i] = arg[i - 1];
        }
        return arg[0];
    }

    private static T BuiltInCopy<T>(T[] arg) {
        int start = 8;
        int length = smallArraySize - start - 1;
        Array.Copy(arg, start, arg, start + 1, length);
        return arg[0];            
    }
}

Here are the results from two runs:

f:\MyProgramming\TimSort\Benchmarks\bin\Release>Benchmarks.exe
============ Move part of array right by 1: int ============
Array.Copy()                     568475865 0:31.606 1,73
Element by element in a for loop 980013061 0:31.449 1,00

============ Move part of array right by 1: string ============
Array.Copy()                     478224336 0:31.618 2,06
Element by element in a for loop 220168237 0:30.926 4,38

============ Move part of array right by 1: DateTime ============
Array.Copy()                     382906030 0:27.870 2,27
Element by element in a for loop 458265102 0:29.239 1,99


f:\MyProgramming\TimSort\Benchmarks\bin\Release>Benchmarks.exe
============ Move part of array right by 1: int ============
Array.Copy()                     500925013 0:28.514 1,76
Element by element in a for loop 988394220 0:31.967 1,00

============ Move part of array right by 1: string ============
Array.Copy()                     483178262 0:30.048 1,92
Element by element in a for loop 193092931 0:27.642 4,43

============ Move part of array right by 1: DateTime ============
Array.Copy()                     450569361 0:30.807 2,11
Element by element in a for loop 568054290 0:31.385 1,71

That is, for int and DateTime ElementByElement is significantly faster; while for string BuiltInCopy is over twice as fast as ElementByElement (and twice as slow as ElementByElement for int). I'd expect the results for int and string to be very similar on a 32-bit machine, since a reference to string on the stack is the same size as an int and no operations other than reading and writing stack memory should be involved.

Answer 2

Perhaps using a linked list would be better in this case.

Answer 3

First I would question whether an array is an appropriate data structure choice given this requirement. However, I can see a possible optimisation in your 'element by element' copying code:

    private static void ElementByElement2<T>(T[] arg, int start)
    {
        int i = arg.Length - 1;
        while (i > start)
            arg[i] = arg[--i];
    }

I have benchmarked this and is approximately twice as fast as your for-loop solution.

Answer 4

Looking at List<T> as an example - it uses Array.Copy, suggesting that if you are constrained to using an array, then this might indeed be your best option.

Or, as Indeera notes - use a different container! Depending on the exact usage, some options

• if you are always inserting at 0, use a List<T> (or keep your own array with spare capacity, but I can't think why), but think of it backwards - so "insert" becomes "append", which is cheaper (especially if you don't have to reallocate)
• linked list is an option
• as is a queue / stack (depending on if/how you remove data)
• or for both prepend and append, keep an array with spare capacity on both sides, wrapped in something like (but more complex than) a List<T> - and maintain the offset - i.e. you have an array of 100, and know that your "zero" is 50, and you've used 20; insert at "zero" is then simple changes the value at offset 49, decrements the main zero offset to 49 and increments the virtual length to 21

Answer 5

If you want to add to a given index, you should be using a Linked list. See also: http://stackoverflow.com/questions/670104/what-are-real-world-examples-of-when-linked-lists-should-be-used