3:30 the real problem with defragmentation is that you cannot move heap data around, as you would invalidate any pointer that was acquired before the defragmentation. As far as I know, generic heap defragmentation is impossible in low level languages, except maybe for a very restricted set of programs. I can only think of heap defragmentation being possible in high-level languages where the programmer cannot ever directly access pointers and heap data is always kept behind two levels of indirection (an object on the heap is owned by a reference counting smart pointer and the programmer is given a reference to the smart pointer), allowing for the mutation of the pointer to the actual heap data (for defrag) without invalidating any reference the programmer may have lying around.
Yes, we discussed this in another comment. You are correct, with this implementation and using pointers natively defragging is impossible. The solution with an additional indirection level could be implemented in C adding an additional field to the bitmap that holds a pointer to its currently assigned block; in this case the programmer would only keep a pointer to the bitmap entry, and whenever the defrag takes place, the second level of dereference changes. One drawback would be that the memory ends up all jumbled up and the adjacency of blocks would only be virtual.
Is a bitmap commonly used? I thought the most common is a freelist since that makes scanning easy and is an implicit data structure (so it works well with things like sbrk).
You're right, some implementations use linked lists as a support structure. It's really a matter of tradeoffs, for example bitmaps offer random access, hence for example one can check if a block is free in O(1) as opposed to O(n) for lists, but a free-space bitmap occupies more space compared to freelists. I've seen both approaches, but I believe that bitmaps lend themselves better as a didactic tool in our case :)
@@DaedalusCommunityalso a bitmap may allow for some advanced algorithms to cheaply determine best fit. While you can combine continuous blocks of memory in a free list to 1 node requiring a simple O(n) answer to best fit. Rather the complex algorithm could theoretically and or practically outperform the free list is something I think would be interesting to find out.
free lists themselves would require allocations OUTSIDE of your allocator. complicates things. also any type of linked-list structure is usually slow in practice
@@lack_of_awareness The advantage of free lists is that they *do not* require allocations outside the allocator. When a block is free, you can store the metadata in the free chunk of memory itself. And this strategy is used by glibc malloc so it’s definitely not too slow!
@@lack_of_awareness the freelist is usually somewhat deterministic in size as it's (not strickly) coupled to the memory it holds. And the free list is more than capable of governing over itself. About linked structures. Often you can unroll linked structures to a dynamic array and indices cutting the cost past the benefit point. On the fly I could just find gnu libstdc++ stating they are using a freelist. In fact a number of freelists for threads. Therefore I guess the cost of the freelist seems to be outweight by the benefits.
Ummmm.... But when you defrag the blocks, how do you notify the consument its pointer to the data has changed ? What I mean by that: int *data = malloc(N); // data now points to 0x123 // allocate bunch of data and free everything except data*, so that memory is fragmented // at some point defrag in malloc runs once you allocated something // data* still points to 0x123, however by defragging everything has moved to lets say beginning, so the actual data is stored at 0x0 data[0] = 5; // CG, you've just pagefaulted.
By literally copying each block along with the bitmap values That's why it takes so long, it's not only the pointers. One would need a different approach, like a linked list of tuples (bit, pointer, next) to defrag only the references.
@@DaedalusCommunity At this point, you’re a third of the way through writing a compacting Garbage Collector, you “just” (idk how) need to scan the stack for roots to ensure you update pointers when defragmentation happens
@@DaedalusCommunity I get the copying part, but my point is, that you have a local program that allocates a memory with system or other malloc. In C program the value of pointer won't change by itself and still points to the same memory location, even when the malloc would quitely defrag stuff in the background. Which would make the pointer invalid.
@@Antagon666 Ah yes, you're correct! With this implementation, you just can't defrag :) It's not quite advisable anyway in general, it's best to use a better allocation policy (maybe a las vegas style random algorithm to have a better compromise between fragmentation and time complexity, idk)
@@kgibbershnoxss Yeah, I guess one could extend it enough to apply some form of reference counting. Not the best sort of garbage collection, but better than nothing :)
Can you maybe show how one would implement a dynamic memory allocator that also keeps track of the amount of memory allocated, such that calling free() doesn't require the additional size parameter?
@@solidnywonsz In C, if you call malloc(), the compiler saves some space in the allocated memory to keep track of how many bytes were allocated in that space. This way, you can call free() without needing to specify how many bytes you want to free, since the compiler already knows.
You can always allocate sizeof(size_t) more bytes, and store the size there, while returning the address just after the size. Free() then looks at ptr-sizeof(size_t) to get size
Could you help me with the os tutorial? I created an array inside the c file, and when I try to access the array, all the values are null or 0. Could you show me how to fix this?
To access heap memory in C++ you don’t use malloc/free nor new and delete, they are considered a bad practice since C++11 since you need to manually manage objects lifetimes and when they are deleted, instead you need to use smart pointers Edit: I know this video talks about a lower level approach, I was just speaking about a more general use case.
Yeah smart pointers are pretty cool :) However, this video is more focused on the OS implementation of dynamic memory. Without a kernel malloc implementation, you can't have smart pointers, garbage collection, or pretty much anything else :)
@@lack_of_awareness i know the video was talking about a lower level approach, I forgot to mention that in my original comment, but in a more general use case, my comment is still correct
3:30 the real problem with defragmentation is that you cannot move heap data around, as you would invalidate any pointer that was acquired before the defragmentation. As far as I know, generic heap defragmentation is impossible in low level languages, except maybe for a very restricted set of programs.
I can only think of heap defragmentation being possible in high-level languages where the programmer cannot ever directly access pointers and heap data is always kept behind two levels of indirection (an object on the heap is owned by a reference counting smart pointer and the programmer is given a reference to the smart pointer), allowing for the mutation of the pointer to the actual heap data (for defrag) without invalidating any reference the programmer may have lying around.
Yes, we discussed this in another comment. You are correct, with this implementation and using pointers natively defragging is impossible.
The solution with an additional indirection level could be implemented in C adding an additional field to the bitmap that holds a pointer to its currently assigned block; in this case the programmer would only keep a pointer to the bitmap entry, and whenever the defrag takes place, the second level of dereference changes.
One drawback would be that the memory ends up all jumbled up and the adjacency of blocks would only be virtual.
I love your content so much. Cannot wait to watch this
Holy shit, you came back
Holy sh*t youre back
Quite :))
Is a bitmap commonly used? I thought the most common is a freelist since that makes scanning easy and is an implicit data structure (so it works well with things like sbrk).
You're right, some implementations use linked lists as a support structure. It's really a matter of tradeoffs, for example bitmaps offer random access, hence for example one can check if a block is free in O(1) as opposed to O(n) for lists, but a free-space bitmap occupies more space compared to freelists.
I've seen both approaches, but I believe that bitmaps lend themselves better as a didactic tool in our case :)
@@DaedalusCommunityalso a bitmap may allow for some advanced algorithms to cheaply determine best fit. While you can combine continuous blocks of memory in a free list to 1 node requiring a simple O(n) answer to best fit. Rather the complex algorithm could theoretically and or practically outperform the free list is something I think would be interesting to find out.
free lists themselves would require allocations OUTSIDE of your allocator. complicates things. also any type of linked-list structure is usually slow in practice
@@lack_of_awareness The advantage of free lists is that they *do not* require allocations outside the allocator. When a block is free, you can store the metadata in the free chunk of memory itself. And this strategy is used by glibc malloc so it’s definitely not too slow!
@@lack_of_awareness the freelist is usually somewhat deterministic in size as it's (not strickly) coupled to the memory it holds. And the free list is more than capable of governing over itself.
About linked structures. Often you can unroll linked structures to a dynamic array and indices cutting the cost past the benefit point.
On the fly I could just find gnu libstdc++ stating they are using a freelist. In fact a number of freelists for threads. Therefore I guess the cost of the freelist seems to be outweight by the benefits.
We're so back
Finally, finallium
Let's go malloc
0:31 only few know what the number 0x7c00 really means
Ummmm.... But when you defrag the blocks, how do you notify the consument its pointer to the data has changed ?
What I mean by that:
int *data = malloc(N); // data now points to 0x123
// allocate bunch of data and free everything except data*, so that memory is fragmented
// at some point defrag in malloc runs once you allocated something
// data* still points to 0x123, however by defragging everything has moved to lets say beginning, so the actual data is stored at 0x0
data[0] = 5; // CG, you've just pagefaulted.
By literally copying each block along with the bitmap values
That's why it takes so long, it's not only the pointers. One would need a different approach, like a linked list of tuples (bit, pointer, next) to defrag only the references.
@@DaedalusCommunity At this point, you’re a third of the way through writing a compacting Garbage Collector, you “just” (idk how) need to scan the stack for roots to ensure you update pointers when defragmentation happens
@@DaedalusCommunity I get the copying part, but my point is, that you have a local program that allocates a memory with system or other malloc.
In C program the value of pointer won't change by itself and still points to the same memory location, even when the malloc would quitely defrag stuff in the background.
Which would make the pointer invalid.
@@Antagon666 Ah yes, you're correct! With this implementation, you just can't defrag :)
It's not quite advisable anyway in general, it's best to use a better allocation policy (maybe a las vegas style random algorithm to have a better compromise between fragmentation and time complexity, idk)
@@kgibbershnoxss Yeah, I guess one could extend it enough to apply some form of reference counting. Not the best sort of garbage collection, but better than nothing :)
Can you maybe show how one would implement a dynamic memory allocator that also keeps track of the amount of memory allocated, such that calling free() doesn't require the additional size parameter?
You mean the amount of memory allocated in general?
@@solidnywonsz In C, if you call malloc(), the compiler saves some space in the allocated memory to keep track of how many bytes were allocated in that space. This way, you can call free() without needing to specify how many bytes you want to free, since the compiler already knows.
You can always allocate sizeof(size_t) more bytes, and store the size there, while returning the address just after the size. Free() then looks at ptr-sizeof(size_t) to get size
void* my_alloc(size_t bytes) { return malloc(bytes); } // ez
You forgot there's no LIBRARIES.
And no size_t
just in time 😍
JIT
Nice!
Could you help me with the os tutorial? I created an array inside the c file, and when I try to access the array, all the values are null or 0. Could you show me how to fix this?
Could you make a repo and share your code?
Nevermind. I fixed it. Now i need help with including bin files in c.
It's not true you can move memory in linear way with memove moving a pointer elsewhere
To access heap memory in C++ you don’t use malloc/free nor new and delete, they are considered a bad practice since C++11 since you need to manually manage objects lifetimes and when they are deleted, instead you need to use smart pointers
Edit: I know this video talks about a lower level approach, I was just speaking about a more general use case.
Yeah smart pointers are pretty cool :)
However, this video is more focused on the OS implementation of dynamic memory. Without a kernel malloc implementation, you can't have smart pointers, garbage collection, or pretty much anything else :)
you missed the whole point of the video. dont regurgitate what you have seen online without understanding what it means first 🥺👉👈
@@lack_of_awareness i know the video was talking about a lower level approach, I forgot to mention that in my original comment, but in a more general use case, my comment is still correct
(yet another)
ill try out the free project for september in codecrafters, if it's cool enough
Is it the interpreter? It seems very cool, I'm thinking of doing it too :)
@@DaedalusCommunity I don't think that's the September one, but it seems it is free for now! I'll check it out