Best heuristics for malloc

Question

Consider using malloc () to allocate x bytes of memory in a fragmented heap. Suppose a heap has several contiguous locations larger than x bytes in size.

Which of the best (which leads to the least debilitating load) heuristic to choose a place among the following?

• Choose the smallest place that is greater than x bytes.
• Choose the largest location that is greater than x bytes.

My intuition is the smallest place that is larger than x bytes. I'm not sure what is better in practice.

No, this is not a question of assignments. I read this. How do malloc () and free () work? and it looks like a good next question to ask.

Answer 1

In a common heap where mixes of different sizes are mixed, then of the two I would go for placing the selection in the smallest block that can place it (to avoid reducing the size of the largest block that we can allocate before we need it).

There are other ways to implement heaps that will make this issue less relevant (for example, the popular dlmalloc Doug Lea - where it combines blocks of similar sizes to improve speed and reduce overall fragmentation).

Which solution best always comes down to how the application allocates memory. If you know the application template in advance, you must beat the generic heaps in both size and speed.

Answer 2

Better to choose the smallest place. Think about future malloc requests. You do not know what they will be, and you want to satisfy as many requests as you can. Therefore, it’s better to find a location that exactly matches your needs, so that in the future you can satisfy large needs. In other words, choosing the smallest space reduces fragmentation.

Answer 3

The heuristics you have specified are used in the Best Fit and Worst Fit algorithms, respectively. There is also a First Fit algorithm that simply takes the first space it finds that is large enough. This is about as good as Best Fit, and much faster.