New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Do not claim that structs are on the stack #4561

Open
svick opened this Issue Mar 6, 2018 · 17 comments

Comments

Projects
None yet
7 participants
@svick
Collaborator

svick commented Mar 6, 2018

The new Operator article says:

Value-type objects such as structs are created on the stack, while reference-type objects such as classes are created on the heap.

Depending on how you understand it, this claim could be considered true, if you consider that value types are created on the stack, but then can be copied to the heap.

But I think it's still too confusing and too close to the common misconception of "value types are stored on the stack, reference types on the heap" and that the wording should be changed.

(But I'm not sure what should it be changed to, which is why I'm creating an issue and not a PR.)

@BillWagner

This comment has been minimized.

Member

BillWagner commented Mar 7, 2018

I'd like to start a discussion on this issue.

First, this is much larger than a single topic. A search of the repo for the phrase "on the stack" produces more than 100 occurrences. Some are correct, in that they refer to a Stack collection. Most refer to the common inaccurate phrase that value types are "on the stack".

@ericlippert wrote a few great blog posts explaining that the relevant fact for value types is they are copied by value, not that they are stored on the stack. 1 2

The recent additions of in, readonly struct and ref struct declarations make the copy semantics much more relevant than the storage implementation.

I propose that we remove any description of stack storage from all documentation on value types in the language guide(s) and the .NET guide, and replace that explanation with a correct discussion on the copy semantics.

@svick svick changed the title from The new operator article should not claim that structs are created on the stack to Do not claim that structs are on the stack Mar 7, 2018

@dopare

This comment has been minimized.

dopare commented Mar 7, 2018

I would suggest to add clear note that value types are not restricted to stack storage instead of removing all descriptions about stack storage.

@jskeet

This comment has been minimized.

jskeet commented Mar 7, 2018

While I'm always nervous about disagreeing with Bill, I'd argue that ref struct makes the stack/heap distinction more relevant than ever before. The rules around what you can do with a ref struct are designed to avoid it escaping the stack. (The implementation details of captured variables etc then definitely leak into the language.)

I think it would make sense to start with the "copy by value" part, but then include material about heap vs stack in later material.

@ericlippert

This comment has been minimized.

ericlippert commented Mar 7, 2018

This is indeed a tricky topic with over a decade of misinformation and confusing documentation muddying the waters. So indeed, first, do no further harm!

The situation is further complicated by the fact that most people still reason from the perspective that coroutines or closures don't even exist, even though they've been in C# for well over a decade.

If I had the opportunity to do it all over again knowing what I know now, I would emphasize the following key points:


  • Many methods in C# are coroutines. That is, upon activation they can subsequently return, hang (run forever), throw, or suspend. (That is: yield or await) A method which never possibly suspends we can call a "normal method". A coroutine which suspends can be resumed.

  • Variables are storage locations that store values. Values are either references or instances of value types.

  • "Temporary" variables are special unnamed variables used to hold values created during expression evaluation.

  • Variables have a lifetime that is either long or short. A variable with short lifetime is one where we know at compile time that it will never be used after the return/throw of the method that created it, or across a suspension of the coroutine that created it.

  • Variables not known to have short lifetimes must conservatively be given long lifetimes.

  • An aliasing relationship -- that is, two names for the same storage location -- can be imposed by ref/out/in. Establishing an alias must never cause the aliasing variable to live longer than the aliased variable.

  • The transitive closure of references in long-lived variables lives arbitrarily long; this imposes significant runtime costs because a garbage collector must work out which long-lived variables are dead, and collect their storage. However, the total amount of storage available is limited only by address space available to the process.

  • No such runtime costs are imposed by short-lived variables. However, an extremely small amount of memory -- typically only a million bytes -- is reserved for short-lived variables; if this pool is exhausted then the program will fail catastrophically with no opportunity to recover.


You'll note that nowhere in there did I say anything about heap, stack or registers; all of those are implementation details. But everything follows logically from these principles. A closed-over local variable can be accessed after the method which declared the local returns, and therefore it is on the long-term pool. And so on.

However, at this point, decades in, it is probably too late to go refactoring all of the documentation from scratch.

@BillWagner

This comment has been minimized.

Member

BillWagner commented Mar 8, 2018

@jskeet This is a great discussion.

Consider this explanation of ref struct:

