Currently, the general purpose allocator keeps up an ordered linked list for the free blocks. The benefit of this approach is, that combining adjacent free blocks is easily done. The drawback is that deallocation time increases with the number of free blocks. The list has to be traversed until the free block preceding the current deallocation has been found.
An alternative approach would be to simply use an unordered linked list were deallocated blocks are added at the end of the list (The block that reaches until the end of the managed memory has to be excluded from that list). The drawback here is that combining adjacent blocks is not as easy anymore. Here you have to traverse the whole list to check if there is an adjacent block for every block in the list. Even though this can be optimized below N^2 checks, it is even more expensive. However, the block combination could be delayed and only be done at certain intervals or after a certain number of deallocations.
Another possibility is to have a recently freed blocks list which is ordered. If it reaches a certain size, one could do an update of the linked list. This would reduce the traversals of the list.
Question is if this is really faster/necessary since the general purpose memory is not really intended for frequent allocations and deallocations.
Another question is if it makes sense to make the general purpose memory dividable into multiple blocks for allocations of different sizes. This should help to prevent fragmentation.
Currently, the general purpose allocator keeps up an ordered linked list for the free blocks. The benefit of this approach is, that combining adjacent free blocks is easily done. The drawback is that deallocation time increases with the number of free blocks. The list has to be traversed until the free block preceding the current deallocation has been found.
An alternative approach would be to simply use an unordered linked list were deallocated blocks are added at the end of the list (The block that reaches until the end of the managed memory has to be excluded from that list). The drawback here is that combining adjacent blocks is not as easy anymore. Here you have to traverse the whole list to check if there is an adjacent block for every block in the list. Even though this can be optimized below N^2 checks, it is even more expensive. However, the block combination could be delayed and only be done at certain intervals or after a certain number of deallocations.
Another possibility is to have a recently freed blocks list which is ordered. If it reaches a certain size, one could do an update of the linked list. This would reduce the traversals of the list.
Question is if this is really faster/necessary since the general purpose memory is not really intended for frequent allocations and deallocations.
Another question is if it makes sense to make the general purpose memory dividable into multiple blocks for allocations of different sizes. This should help to prevent fragmentation.