API Proposal: ValueStack<T> and other stack-allocated collection types

[alrz]

Background and motivation

Fixed-size stack-allocated collection types possibly backed by the given Span<T> for local use.

API Proposal

namespace System.Collections.Generic
{
    public ref struct ValueStack<T>
    {
        public ValueStack(Span<T> storage); // implies a fixed size
        public void Push(T value);
        public T Pop();
        public T Peek();
        // other applicable members from Stack<T>
    }
}

API Usage

var stack = new ValueStack<int>(stackalloc int[10]);
stack.Push(42);

Variants

Other variants such as ValueQueue<T> or ValueDeque<T> are most likely desirable to add.

One that .NET is currently lacking is a "circular-buffer" type which make sense to have a span-backed implementation for, due to the inherent fixed-size.

Risks

No response

[ghost]

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

Issue Details

---

Background and motivation

Fixed-size stack-allocated collection types possibly backed by the given Span<T> for local use.

API Proposal

namespace System.Collections.Generic
{
    public ref struct ValueStack<T>
    {
        public void ValueStack(Span<T> storage); // implies a fixed size
        public void Push(T value);
        public T Pop();
        public T Peek();
        // other applicable members from Stack<T>
    }
}

API Usage

var stack = new ValueStack<int>(stackalloc int[10]);
stack.Push(42);

Alternative Designs

Not exactly "alternatives", but other variables such as ValueQueue or ValueDeque are most likely desirable to add.
One that .NET is currently lacking is a "circular-buffer" type which make sense to have a span-backed implementation for, due to the inherent fixed-size.

Risks

No response

Author:	alrz
Assignees:	-
Labels:	api-suggestion, area-System.Collections, untriaged
Milestone:	-

[Sergio0694]

This sounds like it would suffer from the same issue as ValueStringBuilder, that is, the fact that we don't have moveonly struct-s yet would make this type very error prone for users, especially in such a common namespace as System.Collections.Generic 🤔

[eiriktsarpalis]

Related to #25587 and #30650. Like ValueStringBuilder we likely wouldn't be able to add this before we can get some form of sanity check from the compiler.

[alrz]

Is there a discussion/issue about the compiler's side of things you can link to?

[Sergio0694]

It seems to mostly just be a discussion so far: dotnet/csharplang#859.

I'd imagine we should write a proper proposal and try to get some traction if we wanted to unblock this.
Of course, this specific feature is unfortunately pretty complex to implement, it's not a trivial addition.

[alrz]

This sounds like it would suffer from the same issue as ValueStringBuilder, that is, the fact that we don't have moveonly struct-s yet

So much happening with span safety https://github.com/dotnet/csharplang/blob/main/proposals/low-level-struct-improvements.md I wonder if any of that could address this issue? Really looking forward for a proposal on "move-only structs"

[Joe4evr]

Would the work on ref fields be a mitigation for the (current) lack of move-only enforcement?

[tannergooding]

Likely not and on top of that ValueX is typically a struct equivalent of X and is not significantly different in implementation (ValueStringBuilder is an internal exception).

My TerraFX project provides a ValueStack<T> (https://source.terrafx.dev/#TerraFX/Collections/ValueStack%25601.cs,b03392691a1e5a61) and UnmanagedValueStack<T> (https://source.terrafx.dev/#TerraFX/Collections/UnmanagedValueStack%25601.cs,27e7b6562f2908dd)

• as well as corresponding ValueX and UnmanagedValueX equivalents for many of the various collection types

These types are largely meant for scenarios where you need something like a Stack or Queue or List but its only ever an internal implementation detail and so you'd like to remove an indirection/allocation for perf-oriented scenarios.

UnmanagedValueStack tracks an actual pointer (well UnmanagedArray<T>) and so with a slight tweak initial backing data could come from the stack.