Proposal: Remove covariance on array

[hez2010]

Proposal: Remove covariance on array

Prev discussion: dotnet/csharplang#5153

Basically covariance on array allows us to upcast an array. But it also leads to the following issue:

Base[] array = new Derived[10];
array[0] = new Base(); // exception here, type system is broken

class Base {}
class Derived : Base {}

It's breaking the type system: a type error occurred in runtime regardless the compile-time type check.

And also, an interesting case:

Random[] a = new Random[1];
object[] c = a;
MemoryMarshal.GetArrayDataReference(c) = "a string";
var l = a[0].Next(); // guess what method is actually being called
Console.WriteLine(l);

Covariance array is not only breaking the type system, but also has huge performance impact, let's see the benchmark (provided by @huoyaoyuan):

    class Base
    {
    }

    class Derived : Base
    {
    }

    [SimpleJob(RuntimeMoniker.Net60)]
    public class Program
    {
        static void Main(string[] args)
        {
            BenchmarkRunner.Run<Program>();
        }

        private readonly Base[] array = new Base[256];
        private Derived derived = new();
        private Base @base = new();
        private readonly int[] intArray = new int[256];

        [Benchmark]
        public object Array()
        {
            for (int i = 0; i < array.Length; i++)
                array[i] = derived;
            return array;
        }

        [Benchmark]
        public object ArrayBase()
        {
            for (int i = 0; i < array.Length; i++)
                array[i] = @base;
            return array;
        }
        
        [Benchmark]
        public object ArrayInt()
        {
            for (int i = 0; i < intArray.Length; i++)
                intArray[i] = 19260817;
            return intArray;
        }

        [Benchmark]
        public object SpanIndex()
        {
            Span<Base> span = array;
            for (int i = 0; i < span.Length; i++)
                span[i] = derived;
            return array;
        }

        [Benchmark]
        public object SpanRef()
        {
            Span<Base> span = array;
            foreach (ref var x in span)
                x = derived;
            return array;
        }
    }

Benchmark result:

Method	Mean	Error	StdDev
Array	1,490.6 ns	6.19 ns	5.17 ns
ArrayBase	600.3 ns	1.13 ns	1.06 ns
ArrayInt	113.1 ns	0.72 ns	0.67 ns
SpanIndex	435.9 ns	1.28 ns	1.00 ns
SpanRef	435.1 ns	0.43 ns	0.40 ns

The overhead of array covariance is significant.

As you can see, array covariance makes code completely unsafe and can lead to undefined behavior, and it also makes writes to array much slower. Its benefit-harm ratio is minus:

Benefits:

• You can upcast an array

Harm:

• It can easily bypass the compile-time type check without a line of unsafe code
• It breaks the type system and leads to runtime exception of type mismatch despite successful compilation
• It introduces unnecessary runtime check against type of elements in an array which introduces more runtime overhead
• It makes JIT hard to optimize against arrays
• It can lead to undefined behavior easily and can bypass the runtime check

To examine the usage of covariance array, I wrote an analyzer to help detect such usage in assembiles. I ran it against .NET + ASP.NET Core assembiles, and it turned out that the usage is rare.

The analyzer: https://github.com/hez2010/ArrayUpcastAnalyzer
Here is the analysis report: report.txt

Note that there may be some false positives, such as object[] array = (object[])obj; where obj is object.

Most usages can be avoided via casting the type of element in array initializer (i.e. change object[] x = new T[] { new T() ... } to object[] x = new object[] { (object)new T()... }), which can be done by Roslyn automatically, and after this change, the left usages are nearly none. So it's totally fine to remove covariance on array, since it has never been widely adopted.

Array is a fundamental thing, and its performance affects vast range of applications. Now that the usage of covariance on array is actually rare, let's remove covariance on array to deliver type-safe and high-performance array for everyone

Approaches

• Make arrays invariant by default, and introduce a new array type which is covariant
• Keep arrays covariant by default, and introduce a new array type which is invariant
• Completely disallow covariance on arrays

I will prefer the first approach though it will introduce breaking changes, but we can have a guidance to help users migrate their code (basically find'n'replace). The second one seems doable but it requires users to adopt it manually, which makes no difference with today's Span<>: ton of code will still use the slow covariant arrays. While the third one is more aggressive, but it may make existing code hard to migrate.

