Given the following constraints:
- No multithreading.
- No care about hardware cache utilization.
Wondering what a reasonably optimal memory allocation scheme would look like.
From my limited knowledge, one implementation is Free Lists, but it says they have some issues. Then there is buddy management and dynamic allocation.
Overall, the procedure seems to be like:
- Allocate block
- Find available free space
- If some exists, then use it.
- Calculate the changes you would have to make to the memory blocks to satisfy the request. This results in a set of movements of blocks to open up an appropriately sized gap to fulfill the request.
- Given you know how to shuffle the blocks around, do that.
- Then allocate the memory.
- Potentially shift around some other blocks if you have time, to get rid of some of the fragmentation.
The middle part of that is where it starts to get difficult. There must be some data structure associated with the free/used blocks perhaps, to make it efficient to navigate around in them. Then wondering how much time can we spend looking for an ideal location. It's like you have to calculate and predict what the best case scenario is, but that would require computing a lot of stuff. Then there's the issue of doing sort of GC, and clean up the memory organization. All of this on top of balancing copying memory which is a small performance hit. Who would've thought it is so complex.
To summarize, wondering what a standard memory allocation procedure looks like that is pretty optimal. I have seen the C implementations of malloc variations but it is hard to gather all of the pieces from how large and complex it is.
For reference, I am thinking along the lines of how if a memory was organized like this:
type 1 type 2 type 3
If they are packed together then if
type 1 needs more space, wondering does it append to the end:
[empty] type 2 type 3 type 1
Or if it would give more space by shifting:
type 1 [empty] type 2 type 3