A ref struct must have a known short lifetime (to use Eric's term above). It follows that ref struct types can only be local variables of methods that are not coroutines, or members of another ref struct. They cannot be members of a class or a struct. They cannot be return values (see note below). They cannot be captured by lambda expressions. They cannot have lifetimes that span await in async methods, or yield return in iterator methods.

Note: a ref struct can be returned by ref when that ref struct was passed into the method by ref.

I think that "on the stack" has been a colloquialism for "variable known to have a short lifetime".

@jskeet

This comment has been minimized.

jskeet commented Mar 8, 2018

I'd say that "on the stack" is more "the usual implementation of variables known to have a short lifetime" - which ties in with Eric's description. On the other hand, by the time we start talking about the amount of memory available for short-lived variables, we're into implementation details anyway.

I think there's more to using stack/heap than just the age of C# and the amount of existing documentation - there's also the expectations coming from developers in other languages, who look for familiar concepts. If we could start the whole process of describing all programming languages from scratch, Eric's description might be ideal.

Some quick points to note about ref structs though (having been exploring them more just this week):

  • They can (currently, at least) be used in iterator methods, so long as they're only used "between" yield return statements (rather than usage potentially straddling a yield return statements)
  • I'd hope that the same would be true for async at some point, even though it appears not to be yet
  • They can be declared in lambda expressions, but can't be captured from an enclosing scope by lambda expressions

Let me know if you'd like examples of all of these for further checks as to whether they're the expected behavior or not. It wouldn't be entirely unusual for me to have wandered into corner cases...

@BillWagner

This comment has been minimized.

Member

BillWagner commented Mar 8, 2018

Both of us missed the full list, which is here as a proposal in the csharplang repo

To your bullet list:

  • They can (currently, at least) be used in iterator methods, so long as they're only used "between" yield return statements (rather than usage potentially straddling a yield return statements)

The third bullet item in the proposal indicates that ref structs should be legal in async methods, as long as they are not in scope at the await expression.

  • They can be declared in lambda expressions, but can't be captured from an enclosing scope by lambda expressions

Yes, I updated my comment above.

@jskeet

This comment has been minimized.

jskeet commented Mar 8, 2018

I didn't miss the proposal - it's just it's inaccurate, in my experience :) Sample code:

public ref struct RefLikeStruct
{
    public void Method() => Console.WriteLine("Hi");
}

public class Test
{
    public static IEnumerable<int> IteratorMethod()
    {
        yield return 0;
        // Rules say this should be invalid: foo is in scope
        // for both yield return statements. It compiles for me.
        var foo = new RefLikeStruct();
        foo.Method();
        yield return 1;
    }

    public static async Task AsyncMethod()
    {
        await Task.Delay(1000);
        {
            // Rules suggest this should be valid: foo is not in
            // scope at any await expression. It doesn't compile for me.
            var foo = new RefLikeStruct();
            foo.Method();
        }
        await Task.Delay(1000);
    }
}

The error message for the last part is unhelpful too:

Parameters or locals of type 'RefLikeStruct' cannot be declared in async methods or lambda expressions.

The part about lambda expressions is definitely not true for local variables...

I've been assuming that the C# team is on the case in terms of tightening up the spec language, error messages, and actual error cases. If you think I've discovered areas they should be aware of, I'm happy to file issues.

@BillWagner

This comment has been minimized.

Member

BillWagner commented Mar 8, 2018

ping @VSadov @jcouv Should Jon file issues based on the above?

@VSadov

This comment has been minimized.

Member

VSadov commented Mar 8, 2018

I think allowing ref structs "between yields" in iterators is a bug.
We catch the violation when it is time to capture, so it is safe, but capturing is an implementation detail.

FWIW which and how locals are captured depends on the precision of flow analysis. It gets refined with almost every major release. It may also be reasonable to capture all locals in Debug - so that you would not lose the values when method is resumed after await/yield.

Currently the language spec says unconditionally that ref struct locals are not allowed in iterators/async.
In the future this may be relaxed to exclude blocks that do not contain yield/await.
And that would have effect of requiring that locals in that block are never captured, which is ok, even considering the Debug scenario.

I have logged a bug on that - dotnet/roslyn#25350

@VSadov

This comment has been minimized.

Member

VSadov commented Mar 8, 2018

Re: "structs on the stack"

Structs vs. classes distinction is mostly defined in terms of value/reference semantics. Structs certainly do not need to be on stack.

The lifetime of variables (not just locals) is tied to scoping. As long as variable can be accessed, it must exist. Therefore, for example, when a variable is accessible from a nested method which may outlive the outer method where the local is formally defined, then such local cannot be implemented as a slot in the method frame and must be "captured", but that is an implementation detail.

Note that this does not prohibit situations when underlying storage lives longer then needed. That could be wasteful, but otherwise noone would observe such difference through regular means provided in the language.
(platform services like reflection and unsafe code should be ignored here since those specifically allow to glance at implementation details and we are talking about semantics)

The problem with ref structs (and ref locals/parameters) is that "stack only" for these is a limitation of the platform which does not permit ref fields - primarily to make it simpler for GC.

In a way the stack-only "leaks" the constraints of the underlying platform and that is why such details as capturing have an impact.

@ericlippert

This comment has been minimized.

ericlippert commented Mar 8, 2018

I agree with VSadov; the simpler rule is the better rule. An interesting question though is should this be illegal? Suppose Whatever() returns ref int. This is legal:

yield return foo;
Whatever() = 123;
yield return bar;

It seems slightly odd that this is legal, but making the ref int explicit in the source code by introducing an explanatory local variable makes it illegal.

@VSadov

This comment has been minimized.

Member

VSadov commented Mar 8, 2018

Not much different from the following being legal

yield return foo;
Whatever(ref someX);
yield return bar;

And the following is not.

yield return foo;
ref var alias1 = ref someX;
Whatever(ref alias1);
yield return bar;
@VSadov

This comment has been minimized.

Member

VSadov commented Mar 8, 2018

The most obscure case IMO is the stack spilling. That is where we have to produce an error even if no locals were involved:

Whatever(ref Lalala(), await Task.Yield());

The case is nontrivial and rare. It is not even considered a language/binding error, but just a known limitation of lowering strategy - it observably does not impact lambda inference for example.

@BillWagner

This comment has been minimized.

Member

BillWagner commented Mar 14, 2018

Thanks for the very thoughtful discussion. I thought a lot about how to explain this and have a proposal.

  • We explain that structs follow value semantics as their main feature.
  • We mention that structs may be known to have lifetimes are known to end when they go out of scope so storage can be reclaimed more effectively. This feature is mentioned when appropriate to the topic.
  • We mention that you can force structs to follow reference semantics when the cost of copying is significant or a design calls for observing modifications. This is mentioned when appropriate to the topic.

Specific tasks:

  • For this issue (on operator new) the entire paragraph should be re-written. It could be interpreted to say using statements force memory to be reclaimed, which is also wrong. Do you want to do this @svick?
  • I will open a new issue that lists where "on the stack" is used incorrectly with these recommendations. That can happen over time as those topics are updated.

Justification

There are two important features of struct types:

  • Structs follow value semantics (except when they don't).
  • Structs are allocated on the stack (except when they aren't)

The performance benefits of many of the new features follow because of those two facts (and exceptions)

Explanations become much clearer when we focus on the first fact and its exceptions. I think the exceptions are much easier to explain:

  • Structs follow reference semantics when passed by in, out or ref as arguments.
  • Structs follow reference semantics when returned by return ref.
  • The new operator returns an initialized struct that may then be copied by value to initialize a variable. (The new operator may have operated on the memory already referenced by the variable, but that's not observable).

The presence of ref in or out makes it clear in the first two cases. The final one is really an implementation detail that doesn't help or harm understanding the code.

The exceptions for "structs are allocated on the stack" are much harder to explain:

  • When struct types are members of a reference type
  • When struct types are boxed
  • when struct types are stored in a collection or an array
  • When struct types are captured in any co-routine
  • ref struct types must be allocated on the stack.
  • I bet I missed some.

Hmm. There isn't an easy explanation here. The first three aren't too hard, but it is extra cognitive load. The fourth once could be labeled "Here be dragons". There are many cases where it's not easy for most readers to look at code and determine quickly what variables will and won't be captured.

The only language location where "on the stack" really has meaning is for ref struct types.

But what about storage location?

Next, I looked at when the phrase "on the stack" was used in reference to structs and allocation (hat tip to @rpetrusha who explained the history of why this was used).

We've used the phrase "on the stack" in two ways:

  • as a substitute for "follow value semantics" when describing parameters and local variables.
  • to describe variables whose lifetime end at the point where they go out of scope. This speaks to the more immediate memory reclamation.

Those two phrases are more accurate, and reinforce a better understanding. The second phrase is also useful in describing ref struct: they can be declared in locations where the lifetime ends at the point where they go out of scope.

Comments?

[ updated per Jon's first bullet below. Still thinking about the second.]

@jskeet

This comment has been minimized.

jskeet commented Mar 14, 2018

Just two comments after skimming:

  • I didn't think ref struct types actually followed reference semantics. They're still copied by value, it's more restrictions around where they can escape that are important, isn't it?
  • I think blurring the line between "reference type" and "by-reference argument passing" by talking about "reference semantics" may cause some conceptual problems for people. In particular, it begs the question of what happens to a parameter of ref StringBuilder x etc.

Will ponder more, but wanted to give those two bits quickly.

@VSadov

This comment has been minimized.

Member

VSadov commented Mar 14, 2018

I agree with Jon here. ref struct is mostly about constraints on their use. They also may optionally contain other ref structs as instance fields.
Some ref structs (like Span<T>) may internally contain direct references to other data, but that is a bit of implementation detail. Ordinary struct that contains an {array, index} tuple and a ref indexer could come very close in functionality to the Span<T>. Technically such struct also act as a reference to a subrange of the array, but we would not call the struct as having reference semantics.

Mixing by-ref argument passing and reference types could indeed lead to confusion. In particular since reference types can also be passed by reference.

@mairaw mairaw added this to the Sprint 134 (4/9/2018 - 4/27/2018) milestone Mar 26, 2018

@BillWagner BillWagner modified the milestones: Sprint 134 (4/7/2018 - 4/27/2018), Sprint 137 (June 11 - June 29) May 21, 2018

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