[ghost]

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

[EgorBo]

It seems to be one of those features .NET team regrets adding in terms of both perf impact and compile-time safety
but I'd guess it needs a proper analysis how many codebases this breaking change would brake.

References:

• ARRAY COVARIANCE: NOT JUST UGLY, BUT SLOW TOO by Jon Skeet
• "If I had a Gene that could fix any code, I would remove the unsafe covariance of arrays completely." by Eric Lippert
• Also, AFAIR both runtime and Roslyn use "struct" wrappers for reference types in order to avoid covariance checks for array (for better perf) in perf sensitive places.

[ghost]

Tagging subscribers to this area: @dotnet/area-system-runtime
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Proposal: Remove covariance on array

Prev discussion: dotnet/csharplang#5153

Basically covariance on array allows us to upcast an array. But it also leads to the following issue:

Base[] array = new Derived[10];
array[0] = new Base(); // exception here, type system is broken

class Base {}
class Derived : Base {}

It's breaking the type system: a type error occurred in runtime regardless the compile-time type check.

And also, an interesting case:

Random[] a = new Random[1];
object[] c = a;
MemoryMarshal.GetArrayDataReference(c) = "a string";
var l = a[0].Next(); // guess what method is actually being called
Console.WriteLine(l);

Covariance array is not only breaking the type system, but also has huge performance impact, let's see the benchmark (provided by @huoyaoyuan):

    class Base
    {
    }

    class Derived : Base
    {
    }

    [SimpleJob(RuntimeMoniker.Net60)]
    public class Program
    {
        static void Main(string[] args)
        {
            BenchmarkRunner.Run<Program>();
        }

        private readonly Base[] array = new Base[256];
        private Derived derived = new();
        private Base @base = new();
        private readonly int[] intArray = new int[256];

        [Benchmark]
        public object Array()
        {
            for (int i = 0; i < array.Length; i++)
                array[i] = derived;
            return array;
        }

        [Benchmark]
        public object ArrayBase()
        {
            for (int i = 0; i < array.Length; i++)
                array[i] = @base;
            return array;
        }
        
        [Benchmark]
        public object ArrayInt()
        {
            for (int i = 0; i < intArray.Length; i++)
                intArray[i] = 19260817;
            return intArray;
        }

        [Benchmark]
        public object SpanIndex()
        {
            Span<Base> span = array;
            for (int i = 0; i < span.Length; i++)
                span[i] = derived;
            return array;
        }

        [Benchmark]
        public object SpanRef()
        {
            Span<Base> span = array;
            foreach (ref var x in span)
                x = derived;
            return array;
        }
    }

Benchmark result:

Method	Mean	Error	StdDev
Array	1,490.6 ns	6.19 ns	5.17 ns
ArrayBase	600.3 ns	1.13 ns	1.06 ns
ArrayInt	113.1 ns	0.72 ns	0.67 ns
SpanIndex	435.9 ns	1.28 ns	1.00 ns
SpanRef	435.1 ns	0.43 ns	0.40 ns

The overhead of array covariance is significant.

As you can see, array covariance makes code completely unsafe and can lead to undefined behavior, and it also makes writes to array much slower. Its benefit-harm ratio is minus:

Benefits:

• You can upcast an array

Harm:

• It can easily bypass the compile-time type check without a line of unsafe code
• It breaks the type system and leads to runtime exception of type mismatch despite successful compilation
• It introduces unnecessary runtime check against type of elements in an array which introduces more runtime overhead
• It makes JIT hard to optimize against arrays
• It can lead to undefined behavior easily and can bypass the runtime check

To examine the usage of covariance array, I wrote an analyzer to help detect such usage in assembiles. I ran it against .NET + ASP.NET Core assembiles, and it turned out that the usage is rare.

The analyzer: https://github.com/hez2010/ArrayUpcastAnalyzer
Here is the analysis report: report.txt

Note that there may be some false positives, such as object[] array = (object[])obj; where obj is object.

