Algorithm for efficiently allocating memory

Given the following constraints:

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.

• You question seems to be stated as language agnostic except that the `malloc` tag seems to hint at C, but in C, for example, we cannot rearrange blocks as there is insufficient information to repair the program after doing so; thus, an algorithm for C would necessarily omit such actions. Apr 26, 2018 at 4:15
• Wondering what exactly you mean / how that works, that's interesting. They mentioned that here as well. Apr 26, 2018 at 4:51
• I heavily recommend you get a copy of "Modern C++ Design" by Alexandrescu. Chapter 4 of that book is completely dedicated on how to write a very efficient memory allocator (table of content here). Apr 26, 2018 at 6:42
• @LancePollard The fastest time-wise is usually just a simple bump allocator i.e. you just increment the pointer by the necessary size (taking into account alignment). You then free the whole thing when you're done. You only need free lists etc if you have space constraints.
– Alex
Apr 26, 2018 at 13:19
• C doesn't record the type of the item that is `malloc`'ed, so to C's runtime, `malloc`ed blocks are just blocks of memory that can be (used and) `free`ed. C also uses pointers, of course. So one `malloc`ed block may have pointer(s) within it referring to other `malloc`ed block(s). If you move a latter such block, you would have to make a corresponding update to any pointers to it. But since C doesn't track `malloc` block types, we cannot find these pointers that require corresponding updates. And that is the tip of the iceberg for C and block moving/compaction. Apr 26, 2018 at 16:00

Let's imagine for a moment all of your `Item`s 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 `Item`s 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).