Algorithm for efficiently allocating memory

Question

Given the following constraints:

1. No multithreading.
2. 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:

1. Allocate block
   1. Find available free space
   2. If some exists, then use it.
   3. Otherwise
      1. 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.
      2. Given you know how to shuffle the blocks around, do that.
      3. Then allocate the memory.
      4. Potentially shift around some other blocks if you have time, to get rid of some of the fragmentation.
   4. Return

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

But then it starts to get complicated. You might mitigate this a little bit by preallocating slightly more space than necessary, but eventually it will outgrow its location, so then how to balance it out. That's where I get confused. I'm coming from JavaScript land.

Answer 1

Let's imagine for a moment all of your Items have the same size. A simple scheme would then be to have a pool of items, plus a bit for each one to mark whether it is allocated or not. Then the algorithm is simply "loop through the pool until you find an empty Item".

This is a bitmap allocation scheme.

A faster variation of this scheme is to have the free Items form a linked list. Then to allocate you remove a block from the free list (and you could even use the space for the pointer as data, since it isn't used when the block is allocated). To free you add it back to the linked list.

This is the free lists approach you mentioned.

Expanding that to variable-sized allocation, you have the entire memory area you're working with be a single "Item". When you need a smaller-sized space, you split it in half and run the algorithm recursively. When you have a fitting size, mark it as "allocated" and return it. To free, mark it as "unallocated" and merge the areas back as needed.

This is the buddy allocation scheme.

Most allocation algorithms don't do compaction, i.e. moving memory blocks around to make more space. They avoid fragmentation instead. And when their pool is full, they ask the system for more memory (the system normally allocates memory in whole pages (normally 4KB each), so they have to be subdivided).

Also, normally garbage collection is performed at a higher level (see munificent's garbage collector "tutorial" for more details).

A good representative of a "common" allocation scheme is Doug Lea's malloc. It is used by glibc and in several other places. It includes a little overview of the algorithm in its page.

The thing is that you need the right allocation scheme for the problem at hand. For example, Doug Lea's malloc is tailored and optimized to be reasonably fast, compact and safe (it can detect some usage errors), but if all you're doing is fixed block allocation, a linked list approach is probably going to be much more performant.

The wikipedia page on memory management has an overview of a few allocation schemes, but if you want all the details I really recommend Knuth's The Art of Computer Programming, which has a whole section of the second chapter (vol. 1) dedicated to this problem (considering the sheer size of the book, this really means something).