[MUSIC]. Okay. Let's now start digging into how memory locators work. Okay. Let's, let's start with the assumptions made in this lecture. Okay. So first of all, memory is word addressed. Okay. So each. So each word, you know, each word can hold a pointer. And a block size, the allocator of free block size is going to be a size that's multiple of words, okay? For example if, if here we have our heap. So we'll have for example, have an allocated block here that happens to be four words, and have a free block here that happens to be two words. And so on. 'Kay, another free block here, and so on, and this, this is a free block, and this is an allocated block. Okay. So let me give an example, okay. So that's the order we're going to make these calls. First, when we call malloc, this is our heap, okay, this is our heap, and then when malloc says, I want a block of size 4. We're going to allocate four words, okay? Now, now it could say allocate five, I'm going to allocate another five words. and now I can allocate six, I counted six words. Then now we're going to free p2 and note that we're passing some parameter, a pointer that was earlier returned by malloc. 'Kay. So that's, so when we do that, this block is now free. Now we have some holes in our heap. And when I allocate 2, we have two options, could go there or there. We just chose to allocate it here, and so on. One important question is that when we were implementing this allocator, what information, what information does it need to keep track of? Well, it needs to keep track of where the heap is, where it starts. Right? And the word ends so it is the size of the heap. And that's what keeps, it needs to keep track of what are, what parts of the, the, the heap are allocated. Like this allocated, allocated and allocated, and what part is free, 'kay. And it also needs a data structure to, in order to find blocks we need to allocate it and you need to also be able to know what, what parts of course know parts of the heap are free. So you are allocating it there and so on. Let's look at what constraints the allocators have. So first from the application point of view it can issue an arbitrary sequence of mallocs in free requests. Okay. So and free requests must be made only to a previous malloc block. I've said this two or three times already because it's actually really important. And allocators, from the allocator point of view, the first thing it's important to know is that they really can't control the number size of allocated block. This is something that the application does. The application does the requests and the allocator just serves those requests. So it doesn't really know what the application is going to need. In the future. 'Kay. And we want it to be able to respond immediately to Malloc Requests. 'Kay? So in other words, it cannot reorder or buffer requests. So a synchronous call. When you call Malloc, when it returns, it has to have done the job. It can't just reorder them. It has to prompty respond immediately. Right, it have to be So otherwise it creates a, a big problem. Of course we only want to allocate blocks from free memory. If you allocate blocks from allocated memory, it's going to be a big mess. You're going to be over writing data from the application. That is not going to be a good thing, for sure, contains bugs, and hard to find and so on. So blocks can't, cannot overlap. So and also it has to align blocks. And by alignment, it means that the pointers at the beginning of the block has to be a multiple of a certain number. 'Kay? For example the GNU malloc library allocates blocks in an eight byte criminality. Okay? So this just is just satisfy a bunch of alignment requirements. And, of course, once an allocated block has been allocated it can not move. And so in other words compaction is not allowed. Why? Well imagine the following, you call malloc, you get a pointer. And now you assume that the data is in that pointer and then the allocator just moves it around. If you don't update the pointer then you're going to be pointing to stale data and that's going to be again a big mess. Okay, so allocators have to follow a very strict discipline. And now from the performance point of view there's two components, the first one is throughput Okay? Instead it means the following. Given sequence of malloc and free requests. Their goal is to maximize throughput okay? So their goal is to maximize that. And the other component by the way of performance is peak memory utilization. We want to use memory, we want have as few holes as possible. We want to use as much memory as possible. Okay. So, and this goal is often conflicting because if you want to maximize throughput you want to do things very, very fast. Therefore you can't afford to do very sophisticated, do a lot of work in managing memory to increase big utilization. So in the throughput here is a number of completed request per unit time. For example, you want to do 5000 mallocs in a 5000 free calls in 10 seconds, that's throughput and what we are doing here is it will be a total of 10, total of 100 operations per second, because we had 10000 operation than in 10 seconds 1000 operations per second. The other performance goal of allocators is peak memory utilization, okay. Let me tell you what it is now. So again we have our sequence of requests from R0 to Rn minus 1 and the aggregate payload Pk is the total useful memory provided by the malloc. Blocks. Kay? So, the, that's the payload P of a malloc block is isn't the number of bytes requested by the application. Kay? So, say the aggregate payload Pk is the total by, the total number of bytes that malloc provided but it's requested by the application. At request Rk OK and now we define the heap size the current heap size is hk and its monotonically nondecreasing, it only grows as we need more heap space and this is done by the system called sbrk as I mentioned before and now, now that we know we defined the current heap size and the aggregate payload. 'Kay. Which is the, the aggregate number of useful bytes in a, in a sequence of [UNKNOWN] and free requests. What we want to do is if I'm peak memory utilization as the maximum of the payload up to request K. Right, that's the peak memory utilization at the moment when you call a certain request here RK. Okay? And so the pigment memory utilization is the fraction of the heap that was useful in the past. Okay, remember that the heap never decreases so that's why we, we, we're using max. Okay, so the pigment memory utilization is the maximum aggregate payloads divided by the size of the heap. Okay? And the goal is to actually maximize this number. We want to make the heap as useful as possible, do whatever allocated leap as useful as possible. Okay? Why is this hard? This is hard because something called fragmentation all the wholes that appear in our heap okay. And by the way managing that has an effect on throughput because it has overheads. It takes work by the memory allocator to, to provide that. So let's go towards fragmentation now. There is two types of fragmentation from internal fragmentation and external fragmentation An internal fragmentation is the fragmentation within a block, and the reason we have that is that, this is for example, here's our block, 'kay? And the actual payload is just a part of this block. The payload, that's what, that's what useful to the application, and it's smaller than the block size. 'Kay? So all of these parts here they are not useful. These are, they are the source of internal fragmentation. 'Kay? So, and this is caused by overhead of maintaining, in space overhead in maintaining the heap data structures. Like you know, things like markers whether the block is free or not, pointers among the blocks, and so on. Also the padding for alignment purposes, we just had earlier that one of the requirements of dynamic memory locators that they need to provide aligned blocks. Kay? And also this internal fragmentation is caused by, by explicit policy decisions. Kay? So, you could return a big block to satisfy a small request. Why would you do that? Because of performance reasons, okay? So and one interesting thing about internal fragmentation is that depends only on the pattern of previous requests so it's easy to measure, okay? So now what's external fragmentation. Well it's external because it's external to the block. So that means that it's, it occurs when there is enough aggrogate heap memory. But no single free block that's large enough. So let me give you an example here. So suppose that we had the sequence of mallocs, here, and then we had the free, so we have, you know, five free here and two free. And what if I all, if I allocate six, I'm not going to do that. So what happens, so actually I have is 5 free here and I have 2 free here, so I have a total of 7 free. But, none of them are large enough to honor this, this request of 6, so what will happen now. Well, nothing we can so in, by the way this is actually depend on the pattern of future request. Its actually difficult to measure. Where the fir-, external fragmentation is a problem or not. See you soon.