Stack Memory

[00:00:00]
>> So just a quick recap of what we talked about two sections ago with regards to memory. So we have all these bits in memory, we can choose to interpret those bits as bytes, which is to say groups of eight 1's and 0's. So these eight 1's and 0's happened to be the number 243.

[00:00:15]
Here's another group of eight 1's and 0's and those correspond to 107. And so on and so forth. And for most of the time, we're talking here we're just gonna be thinking about it as bytes, but while still remembering that the bits in there are representative of this, this is just a way of interpreting these 1's and 0's.

[00:00:32]
Okay, but now we're gonna get a little bit more specific and talk about the stack versus the heap. So basically, we've been talking about how all memory can be thought of as like one big long continuous piece of 1's and 0's. And that is a useful mental model.

[00:00:47]
But in practice, basically every process divides that up into a couple of different regions, one of which is the stack, and another which is the heap. So let's talk about like why those are divided. Why would you ever like want to divide up your memory into these two different regions like what would be the purpose of that?

[00:01:03]
So we'll talk through that. So we're gonna start with the stack. And basically the stack is a way of dealing with function calls. It's a way of passing memory between functions. So we're gonna have this sort of, we'll pretend it's a global variable called stack length. I know global variables have a bad reputation, but let's just go with it for now.

[00:01:22]
And it's called stack length. And right now the stack is quote on quote, empty, which is to say, we have these like memory cells, these are gonna be bytes, but nothing's in them right now. There's no information of any importance in them so far. Okay, and now I'm gonna define a couple of functions that we're gonna use an example.

[00:01:39]
So one's gonna be called increment decrement. It takes a number and then it calls a function called print_nums passing num +1 and num -1, hence, increment and decrement. The print_num function just takes an x and y and as you would expect, prints them both out. And then finally we're gonna have a function call, we're going to invoke increment decrement 42.

[00:02:00]
So we haven't really talked about this before, but there's some memory traffic going on here. Like we're passing these numbers between these different functions. So what's actually going on there in terms of memory, when the computer runs this code? That's exactly what we're about to talk about. So let's just step through what happens when I call increment decrement passing 42 and then increment decrement in turn calls print_nums, passing 42 plus one and then 42 minus one, and then print_nums runs.

[00:02:23]
Let's see what happens in terms of just specifically the memory involved. Okay, so at first before we call the function, our stack is empty. There's no memory in any of these cells. Okay, let's start with just our first call to increment_decrement (42). So what happens is we come along, the program is running along it sees this instruction, says hey calling from executive and passing 42.

[00:02:45]
So it says okay, I wanna put that 42 onto the stack, which basically means I want to take this sort of conceptual array of bytes and I wanna fill the first one with 42. Why the first one? Well, because our stack length was previously zero. So it says, okay, well, I mean, since it's zero, I know that I can just overwrite what's in the cell.

[00:03:05]
And it's going to be no problem because they're like the zero, there's nothing in the stack. So I'll just write it right in there. Great, so now I have a 42 on there. Next thing that happens is the program moves on and says, okay, you told me to call increment_decrement.

[00:03:15]
I've got this 42 hanging out of the stacks not really doing anything, but it's just hanging out there. Now we're gonna run this increment_decrement function. So, increment_decrement, when it gets inside of there, the way that it knows where it's argument is, is it actually pulls it out of memory like this.

[00:03:31]
It says I wanna take stack length minus one. So in this case, our stack length is one, so stack length minus one is zero. And I wanna get the memory that's at that address. So in other words, slot zero because stack length minus one is zero, slot zero and stack bytes, that's what my number is.

[00:03:48]
And this works no matter how many other functions have been called. It's basically saying like the most recent thing that was put onto the stack, even if there's like a bazillion things in this stack right here, that's what I want to be my num argument. It says, okay, cool, now I know what num is.

[00:04:02]
It's this thing right here. And then it can proceed on to its print _nums and says, okay, I've got 42 and I'm gonna say 42 plus one is 43. And then 42 minus one is 41. And now it's going to call print _nums. So what does it do to call print _nums?

[00:04:19]
We follow the exact same procedure. Except this time we're gonna do it twice because print_nums takes two arguments. So first we're gonna say num + 1, we're gonna put that on the stack. So now our stack length is 2 and there's a 43 on there. The 42 is still hanging out from before, we haven't gotten rid of that yet.

[00:04:33]
And then we're gonna do 42 minus one is 41. And then put that on the stack. So, basically this first argument gonna go to stack length of 2, put the 43 there. And then this one is gonna evaluate to 41, we're gonna put that on the stack. Now we have a stack length of 3.

[00:04:48]
Then the program says, okay, now it's time to jump over and start executing print_nums. How do we do that? How do we know what these two arguments are? Well, again, it's gonna be the same kind of algorithm as before. Although the first one in this case is gonna be stack length -2, because this has two arguments.

