Proposal: Value type arrays

[ryantrem]

I'm not sure if this depends on runtime changes or not, so I'll just start here. It would be great if C# supported the concept of stack allocated (value type) arrays in a safe manner. This would be particularly useful in cases where a method takes a variable number of parameters via a params array. If this method is heavily called, it can result in many allocations an GC pressure. Perhaps there would be special syntax for a stack allocated array, such as stack int[], and perhaps there would be implicit conversions between stack allocated arrays and heap allocated arrays.

[HaloFour]

IIRC the safety that the CLR provides with normal arrays vs. stack-allocated arrays is bounds checking and type-safety. Since stackalloc hands back a pointer you are free to both index wherever you want relative to that location or to interpret it as a different type.

However it sounds like what you want is very similar to stack-allocated classes and the problems are largely the same. It's effectively impossible to treat such a reference the same as a heap-allocated reference because you are free to safely do whatever you want with such a reference without worry as to whether or not that reference is still valid. That's not the case with stack-allocated references which are invalid as soon as the allocating method returns. It's impossible to know what a consuming method might do with any given reference, including saving it off to a field for future use.

[Joe4evr]

Is this proposal different from Span<T> somehow? If not, then the language team is already way ahead of you.

[HaloFour]

@Joe4evr

Good call, complete with special syntax to declare/init without requiring unsafe:

Span<int> sp = stackalloc int[100];

[ryantrem]

However it sounds like what you want is very similar to stack-allocated classes and the problems are largely the same. It's effectively impossible to treat such a reference the same as a heap-allocated reference because you are free to safely do whatever you want with such a reference without worry as to whether or not that reference is still valid. That's not the case with stack-allocated references which are invalid as soon as the allocating method returns. It's impossible to know what a consuming method might do with any given reference, including saving it off to a field for future use.

@HaloFour - To be clear, what I was trying to describe is a stack allocated array that behaves like any value type (struct) with pass-by-value semantics.

Is this proposal different from Span somehow? If not, then the language team is already way ahead of you.

@Joe4evr - I'm not sure. I read through the page you linked regarding Span, and it does sound similar. However, it is not clear to me that Span<int> sp = stackalloc int[100]; results in no heap allocations, and it also does not look to me like I could use this in a params array scenario. I would be very happy if the language team was already thinking about this scenario though.

[Joe4evr]

However, it is not clear to me that Span<int> sp = stackalloc int[100]; results in no heap allocations, and it also does not look to me like I could use this in a params array scenario. I would be very happy if the language team was already thinking about this scenario though.

So you're looking for #535?

[HaloFour]

@ryantrem

However, it is not clear to me that Span<int> sp = stackalloc int[100]; results in no heap allocations, and it also does not look to me like I could use this in a params array scenario.

Eliminating the heap allocations is the point of that feature. Span<T> is a struct which wraps the pointer returned by stackalloc to provide a type-safe and bounds-checked window to the underlying stack space. I didn't realize that the LDM were considering an implicit conversion to Span<T> which would eliminate the need to use unsafe as is currently required with stackalloc.

As for the use with params, that will require additional compiler support but it does sound like that it's being considered here.

[ryantrem]

Thanks for the clarification @HaloFour.

So you're looking for #535?

Reading through it, I would say sort of but not entirely. #535 describes various limitations due to the Span being tied directly to the execution stack, like not being able to use it in an async context, etc. What I really want is a value type array that behaves just like any other value type. I updated the title of this thread to reflect that, which hopefully clarifies the ask/proposal. Thanks everyone for sharing your thoughts on this!

[HaloFour]

@ryantrem

The problem with that idea is that one of the inherent limitations of a value type is that it has a fixed size. The only way to dynamically allocate non-heap space is via stackalloc. But there's no built-in way to accomplish copy semantics with such a construct; you're dealing directly with a pointer (or a wrapper to a pointer in the case of Span<T>.) IIRC in any language that allows you to pass arrays of arbitrary sizes between methods you're dealing with references/pointers and the actual data has to exist somewhere.

[ryantrem]

The problem with that idea is that one of the inherent limitations of a value type is that it has a fixed size.

Is that a problem if the size of the array is fixed and can be determined at compile time? This would always be the case with a value type params array, for example.

[HaloFour]

