Why does .NET Array class copy so slow?

Question

I was disappointed to find that Array.Clone, Array.CopyTo, and Array.Copy can all be beat by a simple 3-line manually coded for(;;) loop:

    for(int i = 0; i < array.Length; i++)
    {
        retval[i] = array[i];
    }

Say the base case for performing an operation a few million times on an array of some predetermined size takes 10 seconds.

Using Array.Clone before each operation is abysmal extending that time to 100 seconds.

Using Array.CopyTo and Array.Copy takes only about 45 seconds.

The loop above takes only about 20 seconds.

(Forget the subjective argument of whether this makes a difference in the real world, because in the real world it's arguably just as simple to code a 3-line for(;;) loop as to look up the documentation for the Array class.)

I'm just wondering why the performance is so much different. In good old C, the simplest library function, memcpy() performs about the same as a manual for(;;) loop like the one above, and I'm wondering if there's some other array copy function in .NET that's implemented as such a nice simple for(;;) without whatever abstractions are getting in the way of Array.Clone, Array.CopyTo, and Array.Copy.

Answer 1

Don't the Array methods also have to create and allocate the output array object as well?

Answer 2

Including allocation I get the following results:
For loop: 104ms
Clone: 77ms
CopyTo: 64ms

Here's the code:

int[] values = new int[16000000];

int[] copiedValues1;
Stopwatch sw = Stopwatch.StartNew();
copiedValues1 = new int[values.Length];
for (int i = 0; i < values.Length; i++)
{
    copiedValues1[i] = values[i];
}
Console.WriteLine(sw.ElapsedMilliseconds);

int[] copiedValues2;
sw = Stopwatch.StartNew();
copiedValues2 = (int[])values.Clone();
Console.WriteLine(sw.ElapsedMilliseconds);

int[] copiedValues3;
sw = Stopwatch.StartNew();
copiedValues3 = new int[values.Length];
values.CopyTo(copiedValues3,0);
Console.WriteLine(sw.ElapsedMilliseconds);

Answer 3

Your test may have a wrinkle. A quick look with Reflector shows Array.Copy uses an externed implementation (Array.CopyTo ultimately uses the same call):

[MethodImpl(MethodImplOptions.InternalCall),
ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
internal static extern void Copy(
    Array sourceArray, 
    int sourceIndex, 
    Array destinationArray, 
    int destinationIndex, 
    int length, 
    bool reliable);

This opens up the possibility of memory copying versus item-by-item copying. My own test in Release mode, with an int[1000000] - randomly populated, clocks the loop at 468750 ticks and Array.Copy at 312500 ticks. Not a huge difference, but still faster as weiqure noted.

You may want to tweak your test to make sure there aren't other factors effecting the result.

This post makes a similar observation with Object arrays.

Answer 4

Might it have something to do with boxing?

Answer 5

You didn't mention how large the array being copied was. Perhaps the JIT doesn't specialize Array.Copy and Array.Clone for each type of array, the way it does for generic types. Consequently, the first thing these methods would have to do is examine the array to determine: is it a reference type or a value type, and if it's a value type, how large is each entry?

If I'm right, copying a small array ten million times would result in these checks being unnecessarily repeated ten million times. On the other hand, copying a one-million element array could be faster than a hand-coded loop because Array.Copy might employ optimizations for large arrays. Notably, in your hand-coded loop

for(int i = 0; i < array.Length; i++)
{
    retval[i] = array[i];
}

the JIT will optimize away the range check for array[i] because it recognizes that i is always in-range; but it probably won't remove the range check for retval[i], even if it can be easily proven to be in-range too. Since it is probably written in native code, Array.Copy can avoid these checks. Besides that, Array.Copy might use loop unrolling, and for large byte arrays might copy one machine word at a time.

But I'm just conjecturing. I don't know how to find out what Array.Copy actually does.