Skip to content

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

Open

Description

@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).

Activity

  1. added
    api-suggestionEarly API idea and discussion, it is NOT ready for implementation
    on Apr 29, 2021
  2. ghost added
    untriagedNew issue has not been triaged by the area owner
    on Apr 29, 2021
  3. tannergooding commented on Apr 29, 2021

    @tannergooding
    MemberAuthor

    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

  4. tannergooding commented on Apr 29, 2021

    @tannergooding
    MemberAuthor

    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)

  5. GrabYourPitchforks commented on Apr 29, 2021

    @GrabYourPitchforks
    Member

    Related to #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.

  6. jaredpar commented on Apr 29, 2021

    @jaredpar
    Member

    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>
  7. jkotas commented on Apr 29, 2021

    @jkotas
    Member

    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.

  8. tannergooding commented on Apr 29, 2021

    @tannergooding
    MemberAuthor

    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

  9. jkotas commented on Apr 29, 2021

    @jkotas
    Member

    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.

  10. tannergooding commented on Apr 29, 2021

    @tannergooding
    MemberAuthor

    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.

  11. jkotas commented on Apr 29, 2021

    @jkotas
    Member

    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.

  12. jaredpar commented on Apr 29, 2021

    @jaredpar
    Member

    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.

  13. tannergooding commented on Apr 29, 2021

    @tannergooding
    MemberAuthor

    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.

  14. 54 remaining items

  15. tannergooding commented on Feb 5, 2025

    @tannergooding
    MemberAuthor

    And this doesn't run into issues with causing pessimisation over the exiting solution in other dynamic scenarios, ...?

    It should not. For static lengths and/or for the intrinsic API in particular there should be nothing preventing us from hoisting such a case since we know the scoping of it due to the lifetime. There's also nothing preventing Roslyn from doing said hoisting itself since it would already be something implicitly done behind the scenes.

    There's tradeoffs, its just a suggestion for how this could also benefit that scenario.

    It could simply pass RuntimeHelpers.IsReferenceOrContainsReferences() by default (this doesn't require extra state)

    Yes, but its tradeoffs and largely irrelevant to the basic shape getting a nod of approval so we can finally take it to API review. We can discuss additional concepts like clearing in API review and decide if a third overload or parameter is warranted.

  16. jkotas commented on Feb 5, 2025

    @jkotas
    Member

    @jkotas how would we feel about the following shape

    It is still an unsafe API with similar problems as ValueStringBuilder. I think we should be shooting for a construct that makes it impossible to introduce a memory safety bug.

  17. MitchRazga commented on Feb 5, 2025

    @MitchRazga

    It is still an unsafe API with similar problems as ValueStringBuilder. I think we should be shooting for a construct that makes it impossible to introduce a memory safety bug.

    Perhaps something along the lines of ref struct destructor?

  18. tannergooding commented on Feb 5, 2025

    @tannergooding
    MemberAuthor

    It is still an unsafe API with similar problems as ValueStringBuilder. I think we should be shooting for a construct that makes it impossible to introduce a memory safety bug.

    @jkotas could you elaborate a bit on what you'd be expecting the long term solution to be, possible with some pseudo-code?

    Notably I don't see the potential issue with StackallocOrCreateArray<T>(). That is we only need provide an analyzer encouraging users to do scoped Span<T> buffer = Unsafe.StackallocOrCreateArray<T>(...) themselves. Because we know it stackallocs or creates an array, there is no need for a disposal pattern and the scoped keeps it from escaping. A language feature that allows us to declare the signature as scoped Span<T> StackallocOrCreateArray<T>(int length) would be even better and make this implicit, but it isn't "required". So this API seems completely safe to expose and doesn't necessarily have to be on the Unsafe class, its rather just a power API and this is a convenient place for it.

    With the StackallocOrRentedBuffer you do have the issue of:

    scoped StackallocOrRentedBuffer<T> buffer = Unsafe.StackallocOrRentArray<T>(...);
    scoped Span<T> span = buffer;
    
    buffer.Dispose();
    span[0] = ...; // mutating a buffer that's been returned to the array pool

    This issue exists because of how Dispose works on structs in general and there isn't really a "safe" option for it without the language exposing a much more expensive language feature around ownership/lifetimes and move only semantics (you need to ensure prior instances become dead on copy and need to ensure that it understand Dispose "ends" the scope early so any derived buffers also end at that point in time).

    While this danger does exist on the latter, the same danger notably already exists in the paths that would use it just hidden around much more convoluted API surface. So it seems like exposing such an API is still improving safety and would be worth it for power users given the other feature may still be years out.

    Short of a language feature, I could see the signature being Span<T> StackallocOrRentArray<T>(int length) to avoid this issue (with the same note about an analyzer and requiring the asignee involve scoped), but it would require the JIT to internally emit a T[] local and cleanup for such values in the function epilogue. This seems doable, just a bit more expensive to achieve.

  19. jaredpar commented on Feb 5, 2025

    @jaredpar
    Member

    That is we only need provide an analyzer encouraging users to do scoped Span buffer = Unsafe.StackallocOrCreateArray(...) themselves.

    Rather than an analyzer I think we'd want to encode this into the compiler. This has come up a few times in the past. Essentially how can the runtime mark an API that is ref struct returning as "cannot escape calling method"? Once that is in place APIs like this could be tagged with the attribute and it would just fall into our existing ref safety logic. Don't even need an explicit scoped cause compiler will infer the lifetime correctly to be scoped. It's a fairly low cost item for the compiler, just never had the runtime motivation to go through with it.

    Short of a language feature, ...

    I'm somewhat warry of taking this entire idea and encoding it as a language feature. Basically I'm hesitant about having Span<byte> b = malloc(...). That is putting too much logic into the compiler that feels like it should really be in the runtime. I'm definitely supportive though of ideas like I mentioned above where we can help give you the tools to enforce APIs like this.

  20. rickbrew commented on Feb 5, 2025

    @rickbrew
    Contributor

    Yeah I'd love to have something like this but it would probably need even more compiler support

    using StackAllocOrCustomAllocBuffer<T> buffer = Unsafe.StackAllocOrCustomAlloc<T>(length, static len => MyCustomWin32HeapAllocator(len));
  21. EgorBo commented on Feb 5, 2025

    @EgorBo
    Member

    I presume the perfect solution is something like this:

    byte[] buffer = Buffer.AllocateTempBuffer(len);

    and the JIT/C# either uses stackalloc (if it's not inside a loop, size is not too big), ArrayPool (if it can guarantee that the buffer never escapes the current scope and the Return is correctly placed - this is tricky as most likely it requires an inter-procedure analysis) or heap alloc otherwise.

    Maybe even just byte[] buffer = new byte[len]; Although, in this case it might be tricky/against the spec to use ArrayPool internally.

    Meanwhile Tanner's impl looks good as an internal helper to replace all ugly code we have in BCL IMO.

  22. jaredpar commented on Feb 5, 2025

    @jaredpar
    Member

    byte[] buffer = Buffer.AllocateTempBuffer(len);

    If the issue is around determining escape, why a byte[] vs. a Span<byte>? The latter with compiler help should be much easier to guarantee about escape.

  23. EgorBo commented on Feb 5, 2025

    @EgorBo
    Member

    byte[] buffer = Buffer.AllocateTempBuffer(len);

    If the issue is around determining escape, why a byte[] vs. a Span<byte>? The latter with compiler help should be much easier to guarantee about escape.

    Good point. Although, say I have:

    void Test(bool cond)
    {
        char tmp = 'x';
        ref char c = ref tmp;
        if (cond)
        {
            Span<char> span = Buffer.AllocateTempBuffer(100000);
            c = ref span[0];  // escapes the current scope?
            // ArrayPoo.Return is no longer legal here?
        }
        c = 'x'; // out of scope
    }
  24. tannergooding commented on Feb 5, 2025

    @tannergooding
    MemberAuthor

    I presume the perfect solution is something like this:

    At the end of the day, there's a balance between fine tuning perf by hand and relying on implicit optimizations. Within implicit optimizations there is then a further balance between things that can be statically relied on and things which require heuristics.

    For things we can statically guarantee, I think it's completely acceptable to rely on the implicit optimizations. This is especially true for things like standard for loops allowing bounds check elimination as the code stays idiomatic, safe, and achieves the desired performance. I likewise imagine there are some scenarios where the JIT can better understand lifetimes by knowing things are ref structs and similar and so there are some viable optimizations that can be done here statically.

    However, for things that rely on heuristics like deciding whether a T[] can be stack allocated based on escape analysis, I don't think this is a viable solution for users writing perf-critical code and is instead simply a "nice to have" for all other regular non perf critical code. That is, things like BigInteger or other framework APIs are intentionally choosing to stackalloc within a given threshold and the places this buffer is used are then often in context of complex code where it is passed through non-inlined or large callsites and so the escape analysis will fail. We could of course try and track additional metadata per method and build up a form of Whole Program Analysis as we get into Tier 1 or even some Tier 2, but this adds a lot of overhead and expense that I expect is unlikely to pay off. I expect its especially unlikely to pay off if we're already hand tuning known perf sensitive scenarios with the relevant helpers.

    There's also the consideration that by trying to optimize all code to the extreme, we can actually reduce the performance of the whole application. The stack is intentionally small/limited, CPUs have hardware level features that assume call depth is smallish and that assume the number of stack slots used per call is relatively small. They have features like tracking the last 12-15 return addresses so that it is cheap to leave a method. They have features like mirroring stack spills to the larger internal register file to avoid the penalties with memory accesses or polluting L1 cache for something that is only ever going to be CPU local. If you start stack allocating or start renting from the pool implicitly for all cases of new T[], then you actually risk reducing performance for the application and leaving nothing available for the bits of code that were hand tuned to utilize those features instead. -- For example, code that was expecting to rent from the pool for perf may find it drained because code that didn't actually benefit from using the pool went and got the available allocations first. It's all a balance and sometimes it will win and sometimes it won't, but the things that were explicitly tuned are the ones we actually care about being fast.

    So at the end of the day, I don't think we're ever going to be getting rid of features like proposed here; they will always exist and always have a place for use. I think then the right thing is trying to ensure that when they are exposed we strike the right balance of ensuring they are safe, understandable, and helper users write more idiomatic looking code while still being explicit that they want a particular optimization to kick in.

  25. jaredpar commented on Feb 6, 2025

    @jaredpar
    Member

    Good point. Although, say I have:

    void Test(bool cond)
    {
        char tmp = 'x';
        ref char c = ref tmp;
        if (cond)
        {
            // With compiler integration this would be implicitly scoped. 
            Span<char> span = Buffer.AllocateTempBuffer(100000);
            
            // This is now illegal because you're attempting to escape `span` to a broader
            // scope
            c = ref span[0];  // escapes the current scope?
      
        }
        c = 'x'; // never get here 
    }

    Can see the impact by making span explicitly scoped (sharplab)

    Note: my assumption here is that AllocateTempBuffer would desire to have lifetime of current scope. If the intent is that it's always current method then that is equally doable and the sample would start compiling. That does complicate a bit when the free happens. But in terms of lifetime it's not much different to add both options if we decide to go this route.

  26. EgorBo commented on Feb 6, 2025

    @EgorBo
    Member

    Can see the impact by making span explicitly scoped

    The question is - can you enforce it? Or the safety is going to be based on an analyzer that will suggest user to put scoped there?

    Ah, the answer is here #52065 (comment)

  27. jaredpar commented on Feb 6, 2025

    @jaredpar
    Member

    The question is - can you enforce it? Or the safety is going to be based on an analyzer that will suggest user to put scoped there?

    Ah, the answer is here #52065 (comment)

    Correct. My suggestion was the language provide a mechanism to let the runtime dictate that a ref struct returning method had a specific lifetime. Imagine for example there was an attribute that said [LifetimeCurrentMethod] or [LifetimeCurrentScope] that compiler would recognize as part of it's lifetime rules.

    Span<byte> Use1() => M1(); // Error: M1 is safe to escape to current method
    Span<byte> Use2() => M2(); // okay
    
    [LifetimeCurrentMethod]
    Span<byte> M1() => ...
    Span<byte> M2() => ...;

    The attributes would allow only to restrict returned lifetimes, not increase them.

  28. jkotas commented on Feb 10, 2025

    @jkotas
    Member

    @jkotas could you elaborate a bit on what you'd be expecting the long term solution to be, possible with some pseudo-code?

    The discussion between Jared and Egor above is a good example of the kind of solutions we should be thinking about.

    it seems like exposing such an API is still improving safety and would be worth it for power users given the other feature may still be years out.

    Replacing unsafe APIs with a bit more safe unsafe APIs is not very appealing to me. We can do it occasionally if there is a strong motivation, but it won't get us to where we need to be. Memory safety is not like performance where the incremental approach works fine.

    feature may still be years out

    I expect that we will need to be prioritizing memory safety related features higher compared to where we were in the past. Message from our CEO: Prioritizing security above all else.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions