Add more extensibility points for collection expression optimizations

[asik]

Motivation: immutable collection types suffer from redundant temporary copies when collection expressions are used. Visual Studio has inline hints recommending this syntax everywhere, leading users into sub-optimal code whenever such collections are used.

Consider:

var arr = new[] {1, 2, 3};
MyCollection myCollection = [.. arr];

// Where MyCollection is defined as:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.CompilerServices;

[CollectionBuilder(typeof(MyCollection), nameof(Create))]
public class MyCollection : ICollection<int>
{
    int[] _values;

    public static MyCollection Create(ReadOnlySpan<int> values) =>
        new(values);

    public MyCollection(ReadOnlySpan<int> values) =>
        _values = values.ToArray();

    // ... ICollection<int> implementation
}

Here C# will lower [.. arr] to MyCollection.Create(arr.ToArray()). So we have two allocations:

1. arr.ToArray()
2. MyCollection.Create - since it takes a ReadOnlySpan, it has to copy the collection to its internal array.

The C# compiler works around this for a set of hardcoded "well-known" types and members with optimizations like:

ImmutableArray<int> arr2 = [ ..arr]; // compiles to ImmutableCollectionsMarshal.AsImmutableArray
List<int> list = [ ..anotherEnumerable]; // compiles to Enumerable.ToList

In this scenario, what if we could define a T[] overload of Create that the C# compiler would use? Then we could decide if we'll re-use that array internally and avoid a copy. For instance:

[CollectionBuilder(typeof(MyCollection), nameof(Create))]
public class MyCollection : ICollection<int>
{
    // This should have some scary name like `ImmutableCollectionsMarshal` does to make it clear it's risky and not meant for typical scenarios
    public static MyCollection Create(int[] values) =>
        new(values); // Calls MyCollection(int[] values)
        
    internal MyCollection(int[] values) =>
        _values = values; // no copy, reuses the temporary provided by the C# compiler
        
     public static MyCollection Create(ReadOnlySpan<int> values) =>
        new(values); // Calls MyCollection(ReadOnlySpan<int> values)

    public MyCollection(ReadOnlySpan<int> values) =>
        _values = values.ToArray();

    // ICollection implementation
}

This could not only provide library authors with the same optimizations as "well-known" library types, but allow de-hardcoding these things in the C# compiler.

This is but a suggestion of how to fix this; any other extensibility beyond a method taking ReadOnlySpan would help.

[jnm2]

I support expanding the types allowed by the CreateBuilder Create method, e.g. to T[] and IEnumerable<T>.

This would not allow the compiler to de-hardcode the optimization for ImmutableArray because it is not safe for ImmutableArray to have an API that constructs an immutable array around a T[]; someone could retain a reference to the T[] after the ImmutableArray is constructed, and mutate it. I believe something similar is the case with a List<T> which uses an existing T[] as the backing array; the unsafety for List<T> comes from the resize mechanism. That's why access to the backing memory of these two types is in CollectionsMarshal and ImmutableCollectionsMarshal classes, advertising the unsafety.

[333fred]

It seems to me like most collection types could not support this type of constructor, including the example above. It has the same problem as List<T> and ImmutableArray<T>, where it's not safe to allow anyone to just construct it from an array without assertions around the lifetime of that array. I don't think a simple "just expand Create" approach would actually solve this, you'd actually need to make ImmutableArray<T> and List<T> work here.

Notably, @asik, ImmutableArray<int> arr2 = [ ..arr]; does not avoid an allocation or copy here. Yes, it uses ImmutableCollectionsMarshal.AsImmutableArray, but only after calling ToArray() on arr, because it would be very unsafe to just pass arr to AsImmutableArray.

To solve this, I think you'd need to add a general CreateUnsafe pattern where the compiler has to guarantee that only a temporary value that has not otherwise escaped is passed to the creation method.

[asik]

This would not allow the compiler to de-hardcode the optimization for ImmutableArray because it is not safe for ImmutableArray to have an API that constructs an immutable array around a T[]

I believe that's what ImmutableArray actually does. The compiler calls ImmutableCollectionsMarshal.AsImmutableArray, which constructs an immutable array around a T[]. It's not safe, like you say, but ImmutableArray mitigates this by putting it in this separate class you wouldn't run into unless you were specifically looking for low-level optimizations.

So if you expanded the CollectionBuilder pattern to allow for an arbitrary T[] -> Collection method, then maybe ImmutableArray could apply it to its ImmutableCollectionsMarshal.AsImmutableArray method and that would allow de-hardcoding this in the C# compiler.

[jnm2]

That is true, it may be fine for the CollectionBuilder attribute to point to an unsafe API for compiler use. "De-hardcoding" is still probably not ideal, because we probably wouldn't want the compiler to respect the CollectionBuilder attribute on .NET v8, v9, and v10, because that is pointing at a safe and less efficient ImmutableArray.Create method.

[CyrusNajmabadi]

I'm amenable to this. It would be nice to not have to special case certain apis with the CollectionMarshal bypass. The lang/compiler could certainly look for certain api patterns (or attributes) telling it which apis are safe to pass an array of values into.

That said, the reason we didn't do this originally was simply that when we explored the ecosystem, we did not find enough cases where this would be useful. In other words, the number of collections that backed by their own owned copy of an array was marginal.

I get that the request here is purposefully vague. But are there existing APIs you own that would actually benefit here? If so, can you link to them? We'd need real motivation from API authors stating that this is an actual impediment to them (with examples) to help motivate this. We would be unlikely to do it based on speculative need for apis that don't actually come to fruition.

[asik]

An "array that compares by value" is a request I see every now and then. People expect Records to compare by value and are surprised when they put collections in there and those don't compare structurally 1 2 3 4 5 6.

I had started working on my own implementation a while back, I didn't try to push it past "proof of concept" status but it's useful to me. I revisited it recently which is when I discovered the unfortunate interaction with the new spread element. I find it strange that ImmutableArray doesn't do this, and we don't have a popular, de facto value-like array in .NET.

AFAIK the state of the ecosystem tends to rely more on overring Equals on a case-by-case (error-prone) basis, serializing to JSON to test for equality (a common workaround in JS), adding some custom attributes to generate custom equality (e.g. I've seen this one recently).

As far as "motivation from API authors", you got my personal vote, but I can't show that there's more demand beyond saying "a value array would solve a lot of common problems and confusion for a lot of people".

[RikkiGibson]

I find this problem interesting, and, re: the record custom equality problem, I wonder if the scales have fully tipped at this point, toward using a wrapper type to customize equality per-property, rather than source generator stuff.