Stack implementation details - part two

Several people asked me, in the context of my previous post about meaningful types, why do important types are located on the stack, but there are no reference types.



In short, "because they can." And since a stack of “cheap” we place them on the stack whenever possible.



The long answer is ... long.



To begin with, we define in general terms what we call a heap and what a stack. First a bunch.

')

The CLR pile * is an engineering marvel with a huge amount of detail. The description below is not how the heap actually works, but it is enough to get a general idea.



The idea is that there are large blocks of memory allocated for instances of reference types. These memory blocks may have “holes” because some memory blocks are occupied by “live” objects, and some are ready for use for new objects. In the ideal case, we would like the entire occupied memory to be located in one place as a continuous block, and the rest of the address space would be free.



In such a situation, when allocating a new portion of memory, we would move the pointer to the upper limit of the occupied memory up by the required amount and “eat off” some of the previously free memory. This newly reserved memory would be used for the newly created object. Such an operation is extremely cheap: just move the pointer and fill with a piece of memory with zeros if necessary.



If we have “holes”, then we must keep a “free sheet” - a list of free sections. Then we can search in this list for free space of suitable size and fill it. This operation is a bit more expensive because the list is searched. I would like to avoid this situation because it is not optimal.



Garbage collection occurs in 3 stages: markup, assembly and compression **. In the “markup” phase, we assume that all objects are “dead” (unreachable from ruts). The CLR knows which of the objects are guaranteed to be alive at the start of the assembly and marks them alive. All objects to which they refer are also marked as live, etc. until the entire transitive closure of living objects is marked. In the assembly phase, all “dead” objects turn into “holes”. In the compression phase, the blocks are reorganized in such a way that living objects constitute a continuous memory block without holes.



The described model is complicated by the fact that there are three such areas: the CLR collector implements the generations. First, the objects are in a heap with a “short lifetime”. If they survive *** then over time they are transferred to a heap with an average lifetime, and if there they survive long enough, then they are transferred to a heap with a long lifetime. GC very often runs on a heap with a short lifetime and very rarely on a heap with a long lifetime; the idea is to save on constant checking of long-lived objects whether they are still alive or not. But we also want short-lived objects to quickly free up memory. GC has a huge number of precisely aligned policies that provide high performance. They determine the balance between the state when the memory is similar to Swiss cheese and the time spent on the compression phase. Very large objects are stored in a special heap with a completely different compression policy. Etc. etc. I do not know all the details and fortunately I don’t need it. (And of course, I didn’t complicate with details that are not related to this article, such as “linking objects” ****, finalizing, weak links, etc.)



Now compare this to the stack. A stack, like a heap, is a large piece of memory with a pointer to the upper boundary. But what really makes this piece of memory a stack is that the memory at the bottom of the stack always lives longer than the memory at the top of the stack; the stack is strictly ordered. The object that must die first is at the top, the object that must die last is at the bottom. Based on this, we know that the stack will never have holes and it will never need compression. We also know that memory in the stack is always freed from the top and we do not need to maintain the list of free sectors. We know that everything in the stack below is guaranteed to be alive and we don’t need to tag and collect anything.



Allocating memory on the stack is just moving the pointer — exactly as in the best (and fairly typical) case when allocating memory on the heap. But because of all these properties of the stack, freeing memory is also just a pointer movement! And this is exactly where we save a lot of time. I formed the opinion that many people think that the allocation on the stack is cheap, and in the heap - the road. But in fact, it is almost the same operation time, usually. But the process of freeing memory is the very freeing of memory, defragmentation and movement of objects from generation to generation, all together it is a very significant movement of memory blocks in comparison with what we see on the stack.



Obviously, it is better to use a stack than a bunch if you can. But when can you? Only when all the conditions for the stack to work are satisfied. Local variables and parameters of significant types are the “sweetest” cases when all conditions are met. The local data of the calling functions, located at the bottom of the stack, is guaranteed to live longer than the local data, located at the top of the stack of called functions. Local variables of significant types are passed by value, not by reference, this ensures that only a local variable points to a given piece of memory and does not need to calculate anything to determine the lifetime of an object. And there is only one way to pass a reference to a meaningful local variable — it is ref or out, which are passed to functions located higher on the stack. Local variables located below are still alive until the function above the stack returns control, so the lifetime of the objects passed by reference will not change.



Some additions:

The paragraph above explains why we cannot create a field of type ref int. If you could save a reference to an object with a short lifetime inside the field of a long-living object, if it happened, the stack would lose its advantages and the significant types would just become another type of reference types that need garbage collection.



Closures of anonymous functions and closure of blocks of operators, the compiler implements through the fields of hidden classes. Now, I think you understand why it is forbidden to close ref and out variables.



Of course, we did not want to create an ugly and strange rule like "you can use any local variable in the closure, except the parameters of the function passed through ref and out". But since we wanted to use optimization, having values ​​on the stacks, then we had to add such a seemingly strange restriction to the language. This, however, as always, is the art of finding compromises.



By the way, CLR allows to return ref types. Theoretically, you could create a method “ref int Foo () {...}” which returns a reference to an integer variable. If, for some strange reason, we decided to allow this in C #, then we would have to adjust the compiler and check that the returned reference is assigned either to a variable on the heap, or to a variable located in the stack below.



Let's return to our sheep. Local variables are located on the stack because they can. They can because 1 - “normal” local variables have a strictly defined lifetime and 2 - significant types are always copied by value and 3 - you can only store a reference to local variables in any container whose lifetime is greater than the local lifetime. variable. In contrast, the lifetime of reference types is determined by the number of live links, copied by reference, and these links can be stored anywhere. This extra freedom that reference types give you when asking for time for a more complex and expensive garbage collection strategy.



But again, these are implementation details. Using the stack for local variables is just the optimization that the CLR does for you. The main feature of significant types is that objects of such types are copied by value, and not that their memory can be optimized by the execution environment.

(*) From translator: in .net there is also a heap for internal CLR objects, but usually it is not considered, so in this case we mean exactly the heap that is collected by the GC and which stores instances of objects created by the user.

(**) From translator: compression in this context is equivalent to defragmentation

(***) From translator: not collected during garbage collection

(****) From the translator: in the original pinning - objects that the GC does not move in memory. Read more here: msdn.microsoft.com/en-us/library/f58wzh21%28VS.80%29.aspx .