[00:05:03]
And the second one is gonna be stack length -1. So this first argument, it says, okay, whatever our stack length is, go back two and that's my first argument. So this case the 43. And then this says go back one, and that in this case is gonna be the 41.

[00:05:17]
Now notice that even if the stack were empty, and we had called this thing from scratch, this would still work and give us the right answer. Like if that 42 went there, that'd be no problem because our stack length would be 2 and 2 minus 2 is 0.

[00:05:29]
So this would be our first argument. And this would be our second argument. And likewise it would also work just as well if we add a whole bunch of things here instead of just this one 42. So this is pretty much exactly what's actually going on when you do a normal function call on a computer.

[00:05:45]
It's using this concept of stack memory and this one global counter, that's like how big is my stack to figure out where to write things and then when you call the functions, they know where to look in memory based on these offsets of their arguments. And you can imagine if there were third argument here, this would be stack_length minus three, this would be minus two, and the third argument would be minus one.

[00:06:07]
Okay, so print_nums is finished as we've printed the numbers back out to the screen. And now when we go back where the program jumps back down to here, it says, hey, we saw that this 43 and 41 hanging out of the stack but, nobody's really using those anymore.

[00:06:21]
So now, we can say you know what, I don't need to like zero those out or anything, I'm just gonna reduce my stack link from three down to one and just say, yeah, there's only one thing on the stack right now. But the memory that we wrote into there, the 43 that we wrote it to here, and the 41 of you wrote it there, that's still what the ones and zeros are, like that memory is unchanged.

[00:06:39]
We didn't go through and turn them all into zero, we just sort of marked them as unused by reducing this stack length counter. Which means that later if we go on and call another function, that other function when it puts its arguments on the stack, it's gonna happily overwrite these things.

[00:06:53]
Because all of our logic has been based around the stack length, and everything's still gonna work. But, again, interesting to note that these things are still sort of, like hanging out, they're written into memory, we're just not using them anymore. And the way that we fly that we're not using them anymore is just by changing the stack length.

[00:07:10]
Okay, so we're done calling print numbers, we're back down here. Now increment_decrement is done, it's gonna return. And once again, we're gonna do exactly the same thing. We're not gonna bother erasing this 42, we're just gonna say, well, we're done calling a function. So we're gonna take the stack length all the way back to zero.

[00:07:25]
So this is sorta what actually happens in the computer, when we are running a function call like this. First we push some things onto the stack. The functions use those things on the stack to read their arguments. And then once the functions exit, we don't go and override anything.

[00:07:38]
We just keep decreasing the stack length back down until we get all the way back down to zero. And then we're back at the top and we've finished executing our program. And the stack is now empty once again. Okay, so you can imagine that actually, if we think about how like memory like really works in practice, there's generally all sorts of garbage in here.

[00:07:59]
I mean like these bytes they're not all zeros, [LAUGH] necessarily. There's potentially all sorts of like random numbers from previous function calls just hanging out there. And as long as we're managing our stack length properly, or rather our compiled program is managing the cycling's properly, it doesn't really matter, we're never gonna actually see any of those bytes.

[00:08:17]
They're never gonna sort of interfere with our program. The fact that there is garbage in there, if everything's working properly, it's not really gonna affect us in any way. Okay, so now let's say I wanted to, instead of calling increment decrement passing 11 instead of 42, like let's say I finished running this code and now I want to call it passing 11 instead of 42, real quick, we can kind of go through the example again.

[00:08:40]
So now we're gonna overwrite that 42 with an 11. We're gonna jump up in here. Now, stack bytes of stack length minus one is once again, going to refer to the first slot. Except this time it happens to be an 11 instead of a 42. I'm gonna jump in here, bump up the cycling for 3.

[00:08:54]
This time it's gonna be 12 and 10 instead of 43 and 41, because that's what 11 plus one, 11 minus one are. Then we come in here again, stack bytes of stack length minus 2 is gonna be the same thing. 12 and then 10 for this one. And once we go all the way back down to the second is all the way back to zero except that the memory is now written into these cells instead of what it was before.

[00:09:16]
Okay, so that's passing function arguments on the stack. But what if I wanna return something? What if I have this function called double_and_return which takes a number and then returns that number multiplied by two, and then I call that function double_and_return(30). How does that work with the stack?

[00:09:32]
Well, basically, it works pretty similar to how we had things before, with one exception, which is that basically before we, sorry, when we put the arguments on the stack here, would actually leave space for a return value. We're gonna leave one extra byte here because this returns to u8.

[00:09:47]
And we're gonna say that you ate, we're gonna leave a little landing pad for it here. So, we're gonna put this 30 on the stack and we're gonna put it in the second slot and leave the first slot reserved. So we're basically gonna bump the stack length up to two.