@ryantrem

The size would need to be fixed at both the caller and the callee. I don't see what the point would be for having a method accept a params array that has to be one set fixed length.

[ryantrem]

Yes, requiring the size to be fixed in the callee definition would be pointless :)

[Joe4evr]

What I really want is a value type array that behaves just like any other value type.

But "any other value type" will happily go to the heap anyway when they're used as/hoisted to a field, such as when captured by a lambda or when it's used between async blocks (which is why Span<T> needs its limitations in the first place). See also: The Stack Is An Implementation Detail, Part Deux, and The Truth About Value Types.

The relevant feature of value types is that they have the semantics of being copied by value, not that sometimes their deallocation can be optimized by the runtime.

[ygc369]

@ryantrem
I wonder what you really want.

1. If you want a fixed size value type array, then C# already have it, although unsafe.

unsafe struct ValueTypeArray
{
    fixed int elem[100]; 
}

Maybe you want a safe version of ValueTypeArray, please have a look at my proposal: #115

2. If you want params array to be allocated on stack, then I agree with you. But there are some cases that params array must be allocated on heap. For example:

class A
{
    public int a;
    public int[] b;
    public A(int a, int[] b)
    {
        this.a=a;
        this.b=b;
    }
}
public static A sample = null;
static void function(int a, params int[] b)
{
    sample = new A(a, b); //In this case, b can't be allocated on stack!
    ........
}

So, to determine whether to allocate params array on stack, the compiler need to do escape analysis. Please have a look at my proposal: https://github.com/dotnet/coreclr/issues/1784
Also have a look at #535

[ryantrem]

Thanks @Joe4evr for sharing those posts, very enlightening. I'll have to ponder this some!

@ygc369 - in the example you provided, I think it would be totally fine for the array to end up on the heap (as mentioned in my original post, perhaps by an implicit conversion from a value type array to a reference type array). I'm not trying to avoid ever having a reference type array, just looking for optimizations for the case where an array is passed to a function and has a short lifetime within the execution stack. Maybe that isn't actually necessary if gen 0 GC is just as fast as releasing the stack frame, but no one has suggested yet that this is the case. :)

[ChrML]

A potential use-case for would be a better implementation of this struct. It's a pretty rare use case, but in this case I needed a super-fast and allocation-free way to track if a large string (>1MB) has changed without needing to store the entire string in memory.

public readonly struct LargeStringHash
{
        /// hashing constructors here.

        void GetLastHash(Span<byte> output)
        {
            if (output.Length != 16)
            {
                throw new InvalidOperationException();
            }

            output[00] = this.byte00;
            output[01] = this.byte01;
            output[02] = this.byte02;
            output[03] = this.byte03;
            output[04] = this.byte04;
            output[05] = this.byte05;
            output[06] = this.byte06;
            output[07] = this.byte07;
            output[08] = this.byte08;
            output[09] = this.byte09;
            output[10] = this.byte10;
            output[11] = this.byte11;
            output[12] = this.byte12;
            output[13] = this.byte13;
            output[14] = this.byte14;
            output[15] = this.byte15;
        }

        void SetLastHash(ReadOnlySpan<byte> input)
        {
            if (input.Length != 16)
            {
                throw new InvalidOperationException();
            }

            this.byte00 = input[00];
            this.byte01 = input[01];
            this.byte02 = input[02];
            this.byte03 = input[03];
            this.byte04 = input[04];
            this.byte05 = input[05];
            this.byte06 = input[06];
            this.byte07 = input[07];
            this.byte08 = input[08];
            this.byte09 = input[09];
            this.byte10 = input[10];
            this.byte11 = input[11];
            this.byte12 = input[12];
            this.byte13 = input[13];
            this.byte14 = input[14];
            this.byte15 = input[15];
        }

        byte byte00 = 0;
        byte byte01 = 0;
        byte byte02 = 0;
        byte byte03 = 0;
        byte byte04 = 0;
        byte byte05 = 0;
        byte byte06 = 0;
        byte byte07 = 0;
        byte byte08 = 0;
        byte byte09 = 0;
        byte byte10 = 0;
        byte byte11 = 0;
        byte byte12 = 0;
        byte byte13 = 0;
        byte byte14 = 0;
        byte byte15 = 0;
}