Best heuristic for malloc

Question

Consider using malloc() to allocate x bytes of memory in a fragmented heap. Assume the heap has multiple contiguous locations of size greater than x bytes.

Which is the best (that leads to least heap wastage) heuristic to choose a location among the following?

1. Select smallest location that is bigger than x bytes.
2. Select largest location that is bigger than x bytes.

My intuition is smallest location that is bigger than x bytes. I am not sure which is the best in practice.

No, this is not any assignment question. I was reading this How do malloc() and free() work? and this looks like a good follow up question to ask.

Answer 1

In a generic heap where allocations of different sizes are mixed, then of the two I'd go for putting the allocation in the smallest block that can accomodate it (to avoid reducing the size of the largest block we can allocate before we need to).

There are other ways of implementing a heap however that would make this question less relevant (such as the popular dlmalloc by Doug Lea - where it pools blocks of similar sizes to improve speed and reduce overall fragmentation).

Which solution is best always comes down to the way the application is performing its memory allocations. If you know an applications pattern in advance you should be able to beat the generic heaps both in size and speed.

Answer 2

It's better to select the smallest location. Think about future malloc requests. You don't know what they'll be, and you want to satisfy as many requests as you can. So it's better to find a location that exactly fits your needs, so that bigger requests can be satisfied in the future. In other words, selecting the smallest location reduces fragmentation.