Proposal: Generic overloads of Array.Copy

[jamesqo]

Background

There are a lot of static Array methods that have generic overloads. Take for example Sort, BinarySearch, etc. However, there are a couple of methods where a generic overload is missing, specifically Clear, Copy, and Reverse.

This hinders optimizations, since we cannot directly access the elements in the array from C#-- we either have to call GetValue and box it, or call into the runtime to do so. So for example, if the array's length is under a certain threshold in Copy we would want to stick to a normal for-loop instead of calling into native code. However, since those methods are non-generic, that is currently impossible.

The above problem is particularly bad with Reverse: if the elements in the array are non-primitive structs, then every single element in the array will be boxed. Link to source.

In addition, the lack of type safety means that in Copy, which accepts 2 Array parameters, we have to perform extra type-checking to make sure the arrays match before the actual copy.

Proposal

We should add generic overloads of Clear, Copy, and Reverse. Any code that currently calls the non-generic overloads will automatically light-up to use these methods. (The parameters should have the same names as the non-generic overloads, so this will work with callers who use named parameters as well.)

namespace System
{
    public abstract class Array : ICloneable, IList, ICollection, IEnumerable, IStructuralComparable, IStructuralEquatable
    {
        public static void Copy<T>(T[] sourceArray, T[] destinationArray, int length);
        public static void Copy<T>(T[] sourceArray, int sourceIndex, T[] destinationArray, int destinationIndex, int length);
    }
}

edit: @justinvp has already submitted a proposal for a generic Reverse which was approved, so I removed that from the proposed API.

edit: Removed generic Clear from this proposal after @terrajobst's comment. That's now being tracked in dotnet/corefx#11839.

[jamesqo]

/cc @jkotas, @stephentoub, @justinvp, @terrajobst, @benaadams

[justinvp]

There's already an issue for Array.Reverse<T> (#2352) that's api-approved. Now that api-approved PRs are being merged, I'll submit a PR for it.

[jamesqo]

@justinvp Sounds awesome. I'll remove Reverse from this proposal then, which leaves just Clear and Copy.

[jkotas]

We have done experiments with the generic Copy and Clear methods implemented in C# in CoreRT. Compared with the low-level non-generic runtime implementation, it was slower and generated measurable code bloat.

[jamesqo]

@jkotas That's interesting. Was there a threshold at which you fell back to using the version implemented in C++, or was the managed impl used for arrays of all sizes?

[benaadams]

I imagine the issue is the code will duplicate for every struct type of T its called with; whereas the C++ implementation is just one copy.

@justinvp talking of which, make sure you use ThrowHelper for Array.Reverse<T> for that reason.

[jkotas]

was the managed impl used for arrays of all sizes?

The managed impl was used for arrays of all sizes in the experiment. It is possible to save a bit in special cases. E.g. you can save multiplication and conditional branch if you know that the array is byte[]. This saving is not much compared with cost of argument validation. And the pure C# implementation cannot do tricks like bulk write barrier that save a lot for large copies.

I guess it may be ok to add the generic overload as future proofing, to make it easier to handle these special cases in future if it proves to be worth it. The initial implementation of the generic overload should just forward the call to the non-generic version that the JIT will inline, so it should not cost much - it will just make the JIT work a bit harder.

[jamesqo]

@jkotas Awesome, that sounds like a good idea. I'll submit a pull request to CoreCLR for it when this gets marked as api-approved.

[terrajobst]

It seems to me as if the Clear<T> is questionable. Besides the future proofing argument, it seems to add zero value.

The Copy<T> seem useful because they help in detecting making stupid errors, such as copying customers to orders. I suggest we change this issue and make it only about Copy<T>. Let's do Copy<T> and don't add the generic overload for Clear.

[jkotas]

The Copy<T> seem useful because they help in detecting making stupid errors

As long as we keep the current non-generic Array.Copy next to it, it will not detect these errors. The C# compiler will fallback to the non-generic version if you get a mismatch.

[jamesqo]

@jkotas I think generic Copy<T> methods should be beneficial regardless, since we no longer have to call GetLowerBound(0) for the index-less overload. Avoiding these calls has been shown to improve perf significantly.

@terrajobst I'll move generic Clear into another proposal for now. Does this still sound good after what @jkotas mentioned?

[terrajobst]

@terrajobst I'll move generic Clear into another proposal for now. Does this still sound good after what @jkotas mentioned?

@jkotas' point eliminates the usefulness from a pure API perspective. That doesn't mean I'm against it, but it does mean the only use would be performance gains. So I'd leave the decision to @jkotas.

[jkotas]

Better performance is really the only good reason to add this API, but there is no evidence that it really does that. We should not be adding the API with a hope that it may improve something in the future - related discussion in https://github.com/dotnet/corefx/issues/13374. We can reconsider if the generic implementation is proved to provide significant performance advantage over the existing non-generic one (and equivalent optimization cannot be reasonably applied to the existing non-generic implementation).

[AlexGhiondea]

I am going to close this issue. If in the future we figure out a good way to make these APIs faster we will add them at that time.

As always, feel free to reactivate.