Check out a free preview of the full The Rust Programming Language course:
The "Heap Bookkeeping" Lesson is part of the full, The Rust Programming Language course featured in this preview video. Here's what you'd learn in this lesson:

Richard briefly provides an overview of part 5 of the course and discusses the process of the alloc function. The alloc function, when called, will take unused heap bytes and mark them as being in-use for later reference.

Get Unlimited Access Now

Transcript from the "Heap Bookkeeping" Lesson

>> So part five, six and seven are basically each of them are going to introduce the three main concepts of rusts automatic memory management system. Those concepts are ownership, borrowing and lifetimes. We start with ownership and and first learn how that works. Then in the next section we'll talk about borrowing and then finally we'll end with lifetimes.

[00:00:18] Cool, so first, we're gonna talk about manual memory management. Then we're gonna talk about automatic memory management, then ownership and finally cloning. Okay, so we previously talked about the heap and how when we want to make a vec full of nums that are gonna live on the heap.

[00:00:34] We call this vecmacro, and it's going to actually store them inside the heap. What's gonna go on the stack is something more like this VecMetadata struct, we're gonna have the first element index which is going to be where this one is stored. And then the length which will be three the capacity which is gonna be at least three but might be bigger than that.

[00:00:52] In this case the vec macro will set the capacity to be three but these things are going to live on the actual heap. Okay, so let's talk a little bit more specifically about that he bookkeeping that we were talking about. So basically whenever the vec macro gets run it calls a function called alloc which is short for allocate.

[00:01:13] You may hear the term allocation used to refer to like sort of reserving memory. Allocation can refer to the stack or the heap but typically speaking, whenever people talk about allocations if they're not more specific than that, they usually mean heap allocations. It's a common technique in performance optimization to say, reduce allocations and when people say that they mean reduced heap allocations cuz they can be kinda expensive.

[00:01:35] This alloc function actually takes a non trivial amount of time to run depending on like what's been going on in your program. So basically what its job is to say find three unused heat bytes in a row and mark them as in use. So when this happens, this is not something that's built into the hardware.

[00:01:54] Like the computer does not have a concept of a stack or a heap. It just has ones and zeros and instructions for doing like arithmetic and things like that. So when you run this function, it's actually running a non trivial amount of logic. It's got an actual data structure in memory.

[00:02:08] This alloc function does like a global data structure that's storing these indices of which things are available and which things are in use. When you call it, it's actually doing work to traverse this data structure like it's like a potentially a big tree and actually find out where the next available thing is.

[00:02:26] Especially when you get into concurrency and stuff. This can be quite time consuming, so let's say that it comes back, alloc returns it says okay, I found three unused e bytes in a row. Great, here they are. I'm going to mark them in my alloc data structure as in use.

[00:02:40] So next time you ask me I'll remember not to give you these things. But there's a reasonable question to ask here which is okay, how does it know when they're no longer in use? I guess one of the important points of this bookkeeping system is we ask it for three bytes that are not in use.

[00:02:56] Okay, fine when I call alloc it marks them as in use, but how does it know when to mark them as no longer in use? So this is not a problem that we had on the stack, on the stack we just had that stack length that gets higher and lower and then that's sort of how you know as you call the function.

[00:03:11] Once the function is over, well, we can move the stack back on all the remaining bytes become garbage. But on the heap, it's different. On the heap, the question of when is this thing no longer in use is non trivial. It's it's not obvious. Well, this is where we get into the concept of manual memory management.