4

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.

Community
  • 1
  • 1
Anil Katti
  • 1,313
  • 1
  • 14
  • 26
  • 2
    If one were provably better than the other, neither would qualify as a "heuristic". The entire point of using something called a "heuristic" is that you **can't** easily determine what is best. You are **guessing** based on limited information and/or a need to make up your mind quickly. – Karl Knechtel Jan 03 '11 at 18:41
  • Good point. Will fix it in the description. – Anil Katti Jan 03 '11 at 18:42
  • @Karl But there can be better heuristics and worse heuristics. In a chess game, generally speaking, attacking a queen on the next move is probably a better heuristic than attacking a pawn. But in a very specific case, attacking the pawn is what will bring you the checkmate. – Ilya Kogan Jan 03 '11 at 18:46
  • You offer "best fit" and "worst fit" as options, but I believe "first fit" and "next fit" are known to be better options. – Ben Jackson Jan 03 '11 at 18:51
  • @Ben First fit and next fit seem better in terms of time complexity (time needed to finish malloc). Do they also reduce fragmentation? – Anil Katti Jan 03 '11 at 18:55

3 Answers3

5

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.

Roger Perkins
  • 678
  • 5
  • 7
4

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.

Ilya Kogan
  • 21,995
  • 15
  • 85
  • 141
  • That is my intuition too. But, does best fit do well in practice? It also depend on the request pattern, right? I don't know how to evaluate these heuristics. – Anil Katti Jan 03 '11 at 18:59
3

The heuristics you listed are used in the Best Fit and Worst Fit algorithms, respectively. There is also the First Fit algorithm which simply takes the first space it finds that is large enough. It is approximately as good as Best Fit, and much faster.

Null Set
  • 5,374
  • 24
  • 37
  • 1
    That's interesting. Could you please point me to resources which claim that First fit is approximately as good as Best fit? – Anil Katti Jan 03 '11 at 19:01
  • This paper shows that the time*memory of First Fit is better than or equal to Best Fit usually. http://portal.acm.org/citation.cfm?id=360949 – Null Set Jan 03 '11 at 19:19