object allocations in golang

A Tale of two memories

We as programmers are aware that every program is associated with two kinds of memories

1. Stack Memory - Gets allocated upon each function call and gets reclaimed when the same function returns. This memory is generally contiguous blocks. Generally the stack-memory occupies less space when compared to that of heap memory, if the amount of memory allocated gets filled completely we are bound to get the very famous StackOverflow error.
2. Heap Memory - Not to be confused with the Heap data structure, this is more like a persistent memory where the data stored on the memory blocks are persistent across function calls(unless explicitly destroyed) and persistent as long as the application to which this block gets allocated is running. This kind of memory is usually considered unsafe because in the absence of the mischievous Garbage Collector if the programmer forgets to de-allocate/destroy objects which are created on this memory segment, we are bound to have memory leaks. Sometimes this part of the memory is divided into young, old/tenured, permanent generations. If this memory gets filled completely we are bound to get OutOfMemory error.

As far as goLang is concerned, each go-routine or function call is going to have a dedicated stack memory associated with it. This stack memory is called stack-frame alongside this we also have the heap memory

How do we know if my variable lives on the stack or on the heap

The answer is basically We don’t know, but does it really matter?

1. It does not matter as far as the correctness of the program is concerned. Irrespective of where the object gets allocated goLang is going to make sure that the program which we are trying to run is going to behave correctly as we expect it to be.
2. It does affect the performance of our program, because as we all know goLang is a garbage collected language i.e, it comes with a famous and mischievous garbage collector who’s going to manage the objects on the Heap. Even though the garbage collector is good, collecting garbage(objects not garbage i mean 😛) is going to require some CPU cycles which is going to add latency to the application runtime. While this might not be a problem for most of the programs out there, for performance sensitive applications like those which run at HFTs this is a huge problem.

So the answer to this questions goes like this

1. If our programs are already Fast enough then we never need to bother
2. If we have benchmark tests which prove that our programs are not running as fast as we want it to be.
3. If these benchmark tests resulted in excessive heap allocations in the program

If and only if all of the above points are true, we should look into how allocations are done in our programs. We should always be optimizing for correctness rather than performance. As my architect’s saying goes Do not optimize prematurely 😛

Let’s look at how allocations happen with some examples

Case 1 - Simple Square

func main(){
    n := 4
    n2 := square(n)
    fmt.Println(n2)
}

func square(n int) int {
    return n * n
}

Let’s walk through the above program in a step-debugger fashion, what we have here is a program which is declaring a variable n with an initial value 4 there after we are declaring another variable n2 which is getting assigned to the return value of the square function which is getting n as the program argument.

As we can see in the stack transition diagram above, Initially main starts with a stack frame for itself with two variables n and n2. Alongside this goLang also has a pointer which it uses to identify the point in memory up to which the memory block is valid(this is denoted by the dotted line in the stack memory block above).

Once square gets invoked it also gets a stack frame allocated for itself, and the stack frame contains a variable n which is the function’s parameter with a value of 4.

After the function square returns variable n2 in main gets assigned a value of 16, also notice that the valid memory marker moves above the stack frame of function square denoting that the stack-frame of square has become invalid.

In the next instruction, Println gets called with n2 as the argument and because of this another stack-frame gets allocated for Println, but this time on the same location as that of the stack-frame of square, i.e goLang is going to reuse the same space for allocating multiple stack frames once they are marked as invalid. Notice the valid memory marker now.

This is how the stack memory transitions for the above sample program, also note that the heap was never invoked.

Case 2 - Program with pointers

func main(){
    n := 4
    decr(&n)
    fmt.Println(n)
}

func decr(x *int) {
    *x -= 1
}

