Support for "frozen" array instance

[alrz]

Currently C# collection expressions generate a wrapper class around T[] to avoid cast/mutation on IEnumerable<T>, IReadOnlyList<T>, IReadOnlyCollection<T>. Could runtime support "frozen" array instances to avoid this extra allocation for each instance?

[colejohnson66]

ImmutableArray<T>

[alrz]

That would involve a boxing conversion.

[colejohnson66]

How so? The array is allocated, then wrapped into the InlineArray. Are you suggesting a way to have a T[] that is immutable? That will never happen.

[huoyaoyuan]

Changing array would definitely be non-starer. Inserting a frozen-check on write accesses is a nightmare beyond covariance check. Introducing new type for frozen array is also very heavy for the whole ecosystem.

It may be covered by supporting user-defined variable-length object, but it would need more complex work and limitations.

[alrz]

frozen-check on write access
is a nightmare beyond covariance check.

Yes I think this would be exactly that but I didn't get why it's not desirable?

It may be covered by supporting user-defined variable-length object,

I couldn't find anything on that, is there a tracking issue?

[alrz]

I think another approach is "casting" the array instance to an array that lies about it's actual implemented interfaces (that is, it's a subset of the original).

[huoyaoyuan]

Yes I think this would be exactly that but I didn't get why it's not desirable?

Because array is fundamental and used very intensively. Currently covariance check is only applicable to reference types, which also have write barrier to pay, so the performance difference isn't unacceptable.

I couldn't find anything on that, is there a tracking issue?

No. It's unlikely to happen because of complexity.

[AustinWise]

While a frozen array feature could be hypothetically added, trying to avoid allocating a wrapper object when using collection expressions is probably not a good enough reason to add them. If you want to avoid the extra allocation, surely you also want to avoid the interface dispatch to access each element of the array? The code can be changed to use a Span to avoid both of these sources of inefficiency.

Ignoring the cost/benefit of such a feature stated above, I can think of a couple ways of implementing it. One would be to add run time checks when writing to arrays to make throw an exception if the array is frozen. These checks might not be too costly (they could be lifted out of loops like range checks are), but they probably would add overhead.

Another way to implement a frozen array would be to have the GC store the array in read only memory (memory marked read only by VirtualAlloc on Windows or mprotect on Unix). If code tries to write to such protected memory, an access violation exception is raised on Windows and a SIGSEGV signal is raised on Unix. This signal could be translated into a managed exception to let the program know the memory was write only. There is already similar support for translating the SIGSEGV caused by dereferencing a null reference into a NullReferenceException. So this check would impose no extra runtime checks when writing to an array. But there is a problem: how do you write the initial contents to the array before it is marked readonly? Somehow the protection on the page would have to be changed from read-write to read only. However this is implemented, it would involving changing page protection. And change page protection is expensive: it is at least a system call and potentially expensive as the OS sending an inter-processor interrupt to every CPU core executing code in the process to flush its TLB.

[voroninp]

The issue is that neither IEnumerable<T> nor IReadOnlyCollection<T> provide a guarantee of repeatable enumeration. The concrete implementation can have it or not, but there's no way to know or require the behavior on the accepting side.

I believe we need something like this in .NET:

// Type which implements this interface MUST guarantee that subsequent enumerations always yield the same sequence.
public interface IRepeatableEnumerable<T> : IEnumerable<T>
{
}

public interface IFrozenCollection<T> :  IReadOnlyCollection<T>, IRepetableEnumerable<T>
{
}

public interface IFrozenSet<T> : IReadOnlySet<T>, IrepeatableEnumerable<T>
{
}

public interface IFrozenDictionary<TKey, TValue> : IDictionary<TKey, TValue>, IFrozenCollection<KeyValuePair<TKey, TValue>>
{
}

Then Immutable collections, FrozenSet, and FrozneDictionary can implement these interfaces (a breaking change).

[huoyaoyuan]

// Type which implements this interface MUST guarantee that subsequent enumerations always yield the same sequence.

This doesn't follow .NET design principle to use marker interface without functionality. There's also no way to enforce implementations to follow the contract.

Then Immutable collections, FrozenSet, and FrozneDictionary can implement these interfaces (a breaking change).

It's not.

Moreover, using interfaces has more overhead than concrete type.

[voroninp]

There's also no way to enforce implementations to follow the contract.

I'd be happy if there were means to enforce the contract.

It's not.

Even better.

Moreover, using interfaces has more overhead than concrete type.

Yes, but interface allows to accept any implementation, plus advancements in JIT give a hope for more cases of devirtualization. Anyway, creating defensive copies of collections is worse.