Expose a `malloca` API that either stackallocs or creates an array.

[tannergooding]

Background and Motivation

It is not uncommon, in performance oriented code, to want to stackalloc for small/short-lived collections. However, the exact size is not always well known in which case you want to fallback to creating an array instead.

Proposed API

namespace System.Runtime.CompilerServices
{
    public static unsafe partial class Unsafe
    {
        public static Span<T> Stackalloc<T>(int length);
        public static Span<T> StackallocOrCreateArray<T>(int length);
        public static Span<T> StackallocOrCreateArray<T>(int length, int maxStackallocLength);
    }
}

These APIs would be intrinsic to the JIT and would effectively be implemented as the following, except specially inlined into the function so the localloc scope is that of the calling method:

public static Span<T> StackallocOrCreateArray<T>(int length, int maxStackallocLength)
{
    return ((sizeof(T) * length) < maxStackallocLength) ? stackalloc T[length] : new T[length];
}

The variant that doesn't take maxStackallocLength would use some implementation defined default. Windows currently uses 1024.

Any T would be allowed and the JIT would simply do new T[length] for any types that cannot be stack allocated (reference types).

[ghost]

Tagging subscribers to this area: @GrabYourPitchForks, @carlossanlop See info in area-owners.md if you want to be subscribed.

Issue Details

---

## Background and Motivation It is not uncommon, in performance oriented code, to want to `stackalloc` for small/short-lived collections. However, the exact size is not always well known in which case you want to fallback to creating an array instead. ## Proposed API ```csharp namespace System.Runtime.CompilerServices { public static unsafe partial class Unsafe { public static Span Stackalloc(int length); public static Span StackallocOrCreateArray(int length); public static Span StackallocOrCreateArray(int length, int maxStackallocLength); } } ``` These APIs would be `intrinsic` to the JIT and would effectively be implemented as the following, except specially inlined into the function so the `localloc` scope is that of the calling method: ```csharp public static Span StackallocOrCreateArray(int length, int maxStackallocLength) { return ((sizeof(T) * length) < maxStackallocLength) ? stackalloc T[length] : new T[length]; } ``` The variant that doesn't take `maxStackallocLength` would use some implementation defined default. Windows currently uses `1024`. Any `T` would be allowed and the JIT would simply do `new T[length]` for any types that cannot be stack allocated (reference types).

Author:	tannergooding
Assignees:	-
Labels:	`api-suggestion`, `area-System.Memory`, `untriaged`
Milestone:	-

[tannergooding]

