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

hey friends i'm scott hanselman this one might be actually computer stuff that they did teach you in school or at least they should have or perhaps they taught it to you in school but they did it poorly either way it remains something that a lot of people are confused about let me switch over to here we had a new friend tweet me something earlier today and he said hey do you know of any good video material explaining recursion stack allocation and stack overflow that's a lot a lot going on there i said well no i can make one and i thought i would add it to my list and maybe get to it later this month but then 200 people liked it but then the stress is on then i have to do it night before i go to bed or i will lose my motivation so let's talk about that a couple things going on here a lot of good questions there so the word stack gets used a lot let's think about that there's stack as in the data structure like if you put something in a stack data structure okay and we'll talk about that then there's stack allocation allocating something on the stack the stack that's as in memory allocation okay and then there's the stack frame on top of the stack frame the concept of a call stack talk about that a little bit and then there's recursion and then sometimes the resulting stack overflow so the word stack here appears multiple times and each time it kind of builds on top of it there's the generic concept of the stack as a data structure there's allocating memory on the memory stack and there's stacks as you move through the running of an application and then there's blowing the stack when you have a stack overflow so let's see how long it'll take us in one take to get an understanding of this now i'm going to consider this 100 level or early beginning school level explanation one could do an entire class on these things and get all the way down into the details i'll get a little bit into the details but what i want to give you is an understanding of these terms the best of my knowledge and then enable you to go out there and search the web for the the little details that you want i think that these things come up in interview questions a lot and people think they need to know everything when any new computer science concept comes up there's the need to know there's the should know there's the nice to know there's where you start getting into the edge cases or trivia everything that you need to know you should know that a stack is a thing that it exists edge cases of stacks and what they call tail call recursion that i'll touch on at the end people can argue that you should know that or it's nice to know but honestly if your job is putting text boxes over data those are things that it would be nice to be able to google for you don't need to know everything about everything so pick the level that 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 these but don't feel like you need to know everything just to be a a programmer okay all right first data structures let's talk about the stack as a data structure i made a happy little stack right here let me zoom in just a smidge we'll talk about this and what i'm actually going to do is i'm going to put a draw i o over here on the side as well let's say we have a stack you know what's a better way to think about a stack you draw a box i could do that in a second but actually here let me grab a stack of stuff let's say that i'm reading a book this is a book i have a stack of books on my desk then i'm going to go and i'm going to take another book and i'm going to push this book on top of the stack and then i'm going to take another book and i'll push it on top of this deck 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 isn't an array 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 on the stack there's something back on push something back on or something back on push and pop that is a stack the data structure so return back here same idea take something push it onto the stack push out of the stack push onto the stack let's do that with code we're going to move this over here we're going to think about our stack this way there we go make sure that that's visible cool so i'm going to make a stack of string call it a happy stack then i made a dump function this function called dump i'm going to right click on that in visual studio here and say go to definition and all my dump is going to do is it's going to draw some lines and then it's going to say what's in the stack and then it's going to pour each it's going to loop over the stack and then print out everything that's in that stack now in this case i did it the old way in c sharp now we go like this there we go put a little space a little extra space there we're going to dump our stack we're going to enumerate over our stack now just like i pushed books i'm going to push on hello push on world i'm going to push on the exclamation point then we'll take a look at our stack we'll say hey how many items in our stack i'm going to dump it out then i'm going to pop one thing off the top of the stack and i'm going to look at it again first let's do that once then we'll look at it a little quicker all right we said hello world exclamation point in that order we have three items in our stack and look at the order backwards that came in last hello was first i'm gonna pop the last thing off the stack which was the exclamation point and now it's gone but now the stack has two things okay now in visual studio i can put a break point and i can hit f5 or i can push the play button a debug button start the debugger a bunch of things will happen the windows will change you see right here in our watch window right here we have a happy stack with nothing in it all right now i'm going to hit f n which means step over that's this button right here step over i'm going to step to the next line we still haven't put anything in our stack now we're going to push on hello oh one item appeared in our stack push on world look hello move down hello move down again okay now we're going to pop we're going to pop there's the top of our stack of books our stack of strings in this case now it's gone there it is dump it out all right that is a stack as a type of data as a data structure so if we remember the behavior of a stack that it is last thing in first thing out or lifo lifo last in first out then that can help us as we think about stacks of memory think about stack frames and other kinds of stacks so that was our first example stacks as data structure which we talked about here cool let's check that off cool thanks now let's look at it in the context of memory here i just made a little main a little main application we say and actually you know what i'm going to do i'm going to just move myself up here i'll live up here for now there you go that's nice so i've got some numbers i'll add them together they're all living in the scope of these two curly braces some people think those look like mustaches but i don't think so and then i've got a person myself i've got cancelman and then i'm going to go ahead and output that person so i've made a couple variables here and i've made a variable there these variables here live inside this scope this one also lives inside this scope okay but this is allocated on what's called the heap if we go back over here we think about our execution of our main let's say that this is our main here all right here's our main then we're doing some stuff in there we made our variable a b and c on the stack and then it looks like we did a person object well that's going to be in a in a heap and a pile of memory it's elsewhere maybe i'll have the people over here i could have an array of people or a stack of people i could have a bunch of stuff over here in the heap now this main here we called it main but that could be just a thread thing that we're doing let's say i had a couple of threads red one and thread two spread thread three they each get their own stack they have their own area their own scope they can all use the memory that's in that pile that means that the value of a b and c can be different in each thread over here we might have a is zero because it's doing one thing over here we could have a is 99 50 40 42 we don't know but the person on the heap is the same person if they have a reference to it that can be a little hard to visualize a little confusing to visualize this stuff right here let's try this first we'll just run this and i like to run things with a break point so what i'm going to do is i'm going to put that over here and then i'm going to do this my little trick start running our application i'm going to take my application here i'm going to stick it off to the side and then we're just going to take our splitter okay so our applications here on the left over way over 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 which again hits this button over here it's kind of hidden step over i'm going to step over step over step over see down here in our watch window and nothing really interesting has happened our person is null because we haven't made a person yet all right we haven't printed anything out over here yet either and then there's this thing that you get in visual studio i'm going to move myself out of the way here of course put myself over here there's a thing you get in visual studio called diagnostics tools there's a section here called memory usage and it lets you take a snapshot that you take a picture your memory let's do that let's take a picture of our memory okay then i'm going to go and hit f10 now we have a person see our person down here my age first and last and then i'm going to take another picture snapshot so now i've taken a memory picture twice before and after i made my person we go back to here and we remind ourselves about this situation that we've got okay we have our heap our pile of memory with our person in it and we have our thread in this case the only thread we really have is the main function i don't have any threads we put this in a heap i have a nice stack of books i have lots of stacks of books individual stacks that i'm working on individually pushing and popping things on my list i've got my self-improvement books i've got my science fiction books i've got my language books but then i also have a heap big old pile of books that i'm just kind of dealing with sometimes it gets fragmented it gets a little messy but for the most part i just throw books in the what we can do over here i can say huh let me view this heap take a look at what's going on in here and i can say what's all the memory some of this memory is other stuff because my application is running different things but remember that we have person so i want to type in person and i can say look in my pile of things my pile of memory things i see that there's one person it's 40 bytes big that's cool click on that let's see if it's a is there a graph how large is it where does it live does anyone else care about this thing i can see that it's a local variable and only one person one place one thing has a reference to it in our application let's change this out to make it a little bit more interesting go back over here and let's make our app more complicated so here we output a person we said hey cool i'm going to add another one so i'm going to output it before and after so in here we're going to go and do something cool we'll pass in our person p okay i haven't made a do something cool yet so i get a little squiggly there like it's not spelled right but it's just telling me that there's no person here i'm going to hit control dot and it's going to pop up a thing that says generate method it's going to go and write it do something cool for me look at that that's fun and our do something cool takes a person so inside of 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 being me and then i'll check it afterwards all right let's do that put a break point there hit f5 bounce bounce bounce bounce oops go ahead and put that over there again now let's bounce bounce back okay there's my age and i'm going to say do something cool now instead of stepping over that i want to go inside that so i'm going to push f11 and that's going to let me step into zoom in here i'm going to step into rather than step over these buttons are getting a little messy that's because of the way that 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 hit f11 now i'm inside there you watch my instruction pointers telling me that that's the next thing that's going to be executed all right now here's our person right there there's the age now we're gonna step over we're gonna age plus plus remember that the person lives on the heap and right now it exists right here so i passed in a reference to it i gave someone a pointer to it not a real pointer like c or c plus plus but a reference it's an easier pointer we're going to say age plus plus we see now it's 100. here's the question did i change the age for the person everywhere or just for the person that lives here let's find out we're going to go out next line and look we changed the only person we saw that on the heap on the big pile of memory there is a person and we change that number for everyone or anyone who cares about that person that age just went up okay now back here we had this number c this list long let's change do something cool and we're going to pass in 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 okay and it holds 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 i can pass that in and then i'm going to say a plus plus uh-huh not really c plus plus but still all right and then instead of console.writeline this stuff will console.writeline c that's what we care about all right so we're going to change c and then we're going to come back and we're going to see before and we'll do something cool and then we'll see after all right let's do that okay let's watch 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 that is 99. now talk about call stacks in a little bit but it's worth noting that we're currently in the main application the main uh function it'll f11 okay now we're gonna go and say c plus plus watch our c right here okay and we changed our age now here's our stack our call stack we were in main now we're gonna do something cool now we're gonna leave do something cool we're gonna come back to main let's see what c is c is 99. not 100. but the age of our person remains 100. that's because the c that we changed the number c the variable c that we changed was passed in 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 in the stack inside of that method we changed only that number and then that number went away we pushed all those variables on the stack pushed the parameters on the stack 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 larger object that person object lives in the heap and when we passed it in it was passed in by reference so these items lived in the stack within this context and this c is a different c that had its value passed in and then we made a little copy of it there that created stack here all right that's interesting you can see the way we can prove those things by using our watch window by being really thoughtful about what we're doing that's cool then we talk about stack allocation as in the context of memory allocation i touched a little bit on the stack frame let's dig into that for a second here i've made a little application that says console.writeline and then i have three functions happy little and function and each of those functions returns a string then i say hey console.writeline call this function and then add it to the value of the return value of this function and then add it to the return value of that function so you can imagine what this is going to look like i'll hit a breakpoint push f5 all right let's hit f10 f5 again starts my application f10 steps over all i'm doing is using the hotkeys that visual studio has for me i'll just remind you of those this is your f5 start you can see that it's f5 because it says so right there my function key five and then here we've got step over which my mouse is in the way of a little bit and i've got step into all right so go back here f10 happy little function cool let's actually do that again i'm going to say f11 there's happy there's little there's function all right one more time this time we're going to pay special attention to our call stack i'm going to say restart i want you to watch right here we're in the main function we're going to do something tricky here i'm going to right click on that i'm going to say show parameter names and we have frame status it shows everything that happens in the context of our all stack this lets you know how deep you go all right so we're going to hit f11 we were in main now we pushed on top of that and now our call stack isn't happy we're still in main you see how we're still up there but we're also here we're waiting for this to come back now we're going to return happy and we pop that off and now we returned that value c down here happy returned happy then we're going to go down again now we're in little there's our call stack watch our watch window we just returned little now we're going to return the word function all right so what happened there we had a main and then we ran another function and we said happy and then we came back and we did little and we came back to maine we said function so our call stack never got more than too deep let's change this we're going to change this and what we're going to do is instead of saying happy and then little and then function we're going to go and we're going to call some different things i'm going to call one function that i made earlier called happy and and happy and is going to call little and and pass in happy then little end is going to add itself and then it's going to say function end and then it's going to call little function and we'll go and re take the value passed in and pass in function so we're going to take the string happy pass it to little add a word pass it to another one and add that and we should get the exact same output happy little function but we're going to see a deeper call stack let's do that hit f5 set my window up there all right we're going to watch right here start out there and we're going to say f11 so now we took our main we just added happy end and now we're gonna f11 again and now we've gotten a little deeper f11 again main is down here you can see it right there we're still waiting happy and is still waiting for little n to return little and is still waiting for function and to return over here we can see what's waiting we're going to go in f11 f11 we see that the final result is happy little function and then we're going to go pop up up up all the way back to here and the result will pop out right here happy little function now that is not recursion that is a slightly deep call stack each one of these functions called another passed things in and had to wait around until the return let it release but then the call stack got a little bit deep that gives you a sense of stack frames and call stats now finally recursion isn't this fun take a look at this let's recurse get into some trouble and we're going to have a stack overflow here we're going to take a number which is a million this is a classic example we have a main and main is going to call countdown and then all countdown is going to do is it's going to say hey if 0 is greater than and then it's going to take the number n and it's going to subtract 1. so this million is going to become 999.999 then it's going to call itself i'm going to call itself so it's going to need to call itself a million times set f5 and actually let's just turn off the breakpoint let's let it run because i don't want to go and hit my button a million times do i stack overflow it looks like it made it about 19 000 times and then it gave up and we got a stack overflow that's cool oh i got a nice little exception thing here and a little pop-up and a whole deal chaos back overflow what does that mean look at our memory give up all right figure out what's going on let's put a break point right here let's hit f5 and i want you to watch that call stack oops i'm going to move myself out of the way there we go f11 okay now we're going to call ourselves see that number n i'm just going to add that over here in the watch window if we'll see that go down i'm just going to go f11 f11 11. make myself a little smaller maybe i'll go up here watch our number i'm just going to hold f11 down so what we're doing is we're getting deeper and deeper and deeper watch look at this here look at that look at that scroll bar what's happening is we are making a stack here of functions as we await as each function waits for the net the last one to finish and it can't unroll and pop everything off that stack because it's waiting and it's never ever going to finish the tail the the end of all of this is only going to happen there notice that the countdown method only has one way out the only way out is when the number zero is greater than the result of that n so when we hit negative one then it will return and then this kind of already ridiculous call stack will unravel and go all the way back off so what's happening is we are overflowing our stack because programs have only so much stack space your heap is as big as your your processor architecture allows it to be 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 go and google for that but at this point we have to ask ourselves two things and this is where we get a little bit advanced and i'm going to let you go off and google for that because this is about educating yourself not about me doing 400 level videos one was this the right architecture to do this work was recursing a good idea spoiler alert no second question maybe it was the compiler's job who have figured that out seen it coming and automatically converted that to something a little bit different for example what if we change this countdown and we made a better countdown let's say this one's a bad one a better countdown might look like this and we would pass in our initial value that better countdown would just say well as long as you can forever until it gets done now this is in fact not ideal this code right here but that's what the compiler would generate there's lots of different ways to go and spin through that for loop for each wow doesn't matter point is the instructions that we had before recursed we got deeper and deeper and deeper and deeper and deeper into our methods waiting for the final tail of that while this does it without any stack when i run this this actually finishes because there's no stack at all we can prove that during our break point hitting f5 we call that method once and then we just spend all of our time in this method you see our call stack down here is very simple so that should give you a sense of x as a data structure stack allocation versus heap allocation concept of a stack frame or call stack and then a little bit about recursion and then the results of a stack overflow something to watch out for is that some languages like c sharp in different instances may or may not have what is called tail call optimization that can handle tail call recursion and could theoretically take that and make it better figure it out do the right thing uh there's a language called f sharp that does that automatically every language is different uh c-sharp doesn't do that even though it possibly could that's advanced stuff you might want to go and educate yourself about that but in the course of your average day you usually won't hit these things unless you're doing some pretty interesting computational work or if you're building an architecture that relies on recursion like if you're doing a fibonacci sequence or some advanced math but there's usually always a way to do it without using so much stack and doing it like this imperatively so that's interesting cool so stacks thank you very much for watching this has been looks like how many minutes 36 minutes sorry that was so long i hope you enjoyed it and uh the best thing that you can do to help me out as i'm having all kinds of fun with this youtube is to tell your friends also i'd like to let you know that i made a silly domain or uh this that will get you directly to the playlist so if you go and use computer stuff they didn't teach you dot com it'll just redirect to this playlist so tell your friends have them subscribe and keep sending me your questions and i'll keep doing videos thank you

Channel: Scott Hanselman

Views: 52,700

Rating: 4.9595604 out of 5

Keywords:

Id: 03pp6cz8lWo

Length: 36min 38sec (2198 seconds)

Published: Sun Oct 04 2020