In the current implementation of linkedlist heap allocator, the heap memory being deallocated are still fragmented by distinct nodes, and at some point, after repeated allocations and deallocations, the heap memory may to too fragmented to have large allocations. As shown in the picture:
One possible solution is that instead of appending every new node to the beginning, sort the linkedlist nodes in the order of starting address. During deallocation, examine the addresses and sizes of neighboring blocks to determine whether we can merge them together.
This approach would compromise efficiency for dealloc (from O(1) to O(n)), but will solve the memory fragmentation issue
Raine-Yang-UofT
commented
7 months ago
In the current implementation of linkedlist heap allocator, the heap memory being deallocated are still fragmented by distinct nodes, and at some point, after repeated allocations and deallocations, the heap memory may to too fragmented to have large allocations. As shown in the picture:
One possible solution is that instead of appending every new node to the beginning, sort the linkedlist nodes in the order of starting address. During deallocation, examine the addresses and sizes of neighboring blocks to determine whether we can merge them together.
This approach would compromise efficiency for dealloc (from O(1) to O(n)), but will solve the memory fragmentation issue