Revisit ImmutableExtensions.TryCopyTo behavior for ICollection<T>

[adamsitnik]

From #88093 (comment):

We should revisit this.

runtime/src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableExtensions.Minimal.cs

Lines 93 to 96 in e5ddc6c

	/// The reason we don't copy anything other than for well-known types is that a malicious interface
	/// implementation of <see cref="ICollection{T}"/> could hold on to the array when its <see cref="ICollection{T}.CopyTo"/>
	/// method is called. If the array it holds onto underlies an <see cref="ImmutableArray{T}"/>, it could violate
	/// immutability by modifying the array.

That logic, while well-meaning, isn't worth making the implementations slower. If code wants to get at the underlying array of an ImmutableArray, there are easier ways, including a now fully supported public API.

The comment that triggered the conversation #88093 (comment):

The custom ToArray implementation is slower, because it uses CopyTo only for collections that implement IList<T>, while both KeyCollection and ValueCollection don't. They do implement ICollection<T> which is used by LINQ.

runtime/src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableExtensions.Minimal.cs

Lines 158 to 164 in c06d77a

	if (!sequence.TryCopyTo(array, 0))
	{
	int i = 0;
	foreach (T item in sequence)
	{
	Requires.Argument(i < count);
	array[i++] = item;

runtime/src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableExtensions.Minimal.cs

Line 106 in c06d77a

if (sequence is IList<T>)

runtime/src/libraries/System.Collections/ref/System.Collections.cs

Line 504 in c06d77a

public sealed partial class KeyCollection : System.Collections.Generic.ICollection<TKey>, System.Collections.Generic.IEnumerable<TKey>, System.Collections.Generic.IReadOnlyCollection<TKey>, System.Collections.ICollection, System.Collections.IEnumerable

runtime/src/libraries/System.Collections/ref/System.Collections.cs

Line 532 in c06d77a

public sealed partial class ValueCollection : System.Collections.Generic.ICollection<TValue>, System.Collections.Generic.IEnumerable<TValue>, System.Collections.Generic.IReadOnlyCollection<TValue>, System.Collections.ICollection, System.Collections.IEnumerable

cc @stephentoub

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

Issue Details

---

From #88093 (comment):

We should revisit this.

runtime/src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableExtensions.Minimal.cs

Lines 93 to 96 in e5ddc6c

	/// The reason we don't copy anything other than for well-known types is that a malicious interface
	/// implementation of <see cref="ICollection{T}"/> could hold on to the array when its <see cref="ICollection{T}.CopyTo"/>
	/// method is called. If the array it holds onto underlies an <see cref="ImmutableArray{T}"/>, it could violate
	/// immutability by modifying the array.

That logic, while well-meaning, isn't worth making the implementations slower. If code wants to get at the underlying array of an ImmutableArray, there are easier ways, including a now fully supported public API.

The comment that triggered the conversation #88093 (comment):

The custom ToArray implementation is slower, because it uses CopyTo only for collections that implement IList<T>, while both KeyCollection and ValueCollection don't. They do implement ICollection<T> which is used by LINQ.

runtime/src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableExtensions.Minimal.cs

Lines 158 to 164 in c06d77a

	if (!sequence.TryCopyTo(array, 0))
	{
	int i = 0;
	foreach (T item in sequence)
	{
	Requires.Argument(i < count);
	array[i++] = item;

runtime/src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableExtensions.Minimal.cs

Line 106 in c06d77a

if (sequence is IList<T>)

runtime/src/libraries/System.Collections/ref/System.Collections.cs

Line 504 in c06d77a

public sealed partial class KeyCollection : System.Collections.Generic.ICollection<TKey>, System.Collections.Generic.IEnumerable<TKey>, System.Collections.Generic.IReadOnlyCollection<TKey>, System.Collections.ICollection, System.Collections.IEnumerable

runtime/src/libraries/System.Collections/ref/System.Collections.cs

Line 532 in c06d77a

public sealed partial class ValueCollection : System.Collections.Generic.ICollection<TValue>, System.Collections.Generic.IEnumerable<TValue>, System.Collections.Generic.IReadOnlyCollection<TValue>, System.Collections.ICollection, System.Collections.IEnumerable

cc @stephentoub

Author:	adamsitnik
Assignees:	-
Labels:	area-System.Collections, tenet-performance
Milestone:	-

[prozolic]

Is this issue still open for contributions? I'd like to work on a fix if no one is actively assigned to it.
I'm planning to make the following changes to ImmutableExtensions.TryCopyTo.

• Change the type check from IList<T> to ICollection<T>
• If the type does not match List<T>, T[], or ImmutableArray<T>, fall back to ICollection<T>.CopyTo
• Add conditional compilation( #if NET) to ensure the sequence is not an array before falling back to ICollection<T>.CopyTo to avoid issues with array covariance in .NET Framework

        internal static bool TryCopyTo<T>(this IEnumerable<T> sequence, T[] array, int arrayIndex)
        {
            Debug.Assert(sequence != null);
            Debug.Assert(array != null);
            Debug.Assert(arrayIndex >= 0 && arrayIndex <= array.Length);

            if (sequence is ICollection<T>)
            {
                if (sequence is List<T> list)
                {
                    list.CopyTo(array, arrayIndex);
                    return true;
                }

                // Array.Copy can throw an ArrayTypeMismatchException if the underlying type of
                // the destination array is not typeof(T[]), but is assignment-compatible with T[].
                // See https://github.com/dotnet/runtime/issues/14794 for more info.
                if (sequence.GetType() == typeof(T[]))
                {
                    var sourceArray = (T[])sequence;
                    Array.Copy(sourceArray, 0, array, arrayIndex, sourceArray.Length);
                    return true;
                }

                if (sequence is ImmutableArray<T> immutable)
                {
                    Array.Copy(immutable.array!, 0, array, arrayIndex, immutable.Length);
                    return true;
                }

#if !NET
                if (sequence is Array)
                {
                    return false;
                }
#endif

                ((ICollection<T>)sequence).CopyTo(array, arrayIndex);
                return true;
            }

            return false;
        }

[adamsitnik]

Hi @prozolic

Yes, it's still opened for contributions. Please make sure you benchmark you changes locally when working on it: https://github.com/dotnet/performance/blob/main/docs/benchmarking-workflow-dotnet-runtime.md

[prozolic]

Thank you @adamsitnik!
The benchmark result measured locally are as follows.

Benchmark

Method	Job	Toolchain	input	Mean	Error	StdDev	Median	Min	Max	Ratio	RatioSD	Code Size	Gen0	Allocated	Alloc Ratio
ToImmutableArray	Job-TZICZT	\main\corerun.exe	Array	31.97 ns	3.134 ns	3.609 ns	31.97 ns	23.10 ns	40.01 ns	1.01	0.16	3,632 B	0.0507	424 B	1.00
ToImmutableArray	Job-TQYIYA	\pr\corerun.exe	Array	32.23 ns	3.329 ns	3.833 ns	32.01 ns	24.80 ns	43.01 ns	1.02	0.17	3,659 B	0.0506	424 B	1.00
ToImmutableArray	Job-TZICZT	\main\corerun.exe	ICollection	116.04 ns	6.940 ns	7.992 ns	114.19 ns	106.76 ns	130.55 ns	1.00	0.09	2,203 B	0.0506	424 B	1.00
ToImmutableArray	Job-TQYIYA	\pr\corerun.exe	ICollection	34.18 ns	5.743 ns	6.614 ns	32.89 ns	26.62 ns	52.36 ns	0.30	0.06	3,662 B	0.0507	424 B	1.00
ToImmutableArray	Job-TZICZT	\main\corerun.exe	IEnumerable	246.68 ns	19.784 ns	22.783 ns	244.53 ns	215.81 ns	309.02 ns	1.01	0.12	4,422 B	0.0500	424 B	1.00
ToImmutableArray	Job-TQYIYA	\pr\corerun.exe	IEnumerable	253.29 ns	15.429 ns	17.769 ns	255.31 ns	220.14 ns	290.17 ns	1.03	0.11	4,409 B	0.0506	424 B	1.00
ToImmutableArray	Job-TZICZT	\main\corerun.exe	IList	99.79 ns	9.014 ns	10.380 ns	99.06 ns	86.38 ns	120.11 ns	1.01	0.14	2,212 B	0.0506	424 B	1.00
ToImmutableArray	Job-TQYIYA	\pr\corerun.exe	IList	33.64 ns	7.574 ns	8.722 ns	33.20 ns	21.77 ns	48.51 ns	0.34	0.09	3,662 B	0.0506	424 B	1.00
ToImmutableArray	Job-TZICZT	\main\corerun.exe	List	26.67 ns	2.622 ns	3.019 ns	25.43 ns	22.49 ns	31.48 ns	1.01	0.16	3,643 B	0.0507	424 B	1.00
ToImmutableArray	Job-TQYIYA	\pr\corerun.exe	List	27.57 ns	5.202 ns	5.991 ns	25.88 ns	22.76 ns	45.23 ns	1.05	0.25	3,669 B	0.0506	424 B	1.00

source

    [MemoryDiagnoser]
    [BenchmarkCategory(Categories.Libraries, Categories.Collections)]
    public class Perf_ToImmutableArray
    {
        public IEnumerable<object> Arguments()
        {
            yield return TestData.IEnumerable;
            yield return TestData.ICollection;
            yield return TestData.IList;
            yield return TestData.Array;
            yield return TestData.List;
        }

        [Benchmark]
        [ArgumentsSource(nameof(Arguments))]
        [MemoryRandomization]
        public ImmutableArray<int> ToImmutableArray(TestData input)
        {
            var array = input.Collection.ToImmutableArray();
            return array;
        }

    }

    public class TestData
    {
        internal const int Size = 100;

        private static readonly int[] array = Enumerable.Range(0, Size).ToArray();
        internal static readonly TestData Array = new(array);
        internal static readonly TestData List = new(new List<int>(array));
        internal static readonly TestData IEnumerable = new(ToEnumerable(Size));
        internal static readonly TestData IList = new(new IListWrapper<int>(array));
        internal static readonly TestData ICollection = new(new ICollectionWrapper<int>(array));

        private TestData(IEnumerable<int> collection) => Collection = collection;

        internal IEnumerable<int> Collection { get; }

        private static IEnumerable<int> ToEnumerable(int size)
        {
            for (int i = 0; i < size; i++)
            {
                yield return i;
            }
        }

        public override string ToString()
        {
            switch (Collection)
            {
                case int[] _:
                    return "Array";
                case List<int> _:
                    return "List";
                case IList<int> _:
                    return "IList";
                case ICollection<int> _:
                    return "ICollection";
                default:
                    return "IEnumerable";
            }
        }

        private class ICollectionWrapper<T> : ICollection<T>
        {
            private readonly T[] _array;
            public ICollectionWrapper(T[] array) => _array = array;

            public IEnumerator<T> GetEnumerator() => ((IEnumerable<T>)_array).GetEnumerator();
            Collections.IEnumerator Collections.IEnumerable.GetEnumerator() => ((IEnumerable<T>)_array).GetEnumerator();

            public int Count => _array.Length;
            public bool IsReadOnly => true;
            public bool Contains(T item) => System.Array.IndexOf(_array, item) >= 0;
            public void CopyTo(T[] array, int arrayIndex) => _array.CopyTo(array, arrayIndex);

            public void Add(T item) => throw new NotImplementedException();
            public void Clear() => throw new NotImplementedException();
            public bool Remove(T item) => throw new NotImplementedException();
        }

        private class IListWrapper<T> : IList<T>
        {
            private readonly T[] _array;
            public IListWrapper(T[] array) => _array = array;

            public IEnumerator<T> GetEnumerator() => ((IEnumerable<T>)_array).GetEnumerator();
            Collections.IEnumerator Collections.IEnumerable.GetEnumerator() => ((IEnumerable<T>)_array).GetEnumerator();

            public int Count => _array.Length;
            public bool IsReadOnly => true;
            public T this[int index]
            {
                get { return _array[index]; }
                set { throw new NotImplementedException(); }
            }
            public bool Contains(T item) => System.Array.IndexOf(_array, item) >= 0;
            public void CopyTo(T[] array, int arrayIndex) => _array.CopyTo(array, arrayIndex);
            public int IndexOf(T item) => System.Array.IndexOf(_array, item);

            public void Add(T item) => throw new NotImplementedException();
            public void Clear() => throw new NotImplementedException();
            public bool Remove(T item) => throw new NotImplementedException();
            public void Insert(int index, T item) => throw new NotImplementedException();
            public void RemoveAt(int index) => throw new NotImplementedException();
        }
    }

[adamsitnik]

Provided benchmark results look good to me. There is a regression, but it's small compared to gains for the other codepaths.

[prozolic]

Thank you for your confirmation.
I've submitted a #125304 with this fix.