Stack/Heap Allocation, Frames, Call Stacks, Recursion - Computer Stuff They Didn't Teach You #12

Hi guys, I'm Scott Hanselman, this could actually be

computer

science

stuff

that

they

taught you in school or at least should have, or maybe

they

taught you in school but did it wrong either way, it's still something that many people are confused about let me switch to here. We had a new friend tweet me today and say, Hey, do you know any good video material that explains recursive

stack

allocation

and

stack

overflow? No, I can do one and I thought I'd add it to my list and maybe do it at the end of this month, but then 200 people liked it, but then the stress builds up, so I have to do it the night before I go to bed or whatever.

I will do. I lose my motivation, so let's talk about it. There are a couple of things going on here, a lot of good questions there, which is why the word stack gets used a lot. Let's think about there being stack as in data structure, like if you put something into a stack data structure, okay? and we'll talk about that, then there's stack

allocation

, allocating something on the stack, the stack is like memory allocation, okay and then there's the stack frame on top of the stack frame, the concept of

call

stack, we'll talk about that a little bit and then there's

recursion

and then sometimes the resulting stack overflow, so the word stack here appears several times and each time you build on top of it, there's the generic concept stack as a data structure, memory is allocated in the memory stack and there are

stacks

as you progress in executing an application and then the stack gets ruined when you have a stack overflow, so let's see how long it will take us in a single It takes understanding this.

Now I'm going to consider this 100 level or Early Start of School level Explanation, one could do an entire class on this

stuff

and delve into the details. I'll go into the details a little bit, but what I want to give you is an understanding of these terms, to the best of my ability. knowledge and then allowing you to go out and search the web for the little details you want. I think these things come up a lot in interview questions and people think they need to know everything when a new

computer

science concept comes up. the need to know that you need to know that it is good to know that is where you start to get into the edge cases or trivia everything you need to know you need to know that a stack is a thing that exists edge cases of

stacks

and what they are

call

ed call

recursion

finals that I'll address at the end, people may argue that you should know that or that it's good to know, but honestly, if your job is placing text boxes over data, those are things that would be nice to be able to Google. you don't need to know everything, so pick the level you want to know, maybe it's here, maybe it's down here, maybe you write compilers for a living and you need to know them, but don't feel like you need to know everything. just to be a programmer, okay, first data structures, let's talk about the stack as a data structure.

I made a little happy stack right here, let me zoom in just a little bit, we'll talk about this and what I'm actually going to do. Am I going to put a giveaway next to it too? Let's say we have a stack. Do you know what's a better way to think about a stack? You draw a box. I could do it in a second, but actually let me. grab a stack of things let's say I'm reading a book this is a book I have a stack of books on my desk so I'm going to go and I'm going to grab another book and I'm going to push this book on top of the stack and then I'm going to grab another book and I'm going to place it on top of this platform and another book, another book, so now I have a stack of books, I want to get to this book here.

I can't access this it's not a series of books it's a stack of books I want to get to these books it's last in first out so hop hop pop now I'm getting down to the stack there's something behind push something back or something again in push and pop which is a stack, the data structure, so come back here the same idea, take something, push it on the stack, pop it off the stack, push it on the stack, let's do it with the code, let's move this here . let's think about our stack this way, let's make sure it's visible, so I'm going to make a stack of strings, call it happy stack and then I made a dump function, this function is called dump. right click on that in Visual Studio here and say go to definition and all my dump is going to do is draw some lines and then say what's on the stack and then dump each of them and loop. over the stack and then print everything that's in that stack now in this case I did it the old fashioned way in C sharp now let's go like this there we're going to put a little bit of space a little bit of extra space there we're going to throw away our stack we're going to list our stack now, just like I pressed books, I'm going to press hello, press world, I'm going to press exclamation point and then we're going to take a look at our stack, we're going to say Hey, how many items are in our stack?

I'm going to throw them away, then I'll pull one thing off the top of the pile and look at it again. We'll do that once first and then we'll look. a little faster, okay, we said hello world, exclamation point, in that order we have three items in our stack and we look at the order backwards, the last hello came first, I'm going to take the last thing off the stack, which was the sign exclamation mark and now it's gone, but now the stack has two things right, now in Visual Studio I can put a breakpoint and I can press F5 or I can press the play button, a debug button, start the debugger, a bunch of things will happen things in Windows. will change, you'll see here in our viewport, here we have a happy stack with nothing in it right now, I'm going to press f n, which means hover, that's this button here, hover, I'm going to move to the next line we haven't put anything in our stack yet now let's press hello oh an item appeared in our stack press in the world look hello move down hello move down again okay, now let's pop it's going to appear, there's the top of our book stack, our string stack, in this case, now it's gone there, it's thrown away, okay, it's a stack as a data type like a data structure, so if we remember the behavior of a stack which is last in first out or lifo lifo last in first out, so that can help us when we think about memory stacks, think about stack