The program starts with a stack-frame for main with a variable n and an initial value of 4, another thing to notice is the address of the location at which n lives 0x234jkljlkac. Upon execution of the next instruction, another stack-frame for function decr gets created, this time decr is going to have a variable called x which is a pointer to type integer, x holds the address of the variable n in function main. This decr function is basically de-referencing the value of n and decrementing it. Since all of this is happening on the pointer variable, after the decr function returns the value of n as seen by main is going to be 3 The next instruction is going to result in another stack frame for println, as with the first case the stack frame is going to be allocated in the same place as that of the stack frame for decr Even in the presence of pointers, we saw that heap memory never came into picture. Which brings us to the major lesson,

Sharing down typically stays on the stack.

Case 3 - Returning pointers

func main(){
    n := answer()
    fmt.Println(*n/2)
}

func answer() *int{
    x := 42
    return &x
}

Let’s assume that the allocation proceeds as per the same algorithm, main starts with a stack-frame with one variable n initially set to nil function answer gets invoked which results in a stack-frame with a variable named x and value 42 sitting at address 0xasdfghi. Soon after answer returns we are left with n in main’s stack-frame pointing to an address which is marked as invalid. This is going to cause problems because, the runtime is going to reuse the invalid segment to allocate stack frames for other functions. Assuming that println is going to be allocated with a stack frame at 0xasdfghi the value for x is going to be corrected.

Turns out that this is not what happens under the hood, rather the mechanism is as follows

As seen in the above diagram, soon after the goLang compiler sees that answer gets invoked the value x being reused, it smartly marks it to be allocated on the heap memory rather than allocating it in the stack frame. There fore even if the stack-frame of answer becomes invalid and gets over written with stack frame of println the value of x is safe since its allocated in a different location.

Problem solved? Now, you might be thinking if the value of x on the heap is not going to be overwritten, who’s going to reclaim it? Well, that’s where our garbage collector friend’s role comes into picture, if the variable’s reference counter(number of variables which are referring to this variable) which is on the heap becomes zero of goes out of scope, the garbage collector is going to reclaim this space. This does not mean that it’ll be de-fragmented, what happens is that if there are future allocations which can be fit into the space occupied by this freed variable, it’ll be allocated in this freed variable’s space.

We say that x escapes to the heap, thus Sharing up(returning pointers/references), typically escapes to the heap

This typically is there because, only the goLang compiler knows where each object’s allocation is going to happen.

From the goLang’s FAQ section

1. When possible, the Go compilers will allocate variables that are local to a function in that function’s stack frame
2. However, if the compiler cannot prove that the variable is not referenced after the function returns, then the compiler must allocate the variable on the garbage-collected heap to avoid dangling pointer errors.

This cannot prove thing is the same problem as we saw in sharing up case.

How to ask the compiler

1. Compiler flags - go build command has a flag called -gcflags which is passed to go tool compile command, which results in go build -gcflags “-m”

If we run our program with these flags, we get

So to summarize, when are values constructed on the heap?

1. When a value could possibly be referenced after the function that constructed the value returns.
2. When the compiler determines a value is too large to fit on the stack.
3. When the compiler does not know the size of the value at compile time(Example: A slice whose size is not deterministic at compile time)

Some commonly allocated values

1. Values shared with Pointers
2. Variables stored in Interface variables
3. Function literal variables and variables captured by a closure
4. Backing data for Maps, channels, Slices and Strings

An example exercise - Which stays on the stack ?

First

func main(){
    b := read()
    // use b and do something
}


func read() []byte {
    // return a new slice.
    b := make([]byte, 32)
    return b
}

Second

func main(){
    b := make([]byte, 32)
    read(b)
}

func read(b []byte) {
    // write into the slice
}

Both of the above cases do the same thing as far as the correctness is concerned. In case 1 we create the slice in the read function and then use it in main, where as in case 2, we create the slice in main and pass it down to read to read data into it.

From our learning in this case, we can see that in case 2 there’ll not be any heap allocations where as in case 1 every-time function read gets called there’s going to be an allocation on the heap(we also saw why allocations on heap is considered inefficient right?)