CLR/JIT should optimize "alloc temporary small object" to "alloc on stack" automatically

[ygc369]

If a small object's reference is never stored in heap or static variables, (only stored in local variables), it is temporary, the CLR or JIT should alloc it on stack and free it in time. Thus, GC pressure would be lower. This feature is just like escape analysis technique in JVM.
I've suggested this in Roslyn forum(dotnet/roslyn#2104), but they said I should suggest here.

category:cq
theme:stack-allocation
skill-level:expert
cost:large

[cmckinsey]

Thanks, this is something the team is aware of and discussed. A specific example in a real-world workload that you can share would help us prioritize this request. We already have synthetic examples.

[zpodlovics]

You may be also interested with the following proposal and prototype implementation project: Stackalloc for reference types with Roslyn and CoreCLR [1] [2]

It introduce a generalized stackalloc with a transient variable modififer to solve the problem.

The transient variable modifier
Lets start by defining the concept of a transient variable:
  A transient variable can only be declared for a local method variable or parameter, and cannot be used on a ref/out parameter.
  A transient variable can only be assigned to another transient variable.
  A transient variable can receive a non transient variable as long as types matches

[1] http://xoofx.com/blog/2015/10/08/stackalloc-for-class-with-roslyn-and-coreclr/
[2] https://github.com/xoofx/StackAllocForClass

[mikedn]

@cmckinsey

A specific example in a real-world workload that you can share would help us prioritize this request.

This might be a chicken and egg situation. If the optimization doesn't exist people will try to twist the code to avoid allocations (see for example params support for IEnumerable) and as a result there will be fewer optimization opportunities. On the other hand if the optimization exists then perhaps people will concentrate more on actually writing code instead of figuring out how to avoid allocations.

[OtherCrashOverride]

It introduce a generalized stackalloc with a transient variable modififer to solve the problem.

You will need the same constraints that ValueTypes have so you may as well use a struct instead of a class. For example, you can not have class finalizers. The only difference I see is that the compiler is calling a ctor for you instead of having to call MyStruct.Initialize(); yourself.

[cmckinsey]

@mikedn I don't disagree, but we need some way to help assess priority as we have other opportunities were we can also improve code-quality and this would help to prioritize. We have prototyped this kind of transformation in other experimental systems. Because of the challenges in the compiler automatically finding legal opportunities, which is even more challenging in JIT environments, my experience has been that developers that really want to avoid heap allocations end up having to do manual source changes anyway, such as using ValueTypes.

@OtherCrashOverride yes, that is correct. And there are other correctness rules the compiler must observe, for example this transformation might lead to stack-overflow if done on a recursion path.

[GSPP]

Did the team look at the work the Hotspot JVM team did with Escape Analysis? They have production experience in a very similar setting and should be able to answer many open questions.

You should be able to run benchmarks on the JVM with Escape Analysis turned on and off. They have a command line switch. The performance differential should carry over to the CLR.

Prime use cases would be enumerators (LINQ queries) and string processing I think. These can generate tons of garbage. Also things like new FileInfo(path).Exists. Or updating immutable data structures multiple times in the same method.

[mikedn]

You should be able to run benchmarks on the JVM with Escape Analysis turned on and off. They have a command line switch. The performance differential should carry over to the CLR.

The situation is a bit more complicated than that. Java doesn't have value types and as such it needs allocation optimizations more than .NET needs. Also, it's interesting that the "Escape Analysis for Java" paper shows that for some benchmarks the percentage of objects allocated on the stack can exceed 70% but the execution time improvement is no more than 23%. And as far as I can tell that also includes improvements due to the elimination of locks for objects that don't escape the thread.

Prime use cases would be enumerators (LINQ queries) and string processing I think.

Of all possible use cases LINQ is the least likely to benefit from such an optimization. It's interface reliance means that it is difficult to inline methods or at least perform some interprocedural analysis. Without inlining the created enumerators are returned and it's difficult to allocate such objects on the stack. They cannot be allocated on the callee frame and anyway the callee has no way of knowing that the object doesn't escape the stack, only the caller knows that. I suppose one could imagine some sort of "return allocation context" that's passed from the caller via a hidden function parameter and allows the caller to customize the way returned objects are allocated but that's a rather crazy thing to do.

Personally I'd be happy enough if, for example, small arrays could be allocated on the stack so contortions like that described in "params support for IEnumerable" wouldn't be needed. But unfortunately the cost to achieve this might be too great.

[GSPP]

The Java remarks are entirely true.

---

Regarding LINQ, here's an idea: If the callee is known to allocate a small, bounded amount of memory (this is generally the case for enumerator allocating methods) and if no such pointer escapes according to some simple data flow tracing (also the case here) then change the base pointer for heap allocations to the stack temporarily. Like this:

1. Set allocation base to free spot on the stack (at the end of it).
2. Call allocating callee. It will now allocate everything on the stack. The allocations can be dynamic (e.g. conditional). They do not need to be statically known.
3. Callee returns pointer (to stack memory)
4. Caller restores allocation base pointer

This rather simple scheme should match a lot of functions. No need to inline.

Call targets must be known but that also does not require inlining. It requires the JIT to determine the return type (which is pretty much always known in the case of iterator methods) and apply that knowledge to devirtualize all calls. I do not need to inline OrderBy in order to determine that it returns exactly an OrderedEnumerable. On the other hand this will not work for Select because it is too sophisticated.

No need to inline but it requires analyzing quite a few functions (all that touch the memory allocated).

---