This issue came up on Twitter again (https://twitter.com/jaredpar/status/1387798562117873678?s=20) and we have valid use cases in the framework and compiler.

This has been somewhat stuck in limbo as runtime/framework saying "we need language support first" and the language saying "we need the runtime/framework to commit to doing this first".

We should review and approve this to unblock the language from committing to their work and can do all the appropriate implementation/prep work on the runtime side, without actually making it public until the language feature is available.

CC. @jkotas, @jaredpar, @GrabYourPitchforks

[tannergooding]

There would not be an API which opts to use the ArrayPool today. We don't use the ArrayPool for any type, but rather only specific sets of types. An API which does use some ArrayPool would likely need to return some other type which indicates whether the type needs to be returned.

Stackalloc was added at the request of Jared who gave the following reasoning:

stackalloc

• returns a pointer hence no var
• works only on where T: unmanaged

Yes we could use a runtime feature flag to let the compiler remove the restriction on where T : unmanaged. But that doesn't fix the var issue. At the point we're adding new APIs for stack alloc then seems better to simplify and use them for all forms of stack alloc. Makes the code more consistent, lets you have the same type of call sites (can flip between forms without having to also say flip var)

[GrabYourPitchforks]

Related to https://github.com/dotnet/runtime/issues/25423. That proposal is a bit light on concrete APIs, but it suggests behaviors / analyzers / other ecosystem goodness we'd likely want to have around this construct.

[jaredpar]

This does require language changes to work correctly but the implementation is very straight forward. The compiler will just treat all of these calls as if they are not safe to escape from the calling method. Effectively it would have the same lifetime limitation as calling stackalloc today.

I think the best approach is to just have the compiler trigger on the FQN of the method. Essentially any API with this signature in any assembly would be treated this way. That would make it easier to write code that multi-targets between .NET Core and .NET Framework as the framework side of this could be implemented as new T[length] in all cases.

The other advantage of this API is that w can once again var all the things.

var local1 = stackalloc int[42]; // int*
var local2 = Unsafe.StackAlloc<int>(42); // Span<int>

[jkotas]

This is one of those features that requires a joint work from all runtimes/JIT/language/libraries. Our .NET 6 budget for features in this space was taken by the generic numerics. We should include this proposal next time we do planning in this area.

Approving this API without the resource commintment won't achieve much.

[tannergooding]

Approving this API without the resource commintment won't achieve much.

It gives us a surface on which this can be implemented given "free time" and can be prioritized appropriately.

The library work is approving the API and exposing the surface area. The language work is recognizing these methods and based on Jared's comment is relatively trivial.

The JIT work should just be implementing it as a recursive named intrinsic and then creating the relevant nodes for:

if ((sizeof(T) * length) < maxStackallocLength)
{
    var x = stackalloc T[length];
    return new Span<T>(x, length);
}
else   
{
    var x = new T[length];
    return new Span<T>(x);
}

This is fairly straightforward, except for the newobj calls which involves getting the relevant method tokens

[jkotas]

The JIT work should just be implementing it as a recursive named intrinsic and then creating the relevant nodes for:

I do not think we would want to do a naive implementation like this. I think we would want to do explicit life-time tracking even when the lenght is over the threashold.

[tannergooding]

I think we would want to do explicit life-time tracking even when the lenght is over the threashold.

What's the scenario where the JIT needs to do additional tracking that isn't already covered by the language rules and by the existing tracking for Span<T>?

Users can and already do write the above today, just manually inlined. We are looking at doing exactly this already in one of the BigInteger PRs. This is an API on Unsafe that exists to help simplify the logic and behave like alloca does in C/C++ and can be immensely simplified/unblock scenarios by doing the trivial implementation. It then becomes a drop in replacement for what users are already doing.

[jkotas]

What's the scenario where the JIT needs to do additional tracking that isn't already covered by the language rules and by the existing tracking for Span?

We would be leaving performance on the table.

Majority of the existing stackalloc uses are using ArrayPool as the fallback. If the new API is not using pooled memory as the fallback, the majority of the existing stackalloc sites won't be able to use it.

[jaredpar]

It is also could be a common pattern to use stackalloc or ArrayPool, e.g.:

That requires a different level of language support. Supporting the non-arraypool case is very straight forward. It's just generalizing the existing lifetime restrictions we associate with stackalloc to instead be a collection of API calls. It's closer to a bug fix level of work than a new feature.

The ArrayPool case is very doable but it's definitely in the "new feature" category because we have to do the work to handle Free and design some cases around it. Example: do we make locals initialized with these APIs as unassignable? If we allow reassignment then we have to consider how that impacts us calling Free with the resulting value. Solvable items but definitely a bit of design work that needs to go into it.

[tannergooding]

That really sounds like an additional ask and one isn't strictly needed at the same time.

Pooling has a lot of different considerations and we ourselves largely only use it with a few primitive types (namely byte), not any T. It likewise requires:

• a way to get the array from a Span<T>
• knowing that Span<T> definitely points to the start of an Array
• may involve custom pooling and not just ArrayPool
• etc

I think its doable, but we could also unblock many scenarios with the above today and with minimal work.

[jkotas]

The ArrayPool case is very doable but it's definitely in the "new feature" category because we have to do the work to handle Free and design some cases around it.

I do not think we would necessarily want to deal with the pooling in Roslyn, nor have it backed by the ArrayPool as it exist today.

[jkotas]

we could also unblock many scenarios with the above today and with minimal work.

I do not see those scenarios. The minimal work just lets you do the same thing as what you can do with stackalloc today, just maybe saves you a few characters.

[tannergooding]

I do not see those scenarios

They exist everywhere that alloca is used in native. They exist in 3rd party libraries like ImageSharp. They exist for types where array pooling isn't desirable because pooling has its own overhead and costs (and generally cost per type).

None of the existing proposals or discussions around this, including https://github.com/dotnet/runtime/issues/25423 which has been around for 3 years, have really covered pooling as that is considered a more advanced scenario.

This covers the case of "I want to allocate on the stack for small data and on the heap for larger data" and where the limit for that might vary between platforms and architectures. Windows for example has a 1MB stack by default and uses 1024 bytes. Linux uses a 4MB stack and might want a different limit.

Encountering large lengths is typically expected to be rare, but not impossible. Its not unreasonable to simply new up an unpooled array in that scenario.

[tannergooding]

Pooling, for example, is likely only beneficial for types like byte, char, or int which are (for the vast majority case) the only usages in the BCL: https://source.dot.net/#System.Private.CoreLib/ArrayPool.cs,704a680ba600a2a4,references

[EgorBo]

stackalloc + new:

    Span<byte> span = Unsafe.StackallocOrCreateArray(len, 1024);
    // vs 
    Span<byte> span = len > 1024 ? new byte[len] : stackalloc byte[1024];

Indeed just saves a few characters (but nice to have).

But stackalloc + arraypool should save a lot 🙂 :

    byte[] arrayFromPool = null;
    Span<byte> span = len > 1024 ? (arrayFromPool = ArrayPool<byte>.Shared.Rent(len)) : stackalloc byte[1024];
    try
    {
    }
    finally
    {
        if (arrayFromPool != null)
            ArrayPool<byte>.Shared.Return(arrayFromPool );
    }

    // vs 
    Span<byte> span = Unsafe.StackallocOrPool(len, 1024);

[jaredpar]

Indeed just saves a few characters (but nice to have).

Has a couple of other benefits:

1. Path forward for supporting unmanaged types in stackalloc, particularly for code that needs to cross compile between .NET Core and Framework
2. Supports var

[jaredpar]

But stackalloc + arraypool should save a lot

I'm now seeing conflicting advice on whether or not arrays should be returned to the pool in a finally. Had others suggest that the finally is too much overhead and best to just let the array leak in the case of an exception.

[gfoidl]

@EgorBo your example with the pool would save even more when the Span is sliced to the desired length (as it's often needed that way when the length is given as argument).

[jkotas]

They exist for types where array pooling isn't desirable because pooling has its own overhead and costs (and generally cost per type).

This is due to current array pool design limitations. This is fixable by treating management of explicit lifetime memory as core runtime feature.

I'm now seeing conflicting advice on whether or not arrays should be returned to the pool in a finally

This depends on how performance sensitive your code is and how frequenly you expect exceptions to occur inside the scope. If your code is perf critical (e.g. number formatting) and you do not expect exceptions to ever occur inside the scope (e.g. the only exception you ever expect is out of memory), it is better to avoid finally as it is the common case in dotnet/runtime libraries.

[tannergooding]

This is due to current array pool design limitations. This is fixable by treating management of explicit lifetime memory as core runtime feature.

That also sounds like a feature that is potentially several releases out and which is going to require users and the compiler to review where it is good/correct to use.

Something like proposed here is usable in the interim, including for cases like params Span<T>. It represents something that many languages do provide and which is part of the "standard" set of memory allocation APIs commonly exposed by languages. It likewise fills a gap for languages that don't have unsafe support or which don't have an implicit conversion to span, such as F#: https://github.com/fsharp/fslang-suggestions/issues/720

Having to do Span<byte> span = len > 1024 ? new byte[len] : stackalloc byte[1024]; everywhere and then go and find/update every callsite if you end up changing the behavior or size limit isn't great. Having an API is good for the same reason all helper/utility methods are good and helps with refactorings, maintainability, finding usages of the pattern, etc. It also allows it to easily be customized for different stack sizes, at least for Unix vs Windows and possibly vs MacOS or ARM or 32-bit vs 64-bit.

[xoofx]

What about making the allocator not necessarily bound to new byte[len] or ArrayPool<byte>.Shared.Rent(len) (e.g could come from e.g unmanaged memory pool)

namespace System.Runtime.CompilerServices
{
    public static unsafe partial class Unsafe
    {
        public static Span<T> Stackalloc<TAllocator, T>(int length, TAllocator allocator) 
                                                 where TAllocator: ISpanAllocator<T>
        // ...
    }

    public interface ISpanAllocator<T> {
         Span<T> Allocate(int length);   
    }
}

[benaadams]

Any T would be allowed and the JIT would simply do new T[length] for any types that cannot be stack allocated (reference types).

Could also allocate a series of ref fields (all null); and then allow indexing them as via Span

[tannergooding]

What about making the allocator not necessarily bound to new byte[len] or ArrayPool.Shared.Rent(len)

I think any API that isn't tracking either T* or T[] would need to return something like DisposableSpan<T> so the appropriate free could occur (or would need language support for the relevant TAllocator.Free to be called).

Otherwise, I think it falls into the general camp of what it seems @jkotas is proposing with runtime supported lifetime tracking.

[xoofx]

I think any API that isn't tracking either T* or T[] would need to return something like DisposableSpan<T> so the appropriate free could occur (or would need language support for the relevant TAllocator.Free to be called).

Oh, yeah true, Let's do it! 😅

[xoofx]

That starts to be as painful as implementing IEnumerable<T> 🙃

namespace System.Runtime.CompilerServices
{
    public static unsafe partial class Unsafe
    {
        public static TState Stackalloc<TAllocator, TState, T>(int length, TAllocator allocator, out Span<T> span) 
                                                 where TAllocator: ISpanAllocator<T, TState>
        // ...
    }

    public interface ISpanAllocator<T, TState> {
        Span<T> Allocate(int length, out TState state);   
        void Release(TState state);
    }
}

[Edit] Removed where TState: IDisposable as we have already ISpanAllocator.Release [Edit2] Arg, actually, maybe it was better with the IDiposable, I told you, it's more painful than IEnumerable

[Tornhoof]

The concepts which return some kind of pooled array overlap with IMemoryOwner. The duality of Span vs. IMemoryOwner shows up in e.g. MS FASTER. https://github.com/microsoft/FASTER/blob/master/cs/src/core/VarLen/SpanByteAndMemory.cs

[jkotas]

I do not see those scenarios

They exist everywhere that alloca is used in native. They exist in 3rd party libraries like ImageSharp.

I went through all existing stackallocs in ImageSharp. I do not see any of them matching the naive pattern. Where would this API be used in ImageSharp?

[tannergooding]

Where would this API be used in ImageSharp?

Looks like I was either misremembering or its been changed. They are using ArrayPool<T> right now: https://github.com/SixLabors/ImageSharp.Drawing/blob/d8960b8e2e55875d2c4f990f5fc439b846af1230/src/ImageSharp.Drawing/Shapes/InternalPath.cs#L231-L234

[xoofx]

But I'm a bit worried of the limitations of this proposal, e.g if it is hardcoding to a particular underlying allocator (being new or shared ArrayPool) or to a hardcoded heuristic... After frankly, it's not the end of the world, we are not blocked today as we can perfectly write manually such code. Yes, It can be laborious if we go through the full pattern with array pool + try/finally + dispose but it still sounds to me like a nice to have.

Though, one function that would be helpful to develop wiser stackalloc heuristics is something like RuntimeHelpers.GetAvailableStackSizeInBytes() (I think a similar request was formulated on previous issues)

[iSazonov]

These APIs would be intrinsic to the JIT

I wonder why we need the new API at all if it can be intrinsic in some ways because everything we need is known in advance.

If user writes:

var buffer = new T[length];

and compiler has MaxStackallocLength and it can directly put follow implementation:

var buffer = ((sizeof(T) * length) < MaxStackallocLength) ? stackalloc T[length] : new T[length];

and if the length is known at compile time, it can immediately simplify the expression (this could also be optimized at runtime too).

I guess this could work well most of the time. Otherwise we could have turned off this new behavior with a compiler directive.

---

Majority of the existing stackalloc uses are using ArrayPool as the fallback. If the new API is not using pooled memory as the fallback, the majority of the existing stackalloc sites won't be able to use it.

Compiler could replace:

var buffer = new T[length];

with

var buffer = ((sizeof(T) * length) switch
    < MaxStackallocLength) => stackalloc T[length],
    < MaxPooledLength) =>  ArrayPool<T>.Shared.Rent(length),
    _ => new T[length];

Again we could have turned off this new behavior with a compiler directive.

In special cases, we can use compiler directives to tell the compiler the best values for MaxStackallocLength and MaxPooledLength.

[kkokosa]

I see again a new round of stackalloc, ArrayPool, "sufficent stack" discussion :) Just for a reference 👉 https://github.com/dotnet/runtime/issues/24963

[JimBobSquarePants]

@tannergooding you weren’t misremembering, it was there but we’ve managed to incrementally remove all requirements as we optimised the code. The ArrayPool usage is gone now also.

[Thealexbarney]

What about a general language feature that took inspiration from C macros and C# source generators that could expand a "function call" into something else? This way users would be able to write their own StackallocOrCreateArray<T> that's tailored to their specific case.

Like the suggestion that the APIs be a specialized JIT intrinsic that operates in the frame of the caller, except more general. Maybe a function that could still only access arguments passed to it and its own variables which would still be scoped to itself, but could do things like stackalloc or return. It could be inlined into the caller by the C# or JIT compiler.

That idea is somewhat limited due to trying to be safer than straight text replacement, and I admit I don't know what other issues it might bring up.

A more powerful feature might be able to turn something like

Log.Info($"Some expensive expression: {ExpensiveFoo()}");

into

if (Log.InfoLogEnabled) {
    Log.LogImpl(LogLevel.Info, $"Some expensive expression: {ExpensiveFoo()}");
}

Currently you'd have to either move the check if logging's enabled into the caller, always build the string passed into the log function, or pass a lambda, all of which either have larger maintenance or performance costs to some degree.

I don't know if either of these completely solve the ArrayPool case. It would at least need some work on the design. For example, a user could use a struct like the following and then add a using var returner = new ArrayPoolReturner<T>(); before trying to do stackalloc or allocate the array, but that could easily cause problems when doing something like assigning the allocated Span<T> to a variable outside the scope where StackallocOrCreateArray<T> is called.

struct ArrayPoolReturner<T> : IDisposable {
    private T[] _array;

    public void SetRentedArray(T[] array) { /* impl */ }

    public void Dispose()
    {
        if(_array != null)
            ArrayPool<T>.Shared.Return(_array);

        _array = null;
    }
}

[acaly]

@Thealexbarney There is a planned interpolated string improvement that solves your logger scenario: https://github.com/dotnet/csharplang/blob/f4d1c13a6a2ffd09b2e46b0bed57f2629640e440/proposals/improved-interpolated-strings.md.

[Thealexbarney]

@Thealexbarney There is a planned interpolated string improvement that solves your logger scenario

Ah, I wasn't aware of that part of the new interpolated string APIs. Although the logging example was meant as more of a scenario that most people would be familiar with rather than the only reason for bringing up the idea.

[AraHaan]

Background and Motivation

It is not uncommon, in performance oriented code, to want to stackalloc for small/short-lived collections. However, the exact size is not always well known in which case you want to fallback to creating an array instead.

Proposed API

namespace System.Runtime.CompilerServices
{
    public static unsafe partial class Unsafe
    {
        public static Span<T> Stackalloc<T>(int length);
        public static Span<T> StackallocOrCreateArray<T>(int length);
        public static Span<T> StackallocOrCreateArray<T>(int length, int maxStackallocLength);
    }
}

These APIs would be intrinsic to the JIT and would effectively be implemented as the following, except specially inlined into the function so the localloc scope is that of the calling method:

public static Span<T> StackallocOrCreateArray<T>(int length, int maxStackallocLength)
{
    return ((sizeof(T) * length) < maxStackallocLength) ? stackalloc T[length] : new T[length];
}

The variant that doesn't take maxStackallocLength would use some implementation defined default. Windows currently uses 1024.

Any T would be allowed and the JIT would simply do new T[length] for any types that cannot be stack allocated (reference types).

How would the stackalloced buffer remain valid after that function returns? I thought about this and I think the way stackalloc works today is that it lives only until the function returns, then it is freed (GC'd).

Also if it does work, what about ref types, that later needs resized? a prime example is my open Pull request in dotnet/winforms that is a bit tricky because I either have to: A: rent a 32k buffer all at once and stack overflow the thing with a super large stack allocation, or B: Use ArrayPool (also something that can fail the tests in that repository), or C: Some way to allocate a clean buffer using something like this, but later be able to realloca that stuff using stackalloc for the ref type (or create an array).

[MichalStrehovsky]

How would the stackalloced buffer remain valid after that function returns? I thought about this and I think the way stackalloc works today is that it lives only until the function returns, then it is freed (GC'd).

I think this is in the text you're quoting: "These APIs would be intrinsic to the JIT and would effectively be implemented as the following, except specially inlined into the function so the localloc scope is that of the calling method:"

[Xyncgas]

When parsing compressed stream, I find myself decompressing the stream and then parsing the result, the decompression is local to the function and not exposed to the user therefore instead of asking user to pass in a buffer I would much rather creating a buffer in stack to put the compressed bytes before decompressing them and transforming them and the size is small (a couple bytes)

Which is hard to do in F#

and the guys from F# seems to favor this instead of giving me a function that does stackalloac and returns a span

also while we are at it, would be nice to have value type equivalent of, MemoryStream and BinarySerializer for me to use together with stack allocated buffer

Although without these I can still use other hacks to decompress the bytes to stack buffer without MemoryStream or BinaryWriter/BinaryReader

[timcassell]

Any T would be allowed and the JIT would simply do new T[length] for any types that cannot be stack allocated (reference types).

Why can't stackalloc reference types be supported? I get that the GC doesn't track it, but why can't it?

[weltkante]

Why can't stackalloc reference types be supported?

Because the contract of a reference to a reference type is that anyone can take and keep such a reference for later, something allocated on a stack won't be able to hold that contract. You'd need to come up with a new contract to support what you're asking for, or allow breaking the memory safety of .NET

[timcassell]

Why can't stackalloc reference types be supported?

Because the contract of a reference to a reference type is that anyone can take and keep such a reference for later, something allocated on a stack won't be able to hold that contract. You'd need to come up with a new contract to support what you're asking for, or allow breaking the memory safety of .NET

I'm talking about stackalloc object[length], not stackalloc object().

[ayende]

Consider this code:

// Assume [SkipLocalInit]
var items = stackalloc string[2];
items[0] = new string('a', 255);
GC.Collect();
Console.WriteLine(items[0]);

The problem is likely that you now need to scan the stack itself for those roots as well. And there is also an issue with the second value there, which may be garbage because of the SkipLocalInit, leaving aside the fact that raw buffers like that are problematic, since they are often used in.... interesting ways.

[timcassell]

The problem is likely that you now need to scan the stack itself for those roots as well.

What's the problem with that? Afaik, the GC already scans the stack for references.

And there is also an issue with the second value there, which may be garbage because of the SkipLocalInit.

There's an easy solution to that: the runtime enforces zero-initializing managed types, ignoring SkipLocalsInit. I think it already does that with managed locals anyway.

[PatVax]

Consider this code:

// Assume [SkipLocalInit]
var items = stackalloc string[2];
items[0] = new string('a', 255);
GC.Collect();
Console.WriteLine(items[0]);

The problem is likely that you now need to scan the stack itself for those roots as well. And there is also an issue with the second value there, which may be garbage because of the SkipLocalInit, leaving aside the fact that raw buffers like that are problematic, since they are often used in.... interesting ways.

This code already works:

Buffer b = new();
Console.WriteLine(b[0] is null);
Console.WriteLine(b[1] is null);
Console.WriteLine(b[2] is null);

b[0] = new string("Test");

Console.WriteLine(b[0]);

GC.Collect(2, GCCollectionMode.Default, true);
GC.WaitForPendingFinalizers();

Console.WriteLine(b[0]);

[InlineArray(3)]
struct Buffer
{
    private string? _element;
}

Why wouldn't it work with shorter syntax like stackalloc string[3] or Unsafe.Stackalloc<string>(3)?