frames

and other types of stacks, so that was our first example of stacks as the data structure we use.

I talked here great, let's check it out great thanks now let's look at it in the context of memory here I just made a little main application, a little main application that we say and actually you know what I'm going to do, I'm going to just Move up here, I'll live here for now, there you go, that's good, so I have some numbers, I'll add them up. Everyone lives within the reach of these two keys. Some people think they look like mustaches. but I don't believe it and then I have a person, I have cancelman and then I'll go ahead and generate that person, so I made a couple of variables here and I made a variable there, these variables here live within this scope, this one also lives within this scope, okay, but this is allocated on what's called the

heap

, if we come back here we think about our execution of our main, let's say this is our main here, all right, here it is. our main, so we're doing some stuff there, we made our variable a b and c on the stack and then it looks like we made a person object that will be on a

heap

and a heap of memory is somewhere else, maybe I'll have the people here.

You could have a series of people or a stack of people. I could have a lot of things here in the pile. Now, this main here we call it main, but that could just be a thread that we. I'm doing, let's say I had a couple of threads, one red and one thread two, extended thread three, each one has its own stack, they have their own area, their own scope, they can all use the memory that is on that stack, so which means the value of a b and c can be different in each thread here we could have a is zero because it is doing one thing here we could have a is 99 50 40 42 we don't know but the person in the heap is the same person if he has a reference to this can be a little hard to visualize a little confusing visualizing these things right here let's try this first we'll just run this and I like to run things with a breakpoint so what I'm going to do is I'm going to put that here and then I'll do this.

My little trick. Start running our application. I'm going to take my application here. I'm going to stick it to the side and then we're just going to take our divider, okay, so our applications here on the left, there, we're sitting here running our application on line nine and I'm just going to put my finger on the f n button. that again press this button here. kind of hidden step I'm going to step by step step by step look down here in our observation window and nothing really interesting has happened our person is null because we haven't created a person yet okay we haven't printed anything Over here yet neither and then there's this thing you get in Visual Studio.

I'm going to get out of the way here, of course, put me here. There's a thing you get in Visual Studio called diagnostic tools. There is a section here called. memory usage and it allows you to take a snapshot, you take a photo of your memory, let's do that, let's take a photo of our memory, okay, so I'm going to go and press f10, now we have a person who sees our person down here , my age first. and lastly, and then I'm going to take another snapshot, so now I took a souvenir photo twice before and after doing my person, we come back here and remind ourselves of this situation that we have, okay. our heap our memory heap with our person on it and we have our thread in this case the only thread we really have is the main function I don't have any thread let's put this on a heap I have a nice stack of books i I have a lot of stacks of books, individual piles that I'm working on individually, pushing and placing things on my list.

I have my personal improvement books. I have my science fiction books. I have my language books, but also. I have a bunch of old books that I'm dealing with, sometimes it gets fragmented, it gets a little messy, but for the most part I just throw books into what we can do here, I can say, hey, let me see. this heap, take a look at what is happening here and I can tell what is all the memory, some of this memory is something else because my application runs different things, but remember we have a person so I want to write in person and I can say look in my pile of stuff, my pile of memory stuff, I see there's a person, he's 40 bytes in size, that's cool, click on that, let's see if there's a graph of what size he is, where he lives, what?

Does anyone else care about this thing? I can see that it is a local variable and only one person, one place, one thing has a reference in our application. Let's change this to make it a little more interesting. Come back here and let's make our application more complicated, so here generate a person we said hello cool, I'm going to add another one, so I'm going to generate it before and after, so here we're going to go and do something cool, we'll move on to our person p, It's okay, I've done it. I haven't done anything interesting yet, so I get a little scribbled like it's not spelled correctly, but it just tells me there's no person here.

I'm going to hit checkpoint and something will pop up that says generate method. is going to go and write it, do something cool for me, look, that's fun and our doing something cool requires a person, so inside that I'm going to say person dot age plus plus, I'm just going to go and increase the age of that person, that person is me and then I'll check it, okay, let's do that, let's put a breakpoint there, press f5, bounce, bounce, bounce, bounce, oops, go ahead and put that there again, now let's bounce, let's bounce , okay, there's my age. and I'm going to say do something interesting now instead of hovering over it, I want to get into that, so I'm going to press f11 and that's going to let me zoom in here.