A second simple scheme would be to allocate all ref types on the stack if their address is never passed to any other method, returned or stored to non-locals. And then have a (reliable) way to blast all aggregates allocated on the stack to registers. This scheme would catch a lot simple helper classes like vectors, points, some strings, Utf8String's, ....

If we can get a basic implementation of both of these optimizations that should catch a lot. And btw, I think that 23% execution time improvement is a fantastic number. Depends on the workload obviously.

[mikedn]

Call allocating callee. It will now allocate everything on the stack. The allocations can be dynamic (e.g. conditional). They do not need to be statically known.

It can't allocate everything on the stack, some allocations may escape and the callee won't always know which ones. You really need to distinct allocation contexts - "GC allocation context" and "return allocation context". The return context is normally the same as the GC context but the caller may replace it when possible. The callee always uses the return context to allocate the returned object. The return context cannot be used to allocate any other objects, including objects that are referenced by the returned object since the caller may escape those objects.

A second simple scheme would be to allocate all ref types on the stack if their address is never passed to any other method, returned or stored to non-locals.

That's the "normal" scheme. Though it's a bit too restrictive, calling any method of an object implies passing the object address to the method (unless the method is inlined) so you wouldn't be able to do much with such objects. The compiler should analyze the callees a bit for best results, a call depth of less than 5 might suffice in many cases. For example, it should be possible to stack allocate the Stack object used in the bellow example:

void foo(BasicBlock bb) {
    var stk = new Stack<BasicBlock>();
    stk.Push(bb);
    while (bb.Count > 0) {
        bb = stk.Pop();
        // other code that calls stk.Push
    }
}

[GSPP]

OK, all true. I really should not specify any particular (naive) escape analysis scheme but I think it's possible to devise some rather simple scheme that kills a lot of allocations and enables developers to be more productive because they can use more helper objects.

I think a key point is that inlining does not have to occur in order to infer information about the behavior of methods. Often, escape behavior can be summarized for a method in a meaningful way ("does not store to the heap/statics at all" or "does not create a new reference from the heap/statics for argument 3"). We now don't have a code size problem, only need to deal with compile time.

[mikedn]

I think a key point is that inlining does not have to occur in order to infer information about the behavior of methods.

Yes, in general inlining doesn't need to occur. It's just the "return new object" case that benefits from inlining.

[kostrse]

@cmckinsey Here's a practical example where escape analysis could be really helpful.

Let's have a look at this snippet in F# code:

// ReferenceEscapeTest.fs
module EscapeTest

    // a:int -> b:int -> int
    let diff a b =
        let (min, max) = if a > b then (b, a) else (a, b)
        max - min

From functional programming standpoint this is a very primitive construction which utilizes a tuple for dealing with two local variables in one expression. For an F# developer those are just cheap local variables, presumably allocated on stack.

fsharpc --target:library --optimize+ ReferenceEscapeTest.fs
F# Compiler for F# 3.1 (Open Source Edition)

But when we look at the disassembled IL:

using Microsoft.FSharp.Core;
using System;

[CompilationMapping(SourceConstructFlags.Module)]
public static class EscapeTest
{
  [CompilationArgumentCounts(new int[] {1, 1})]
  public static int diff(int a, int b)
  {
    Tuple<int, int> tuple = a <= b ? new Tuple<int, int>(a, b) : new Tuple<int, int>(b, a);
    return tuple.Item2 - tuple.Item1;
  }
}

We can see that, in fact, we're unintentionally abusing heap allocation for a basic arithmetic operation.

P. S. This might (or might not) be addressed by F# compiler in the first place, I just not aware of design decisions what led to this code generation in this particular case, but my point is that this optimization on the JIT side could definitely make the difference.

[SunnyWar]

Example code that can benefit from this is riddled all over FxCore; E.g: HastSet.IntersectWithEnumerable and CheckUniqueAndUnfoundElements both allocate a temporary BitHelper object. List.InsertRange allocates a temporary array. ConcurrentBag new's up a SpinWait in the CanSteal method.

Also, almost all code that has a "using" statement has an object that goes out of scope can be cleaned up immediately. No need to wait for the garbage collector. just call dispose and free it.

like...
using (var sr = new StreamReader(fileName))
{...}

And...
try/catch clause that eat the exception, the exception can be cleanup up, no need for GC.

And...
I can't count how many times I've called string.Split() on a massive amount of data. It's a shame all those arrays allocated and garbage collected unnecessarily.

Finally...
As Roslyn is written in C# and needs to parse thousands of text files, I bet it creates many millions of small objects on the heap that can be collected immediately after they are tokenized and go out of scope.

To name just a few.

[OtherCrashOverride]

Also, almost all code that has a "using" statement has an object that goes out of scope can be cleaned up immediately. No need to wait for the garbage collector. just call dispose and free it.

using simply calls the IDisposable interface. It does not provide any guarantee about object lifetime. Inside the using block, the object could be assigned to objects/variables that would maintain its 'liveness' and its perfectly valid to do so despite it being 'disposed'.

This is the reason the GC has to run to finalize the object. It has to trace to determine if an object reference is still held anywhere. This is also the point where 'escape analysis' enters the discussion.

GC.SuppressFinalizer() in Dispose() should make object clean up more efficent by eliminating a call to the dtor() during GC.

[SunnyWar]

@OtherCrashOverride sure, it's possible that the object is assigned to something inside the using, and in this case I would expect the compiler to see this, be conservative, and not free it. However, I claim the 80% case is this does not happen. Now, perhaps you are talking about the case where there are nested using statements, which is pretty common. In this case, I hope the compiler would be smart enough to unwind the stack and see that after Dispose all the objects can be freed immediately.