Most usages can be avoided via casting the type of element in array initializer (i.e. change object[] x = new T[] { new T() ... } to object[] x = new object[] { (object)new T()... }), which can be done by Roslyn automatically, and after this change, the left usages are nearly none. So it's totally fine to remove covariance on array, since it has never been widely adopted.

Array is a fundamental thing, and its performance affects vast range of applications. Now that the usage of covariance on array is actually rare, let's remove covariance on array to deliver type-safe and high-performance array for everyone

Author:	hez2010
Assignees:	-
Labels:	area-System.Runtime, untriaged
Milestone:	-

[AaronRobinsonMSFT]

/cc @davidwrighton

[madelson]

This is not a defense of array covariance (I agree it is problematic). However, one place where removing it might cause issues is with the various reflection APIs for getting Attributes. These often return object[] or Attribute[], but if you pass in a Type filter you can successfully cast the result type to an array of the attribute type, for example:

var flagsAttributes = (FlagsAttribute[])Attribute.GetCustomAttributes(typeof(RegexOptions), typeof(FlagsAttribute));

Older code (especially things written pre-LINQ) might rely on this behavior; having it baked into the shape of these core APIs feels like a challenge. Hard to say how much of an issue this would be broadly.

[Clockwork-Muse]

That, or anything that's switching between collections with a common base, right?

Animal[] animalsToWhatever = cats ? catArray : dogArray;
foreach (var a in animalsToWhatever)
{ 
     a.Speak();
}

(this seems a more likely and used scenario than dealing with reflection)

[tannergooding]

This isn't really actionable on the area owners end and should probably be a discussion thread instead.

It would require sign-off from @jkotas and the various leads/PMs, etc.

[jkotas]

And also, an interesting case:
MemoryMarshal.GetArrayDataReference

MemoryMarshal is unsafe API. It is by design that you can do bad things with unsafe code.

The analyzer: https://github.com/hez2010/ArrayUpcastAnalyzer

This is good data, but I do not think it is complete as others pointed out.

We tried to remove array covariance before in early days of .NET Native for UWP. It broke too much existing code and was added back.

I would not mind introducing a unsupported runtime configuration switch to disable array covariance to enable experimentation in this area.

[huoyaoyuan]

We tried to remove array covariance before in early days of .NET Native for UWP. It broke too much existing code and was added back.

I realized this after looking at the result of the analyzer. There are a lot of unconscious new[].

[jkotas]

I would not mind introducing a unsupported runtime configuration switch to disable array covariance to enable experimentation in this area.

Actually, it would need to be a compiler switch too so that Animal[] animalsToWhatever = cats ? catArray : dogArray fails to compile. That makes it really hard.

[tannergooding]

CC. @jaredpar for thoughts on this bit.

[jaredpar]

Actually, it would need to be a compiler switch too so that Animal[] animalsToWhatever = cats ? catArray : dogArray fails to compile.

Agree. Can't depend on developers to know this happen cause it can be subtle. Need compiler to help enforce it.

That makes it really hard.

Agree. Midori did exactly this (remove covariance and make it a compilation error) and it was extremely hard. Midori had the benefit that it could break compatibility but even so we struggled to remove all the sources of array covariance in the BCL. At the end of the day we concluded it was not possible to completely remove covariance.

Instead we settled on removing covariance for write scenarios and left it for read only scenarios. To that end we introduced a new type called ReadOnlyArray<T>. Arrays themselves were no longer covariant but ReadOnlyArray<T> was allowed to be covariant. Together those allowed us to move forward.

I suspect we'd come to the same conclusion if we tried the experiment in .NET Core

[GSPP]

I believe, array variance was added as a compatibility/migration feature for Java. It's probably a mistake...

Another one that is at least as big is multicast delegates. I believe that was done to support events. Delegates should have been single-cast, and events should have been an IEvent-based object. Making delegates multicast just to support events seems like a rather big hack.

[jkotas]

Unlike array covariance, multicast delegates do not slow down single cast delegates. If you do not like multicast delegates, you can ignore them and it won't affect performance of your code.

[hez2010]

multicast delegates do not slow down single cast delegates

I think multicast delegates make it harder for JIT to inline delegate calls.

[jkotas]

multicast delegates make it harder for JIT to inline delegate calls.

That is not correct (for CoreCLR runtime at least).