Proposal: Allow to allocate objects on the stack

[ygc369]

To reduce GC, C# should provide mechanisms to allocate objects on the stack.

1. Escape Analysis. This is the most important thing. We can get "free" performance improvement through it without any code change.
2. Syntax to force to allocate on the stack.
   (from http://xoofx.com/blog/2015/10/08/stackalloc-for-class-with-roslyn-and-coreclr/)

Escape analysis in many case is impossible to perform. Allocate a class and pass it to a virtual method (for which you know only the type at the callsite, unless allocated in the same method), and you won’t have any way to determine whether stackalloc is safe or not.

So besides escape analysis, we want to have syntax to guarantee some objects allocated on the stack. If the stack-allocated object has finalizer, then its finalizer should be executed once its last reference goes out of scope, not need wait until GC finishes.

[gafter]

@ygc369 What form would this take as a language feature?

[ygc369]

@gafter
The form is just like what xoofx said in his article. I copy some parts here:

This is done first by introducing a new keyword transient to identify a variable that cannot be stored outside of the stack.
Then we can revisit the stackalloc operator to support the physical allocation on the stack.

The transient variable modifier
Lets start by defining the concept of a transient variable:

1. A transient variable can only be declared for a local method variable or parameter, and cannot be used on a ref/out parameter.
2. A transient variable can only be assigned to another transient variable.
3. A transient variable can receive a non transient variable as long as types matches

public void Runner(transient MyProcessor processor)
{
    (...)

	var myProcessor = processor;  // is equivalent to an explicit declaration of:
	transient MyProcessor myProcessor2 = processor; 

	// We can access any method/property/field on this transient object
	processor.Run(...);

	// But we cannot store the transient variable into a non transient avariable 
	MyProcessor test = processor;  // won't compile
	// or cannot store it in a field/property
	myProcessorField = processor;  // won't compile

    (...)
}

When compiling the transient keyword, it would only be stored to a TransientAttribute for method parameters while all local variables would just be statically verified at compile time. The compiler should only ensure the rules defined above, nothing more.

This is introducing a new keyword, something that the language team is not going to take easily for granted!

New stackalloc operator
If you have never used the stackalloc operator, it allows to instantiate an array of blittable valuetypes on the stack:

unsafe {
        // Allocate an array of int
        int* pInts = stackalloc int[5];
        // Allocate an array of Vector3 struct (which cannot contain any reference type)
        Vector3* v = stackalloc Vector3[4];
}

But we notice that:

1. it requires an unsafe context
2. it doesn’t allocate a .NET array but actually return only a pointer to the first element of the allocated array. You don’t have access to a Length property nor you could use this return value with code expecting regular managed arrays.
   In I ideal world, I would replace completely this old operator by a new behaviour that would allow both allocation on class/reference type on the stack, as well as array of class/structs (and not only blittable structs, as it is today). This is what I have chosen for in this prototype as I found it much cleaner and I don’t have to introduce a new keyword.

Basically, the new stackalloc operation should allow exactly the same calling constructors conventions then the new operation.

In order to use the stackalloc operator, you can only assign it to a transient variable, like this:

// Create a new instance of MyProcessor on the stack
	transient MyProcessor processor = stackalloc MyProcessor(...);
	processor.Run(...);

In the case of the lambda, I haven’t work out how the syntax would be used. The compiler could allow an implicit stackalloc operator when the parameter of the method receiving the argument is transient. But we still need a way to define how a lambda is declared transient, like prefixing by transient may be fine (but haven’t checked in terms of parsing coherency):

/* Assume that the lambda is allocated on the stack excplitely when 
    it is marked as `transient` or prefixed by `stackalloc`? */ 
    var matchElement = list.FirstOrDefault(transient t => t.Name == name);

Safe transient class for this access
There is a case where a class is allocated on the stack and used through a transient variable. But if we call a method on this variable, within the method, we can’t ensure statically that we are in the context of a transient call and we may be able to store the this pseudo variable to a location that is not declared as transient, which would violate one of the rule defined above.

Here is a example of the problem:

public class MyProcessor
{
    public MyProcessor Bis;

    public void Run()
    {
       // this can be used in the context of a transient callsite but here, we cannot
       // verify this. It would mean that the `store` variable could live more than 
       // the callsite (and will just result in a program crash)
       Bis = this; 
       (...)
    } 
}


var processor = stackalloc MyProcessor();
processor.Run();

// Bam! The processorBis variable is no longer a transient variable 
var processorBis = processor.Bis;

So It seems (all this post needs lots of peer review!) that it is possible to solve this problem at the cost of making the CLR runtime and the Roslyn compilation to cooperate:

1. At compile time, when Roslyn compile a type, it should store the information whether a particular type is transient safe. It has basically to check if the this pointer is stored/pass anywhere to a non transient method/property/field. In the end, we could just store this information as a metadata Attributes on the class (but might be safer to store it in the PE metadatas directly). Tracking this at the compiler will not be easy, moreover if we want to track all assignments (and possibly raw casts) that are on the stack.
2. At runtime time, when a type is loaded, we verify at classloader/import time that a type (and all its ancestors types) are actually transient safe (result stored in the methodtable/type). Then, at JIT time of a property/method, at every stackalloc callsite (basically, whenever there is a local variable valuetype referencing a class), we verify that the class that we want to allocated on the stack is transient safe.

[benaadams]

@xoofx do ref locals hold the required constraints? e.g. stackalloced classes can only be assigned to ref locals rather than introducing a new transient modfier

[sirgru]

Related:
dotnet/roslyn#16154
https://github.com/dotnet/coreclr/issues/1784

[ygc369]

@benaadams
I think ref locals are OK for referring to stackalloced classes.

[xoofx]

@benaadams not really. A ref to a reference types doesn't tell you that this reference was allocated on the stack (it could be a ref to a heap alloc field). When passing a transient reference to a parameter method, you can't rely on ref, you need to have a semantic that says "you should not store this reference anywhere except on the stack in a transient variable"...

[xoofx]

Before last summer, I heard that there was an internship in the .NET team supposed to work on this... (not strictly the transient thing, afair, it was to try to get escape analysis working for very basic cases, but not for parameter passed to virtual methods...etc.) but not sure what happened to this...

My blog post experiment provides a very primitive specs and a functional prototype, but it may requires a more formalized RFC, and someone dedicated from MSFT .NET Team to follow this (as it has an impact on the runtime and the language)

[svick]

@xoofx I believe you're talking about dotnet/coreclr#6653. No idea if there is any followup to that.

[xoofx]

@svick good catch, yes, that's this one 😉

[fanoI]

In my humble opinion stack escape analysis could be implemented for the simplest cases as a starting point, I don't like at a developer using a high level language to have to think where allocate objects thins should be the work of the compiler...

[wanton7]

@fanoI in my opinion we should have both escape analysis and assurance something is allocated from stack, like this proposal is proposing. One thing I agree with you is that if it's hard to know if something escapes, then just do simplest cases and start from there.

If someone is creating software where you need absolute guarantees that something doesn't allocate, you need way to enforce stack allocation, like game loop, real-time audio or maybe .net framework itself.

I think when using stack allocation keyword/attribute for method parameter, it should only tell that it's safe to call it with stack allocated class, you should be able to use class allocated from heap as well.
This could be combined with escape analysis. Example if you have simple method that doesn't enforce stack allocation for it's parameter that is reference to a class and call's method from a class library with that same parameter and that library method's parameter has support for stack allocation then you know it's not escaping.

[Korporal]

I wondered about this years ago. It struck me that the language designers could have done something more elegant than what they eventually did do.

Specifically they chose to associate how something is allocated with it's type and I think this could have been done in a better way.

Rather than having struct and class for defining types, they could have simply used the keyword type and leave the specifics of allocation to the point of the declaration.

This way we'd simply create types and we'd decide whether we want these on heap or stack when we declare them.

public type UserInfo
{
    string name;
    string rank;
    int age;
}

ref UserInfo user_class; // 'user_class' will be allocated on heap - a class.
val UserInfo user_struct; // 'user_struct' will be allocated on stack - a struct .

Instead we have the keywords class and struct that not only define a type's characteristics but also how it is to be allocated in memory.

Currently in C# a class and a struct with identical member fields are structurally the same except that instances of the class carry a runtime metadata header.

There's no way this will change in C# but I wonder if this approach would have been better than the one chosen, where we must declare a type and its allocation mode together (struct or class).

Today if we have a type that (for whatever reasons) must be available both as heap and stack instances we must either declare a class version and a struct version or declare a struct version and then declare a struct member in the class:

public struct SystemDataS
{
    int count;
    int child_count;
    int timestamp;
}

public class SystemDataC
{
    SystemDataS body;
}

The above defines the type in one place and 'reuses' it in the defintion of the class SystemDataC, this is clumsy and inelegant - separating a type defintion from the semantics of how its allocated is IMHO better.

[HaloFour]

@Korporal

It's the CLR that strikes a sharp distinction between the two. C# as a language is required to observe that distinction. Not even C++/CLI allows you to arbitrarily decide where a managed type is allocated.

[benaadams]

@Korporal struct doesn't specify its allocation type. A struct can be heap or stack (if boxed or stored as member of class)

[xoofx]

Specifically they chose to associate how something is allocated with it's type and I think this could have been done in a better way.

This is not really accurate...

First, you can perfectly allocate a struct on the heap directly (it is called boxing, though I agree, unfortunate that the language made the new operator for struct as not a heap allocation...anyway) and you can also (as my prototype above) allocate a class on the stack. So it is not the type that dictates its allocation model as you said. Note that when you are on the heap, you always need a "vtable" (but for struct, it is more used as a "type table")

Then, the language made a strict difference between passing by value and passing something by reference. By default, a struct is passed by value, a class by reference. You can pass a struct by reference but you can't pass a class by value (no copy semantics)

But a more fundamental difference is the presence of a vtable. A class will always have a vtable, supports inheritance and virtual dispatch (even if it is allocated on the stack). A struct can have a pseudo vtable only when it is allocated on the heap, but it doesn't support inheritance (you can add a loosy inheritance as described in another of my post) and can't have virtual dispatch.

What you are looking for is what Go or Rust have been providing. Both are quite "recent" languages, keep in mind that C# is in the footsteps of Java, so don't expect a platform that is more than 15 years old where OOP was king to comeback to a "simpler" type model.... But neither Go or Rust provides data inheritance for their types. They basically don't have any vtable. They are either a value or a reference (with a * for Go or & for Rust). They support both static and dynamic dispatch (that is different from virtual dispatch, while C# also support static dispatch, and interface dispatch which is more costly than virtual). So this is the fundamental difference. Inheritance of data is not allowed and functions/process associated to a data is separated from it.

As said by others, C# (and more generally as @HaloFour said, the CLR) is deeply rooted in OO language concepts. We can't really expect any changes at this level of the foundations of a language.

[ygc369]

@HaloFour
As a very similar language, Java has escape analysis years ago, so I think C# could have it. If CLR doesn't support allocating object on stack, then CLR need to be modified.

[Joe4evr]

you can perfectly allocate a struct on the heap directly (it is called boxing [...])

Not necessarily. A struct as a class field also lives on the heap without being boxed.

[HaloFour]

@ygc369

As a very similar language, Java has escape analysis years ago, so I think C# could have it. If CLR doesn't support allocating object on stack, then CLR need to be modified.

The situation in Java is identical to the one in C#. Neither language supports allocating classes on the stack. Neither bytecode has opcodes that can support allocating classes on the stack. There is absolutely no way for a developer to explicitly specify that they want a class allocated on the stack.

The difference is in the JIT. I see that you've already opened https://github.com/dotnet/coreclr/issues/1784 and that is where that belongs. I am a proponent of that optimization as well.

[Joe4evr]

I feel the need to re-iterate Eric Lippert's amazing post: The Truth About Value Types. Specifically because people keep proposing language level changes to something that's only an implementation detail. As HaloFour said, you go to the CoreCLR repo for that, not the language.

[jnm2]

Fyi, work has started on stack-allocated objects. dotnet/coreclr#20251