# Best Fit Memory Allocation Algorithm Statistical Analysis

I've been reading book on Operating System, in which author writes :

Somewhat surprisingly, it(Best fit) also results in more wasted memory than first fit or next fit because it tends to fill up memory with tiny, useless holes. First fit generates larger holes on average.

I want to understand how generating larger holes would be better. It would be helpful if someone can share a link of article about statistical analysis of best fit, first fit.

• I can't provide a source, but I'd imagine that tiny holes can't be used for anything, while larger holes could still be filled up with something. – Tom van der Zanden Oct 14 '15 at 15:03
• What if that larger hole + memory allocated for this process could be allocated to another large process, which now might not fit anywhere? – user148865 Oct 14 '15 at 15:07
• That's why they they talk "on average" such. – vonbrand Oct 14 '15 at 19:52

You want your "holes" to be bigger because a big hole is more likely to be useful for an allocation in the future. For example, if you have 2 128-byte holes that are not adjacent then you can't satisfy a request for 160 bytes. If the 2 128-byte holes are adjacent and coallesced into a single 256-byte hole, then you could satisfy a future request for 160 bytes with that hole.

Here's the best article I know of on memory allocation policies:

Paul R. Wilson, Mark S Johnstone, Michael Neely, David Boles: Dynamic Storage Allocation: A Survey and Critical Review, Int'l Workshop on Memory Mgt, 1995.

They followed up with a more detailed experimental study a few years later:

Mark S Johnstone, Paul R Wilson: The Memory Fragmentation Problem: Solved?, First Int'l Symposium on Memory Mgt, 1998.

In the papers they find that best fit works quite well in practice. Another lesson of both papers is that statistical analyses don't work (usually). You need to run experiments on real traces of the alloc/free calls from real workloads.

A very good public domain malloc implementation was written in the mid '90's by Doug Lea: http://g.oswego.edu/dl/html/malloc.html. It's essentially an approximation of best fit.