I'm going to go in instead of Hovering over these buttons is getting a little tricky because of the way I have my toolbars set up and I apologize for that but f10 and f11 are what you need to remember so I'm going to press f11 now that I'm there. You look at my instructions prompts telling me that this is the next thing that will be executed, right now, here is our person, there is the age, now we are going to go over it, we are going to age, also, remember that the person lives in the pile. and right now it exists here, so I passed it a reference.

I gave someone a pointer, not a real pointer like c or c plus plus, but a reference, it's an easier pointer, let's say age plus plus, we see. now it's 100. here's the question: did I change the age of the person everywhere or just the person who lives here, let's figure out that we're going to get out on the next line and look, we change the only person we saw that in the lot? in the big pile of memories there is a person and we change that number for everyone or anyone who cares about that person that age just increased okay now here we had thisnumber basket list is long, let's change, let's do something interesting and we're going to pass a person on the heap and this number c that is on the stack push on the stack push on the stack push on the stack the stack only lives within the context of this method is fine and it keeps it there, what we're going to do is we're going to go down here, we're going to change our method so that it can pass it and then I'm going to say a plus plus Aha, it's not actually c plus plus, but it's still fine and then instead of console.writeline, this will be console.writeline c, that's what we care about, so we'll change c and then come back. and we're going to see before and we're going to do something interesting and then we're going to see after, okay, let's do that, okay, let's look down here, we can see that d is 99, we see that c is 99, now I'm going to go and say f10 and now notice that we have a person here who is 99 and we have the number c which is 99.

Now we'll talk about call stacks in a moment, but it's worth noting that we're currently in the main application, main function uh it's going to be f11 okay, now we're going to go and say c plus plus look at our c right here okay and we change our age now here's our stack our call stack we were in main now let's do something cool now let's go out, do something interesting, we'll go back to main, let's see what it is c. c is 99. not 100. but our person's age is still 100. that's because c we changed the number c the variable c what we changed was passed to this method by value, we gave it a copy of the number 99, we took that number 99, now we had two, it lived only on the stack inside that method, we changed only that number and then that number disappeared. we pushed all those variables on the stack, we pushed the parameters on the stack, we did a bunch of stuff and then we popped everything off the stack and now it's gone, we cleaned up after ourselves, but that bigger object, that person object lives on the heap and when you passed it it was passed by reference so these elements lived on the stack within this context and this c is a different c that was passed its value and then we made a little copy there that created the stack here, okay, that's interesting. you can see the way we can test those things using our observation window by being really thoughtful about what we're doing, that's cool, then we talked about stack allocation, since in the context of memory allocation I touched on it a little bit the stack frame.

Dig into that for a second. I have created a small application that says console.writeline and then I have three functions happy little and function and each of those functions returns a string and then I say hello console.writeline call this function and then add to the return value of this function and then add it to the return value of that function so you can imagine what it will look like. I'll hit a breakpoint press f5 okay let's press f10 f5 again starts my app f10 steps above all I'm doing is using the hotkeys that Visual Studio has for me I'll just remind you this is your start f5, you can see it's f5 because it says it right there, my function key five and then here we have a step above which my mouse is in the way a little bit and I have a step back, so come back here f10 little function happy cool, let's do it again, I'm going to say f11 there it's happy there are few functions, okay once again, this time we're going to pay special attention to our call stack, I'm going to say restart, I want you to look here, we're in the main function that we are going to do. something complicated here, I'm going to right click on that, I'm going to say show parameter names and we have the frame state, it shows everything that's happening in the context of our entire stack, this lets you know how deep you go, so Let's press f11, we were in main, now we press on top of that and now our call stack is not happy, we are still in main, you see how we are still there, but we are also here. waiting for this to come back now we're going to come back happy and we removed it and now we returned that c value down here happy it came back happy so we're going to go down again now we're on little there's our call stack look at our watch window, we just came back little, now we are going to return the word function, so what happened there?

We had one main function and then we ran another function and said happy and then we came back and did little and came. Back in Maine we said function, so our call stack never got too deep, let's change this, let's change this and what we're going to do is, instead of saying happy and then bit and then function, let's Let's go and we'll call some different things. I'm going to call a function that I made before called happy and happy and it's going to call little and it's going to pass happy, then little end is going to be added and then it's going to be I'm going to say end of function and then it's going to call the little function and we're going to take the value passed in again and we'll pass the function, so we'll take the string, happy, pass it to bit, we'll add a word and pass it to another. one and add that and we should get exactly the same result, happy little function, but we're going to look at a deeper call stack, let's do that, press f5, set my window up there, okay, we'll see here, start there and we're going to say f11 so now we take our main, we just add happy ending and now we go to f11 again and now we've gone a little bit deeper f11 again, the main is down here, you can see it right there. still waiting for happy and it's still waiting for little n to return little and it's still waiting for the function and to return here we can see what it's waiting for we're going to go on f11 f11 we see that the end result is happy little function and then we're going to make it appear a popup up to here and the result will appear here, happy little function now that's not recursive, it's a slightly deep call stack, each of these functions is called another, it passes things in and I had to wait until the return left it freed, but then the call stack became a little deep, which gives you an idea of ​​the stack

