Best fit vs segregated fit vs buddy system for least fragmentation

Question

I am working on a dynamic memory allocation simulation(malloc() and free()) using a fixed sized array in C and i would like to know which of these will give the least amount of fragmentation(internal and external)? I do not care about speed, being able to reduce fragmentation is the issue i want to solve.

For the buddy system i've read that it has high internal fragmentation because most requested size are not to the power of 2.

For the best fit, the only negative i've heard of is that it is sequential so it takes a long time to search(not a problem in my case). In any case i can use a binary tree from my understanding to search instead. I could also split the fixed sized array into two where the left size is for smaller blocks and the right size is for bigger blocks. I don't know of any other negatives.

For segregated fit it is similar to the buddy system but i'm not sure if it has the same problems for fragmentation since it does not split by a power of 2.

Does anyone have some statistics or know the answer to my question from having used these before?

Answer 1

Controlling fragmentation is use-case dependent. The only scenario where fragmentation will never occur is when your malloc() function returns a fixed size memory chunk whenever you call it. This is more in to memory pooling. Some high-end servers often do this in an attempt to boost performance when they know what they are going to allocate and for how long they will keep that allocation.

The moment you start thinking of reducing fragmentation in a general purpose memory manager, these simple algorithms you mentioned will do no good. There are complex memory management algorithms like jemalloc, tcmalloc and Poul-Henning Kamp malloc that deal with this kind of problem. There are many whitepapers published around this. ACM and IEEE have plethora of literature around this.