[00:09:59]
Again, we're not gonna bother clearing out that thing. We're just gonna sort of reserve it and hold it and say, you know what, that's sort of reserved for our return value in the future when we know we're gonna end up needing one. So, then we call the function and we say, okay, how do I get my argument out of here stack bytes of stack length minus one.

[00:10:16]
Once again, stack length is two, so two minus one is one. So it's gonna look in slot one, which is gonna be this 30 right here. And so it's got its argument multiplies it by two. And then when it returns it, what the return is actually doing is saying, use that reserved slot that we had previously, and store the return value in there.

[00:10:35]
So 30 times two is 60. So 60 now we finally populated that first value of the stack. And now when we come back in here, this is okay, we're done with that so we can decrease the stack length back down to 1, because we no longer need this argument on the stack cuz the function is done.

[00:10:50]
And now we're left with the stack length of 1 and quite happily, a return value in it. And so now we can say let x equals and then x can be assigned to 60. And then we can proceed with our program as normal. Well, let's take this one step further and say, we're gonna do exactly same thing before I said now we're gonna say doubled twice.

[00:11:07]
And we're gonna say same argument of one thing, but now we're returning a tuple of two units. Okay, no big deal, returns num times two and num times two. And this time we'll say, let (x,y) = double_twice(30). So same exact example as the previous step, except this time we're giving it two, or sorry, we're returning two u8 instead of one.

[00:11:26]
So no big deal. We reserve two slots instead of one, everything else is basically the same as before. And we could also take this one step further and say double thrice. We wanna have return three u8. Again, no problem, just reserve three slots for the return value, and everything else works exactly the same way as before.

[00:11:45]
And if we wanted to, we could instead of using a tuple there, we could say an array. And as we talked about previously, arrays and tuples have exactly the same memory representation, so no big deal there. This will once again work just reserve three slots for the return value.

[00:12:00]
What about this? What if I wanna actually return a Vec of u8's, how many slots do we reserve? I don't know, one, two, three, a billion? We kind of can't know how many slots to return to reserve ahead of time when we're trying to call the function because we won't know how big the Vec is until the function is actually done running.

[00:12:23]
So we've got a bit of a chicken and egg problem here where we wanna figure out how much space to reserve for that return value before we call the function. But until we've actually run the function, we don't know how big the return value needs to be. We don't know how big that Vec is.

[00:12:39]
So remember when I said earlier that this gets into one of the biggest areas of performance, one of the biggest differences between Vec and u8. This is actually a really serious problem, is that we can't just use the basic stack mechanism for passing these things around in order to return a vector of a function.

[00:12:58]
This seemingly simple thing, actually, when you get down to like how the computer is working in order to pass things around in memory, this is actually a really serious problem for it. So, I mean, yeah, potentially we could reserve like [LAUGH] an indefinitely large amount of memory for this Vec just in case it was like a billion items long.

[00:13:16]
But of course that doesn't scale very well what if we have multiple function calls and they're all returning Vec, we're just gonna return like a reserved a billion bytes for each of them? Not really gonna work. So really this kind of generalizes to a rule which is in order to have something be returned directly, the size must be known at compile time if we want to return it on the stack.

[00:13:39]
This is just a truism, like in rust and in any language if you want to return something on the stack the entire value on the stack, it has to be possible to know that size at compile time. Okay, well, so what actually can we return on the stack instead of this entire Vec.

[00:13:57]
So this is basically what Russ does. When it actually returns this Vec, like if I write this function out, it's not actually going to return all of the u8 elements inside that Vec on the stack, instead, what it's gonna return is something that does have a fixed size.

[00:14:13]
In fact, it's a struct. I'm gonna call it Vec metadata. It actually has a different name if you read the Russ source code, but this is the basic idea. It's a struct that has three fields in it. The first element index set is to say the index into memory like as in our actual conceptual array of bytes.

[00:14:32]
Each of those has an index that we've been storing things into. It's gonna write that down and say what's the index of the first element in this Vec. And that's gonna have the type usize. Also what's the length of this back? In other words, how many total elements are there?

[00:14:46]
And finally, capacity. We'll get into capacity a little bit later. But let's first start by looking at the first element index and the length. So first of all, this struct does have a size that is known at compile time. That's three usizes. I know exactly how much those are.

[00:15:02]
If it's a 64 bit system, each of those are eight bytes. If it's a 32 bit system, each of those are four bytes. And I know what compile time, which system I'm compiling for. So no problem, all set. Of course the problem is that this is just an index into some memory and a length, but it's not actually giving me the actual bytes themselves.

[00:15:19]
So where do the actual elements in that Vec go? Well, the short answer is they go on the heap.