frames

and call statistics.

Now finally, recursion isn't that fun. Take a look at this. Let's resort. We get into some trouble. and we are going to have a stack overflow here, we are going to take a number that is a million, this is a classic example, we have a main and the main will call the countdown and then the whole countdown will be done. to say hey, if 0 is greater than and then you will take the number n and subtract 1 from it. then this million will become 999,999, then you will call yourself, I will call myself, so you will need to call yourself a million of times, set f5 and actually let's just turn off the breakpoint, let it run because I don't want to go and hit my button a million times.

Do I stack the overflow? It looks like it did it about 19,000 times and then gave up and we had a stack overflow, that's cool, oh I have a little exception here and a little popup and a whole mess of overflow again, what does that mean? Look at our memory, give up, okay, find out what's going on. Let's put a breakpoint here, let's press F5 and I want you to look at that call stack. Oops, I'm going to get out of the way, here we go, F11, okay, now we'll call ourselves, look at that number. I'm just going to add that here in the observation window, if we see it go down, I'm just going to go to f11 f11 11.

I'm going to make myself a little bit smaller, maybe go up here, look at our number. we're just going to hold down f11 so what we're doing is we're going deeper and deeper look at this here look at that look at that scroll bar what's happening is we're making a stack here of functions while we wait like each function waits for that the network finishes last and it can't unwind and pop everything out of that stack because it is waiting and will never finish the queue, the end of all this will only happen there, notice that the countdown method only has one exit, the only exit is when the number zero is greater than the result of that n, so when we get to a negative one, it will return and then this kind of already ridiculous call stack will be undone and gone completely. a long time ago, then what is happening is that we are overflowing our stack because programs have a limited amount of stack space: their heap is as large as their processor architecture allows. 32 bit processes have a certain heap size and 64 bit processes have a certain heap size, but your stack is fixed again, a little different for 32 bit and 64 bit, you can google that, but in this point we have to ask ourselves two things and this is where we advance a little and I.

I'm going to let you go and Google that because this is about educating yourself, not me making 400 level videos. One was this, the correct architecture to do this work was recursive, good idea, spoiler alert, there is no second question, maybe it was from the compiler. work that realized that saw it coming and automatically turned it into something a little different, for example, what if we changed this countdown and made a better countdown? Let's say this one is bad, a better countdown could look like this and pass our initial value, that better countdown would just say well as long as it can forever until it's done now, in fact this is not ideal, this code is here , but that's what the compiler would generate.

There are many different ways to move forward. that for loop for each wow doesn't matter, the point is the instructions we had before being recursive, we go deeper and deeper into our methods waiting for the tail end of that, while this does it without any stack when I run this on actually ends because there is no stack, we can show that during our breakpoint by pressing f5 we call that method once and then spend all our time in this method. You'll see that our call stack down here is very simple, so that should give you an idea of ​​x as a data structure, stack allocation versus stack allocation concept of a stack frame or call stack and then a little bit about recursion and then results in a stack overflow, something to keep in mind is that some languages ​​like c sharp in different cases may or may not have what is called tail call optimization that can handle tail call recursion and , in theory, you could take that and do better to solve it, do the right thing.

There is a language called f Sharp that does that automatically. Every language is different uh c-sharp doesn't do that, although it could possibly be somewhat advanced, you might want to educate yourself on that, but over the course of an average day you generally won't accomplish these things unless you're doing something. Pretty interesting computational work or if you're building an architecture that relies on recursion, like you're doing a Fibonacci sequence or some advanced math, but there's usually always a way to do it without using as much stack and do it that way imperatively. That's interesting, cool, thank you very much for watching this.

It seems like how many minutes, 36 minutes, sorry it was so long. I hope you enjoyed it and the best you can do to help me as I'm having it all. One kind of fun with this YouTube is to tell your friends. I would also like to tell you that I made a silly domain or this that will take you directly to the playlist, so if you go and use computer things that they

didn

't

teach

you. You dot com will just redirect to this playlist so tell your friends to subscribe and keep sending me your questions and I'll keep making videos, thanks.