Handing out memory
Programs ask for memory all the time: "I need room for 200 bytes", "now 4,000", "I am done with the first one". Each request must be given a stretch of memory that is in one piece, and each freed block becomes available again.
The component that manages this is the allocator. Its job sounds like bookkeeping. The difficulty appears after a while, when blocks have been freed in a different order from the one they were handed out in, and the free space is no longer one big region. It is a scatter of gaps between blocks still in use.
A new request has to go into one of those gaps. Which one?
Four ways to choose a gap
Pick an allocator and watch the same sequence of requests.
Coloured: in use. Grey: free. Red: a free gap too small to be much use.
Start. Scan from the start and take the first gap that is big enough. An empty strip of memory, 32 units long. Programs will ask for blocks of different sizes and give some back.
- Free in total
- 32
- Largest gap
- 32
- Slivers (gaps of 1 or 2)
- 0
- Requests failed
- 0
First fit
Scan from the beginning and take the first gap that is big enough.
Coloured: in use. Grey: free. Red: a free gap too small to be much use.
Start. Scan from the start and take the first gap that is big enough. An empty strip of memory, 32 units long. Programs will ask for blocks of different sizes and give some back.
- Free in total
- 32
- Largest gap
- 32
- Slivers (gaps of 1 or 2)
- 0
- Requests failed
- 0
It is quick, because it stops at the first match. It tends to pack small blocks near the start of memory and leave larger gaps further along.
Next fit
Like first fit, but continue searching from where the last search ended and wrap around at the end.
It spreads allocations around the whole of memory, and avoids re-scanning the crowded start every time. The cost is that it chops into the big gaps at the far end sooner.
Best fit
Look at every gap and take the smallest one that is big enough.
It sounds like the obvious winner: waste as little as possible each time.
Coloured: in use. Grey: free. Red: a free gap too small to be much use.
Start. Check every gap and take the smallest one that is big enough. An empty strip of memory, 32 units long. Programs will ask for blocks of different sizes and give some back.
- Free in total
- 32
- Largest gap
- 32
- Slivers (gaps of 1 or 2)
- 0
- Requests failed
- 0
Watch the red cells. A tight fit is almost never an exact fit. Each time, a tiny leftover remains: one or two units, too small for nearly any request. Best fit is very good at producing these slivers.
Worst fit
Look at every gap and take the largest one.
The reasoning: after a big gap is cut, what remains is still a useful size. No slivers.
Coloured: in use. Grey: free. Red: a free gap too small to be much use.
Start. Check every gap and take the largest one. An empty strip of memory, 32 units long. Programs will ask for blocks of different sizes and give some back.
- Free in total
- 32
- Largest gap
- 32
- Slivers (gaps of 1 or 2)
- 0
- Requests failed
- 0
The flaw shows up at the end. By always cutting into the largest gap, it destroys the large gaps. When a big request arrives, there is plenty of free memory in total, and no single gap big enough to hold it.
Fragmentation
Both failures have the same name.
External fragmentation is free memory that cannot be used because it is in pieces. In the worst-fit run, the last request needed 5 units, 9 were free, and it failed, because those 9 were split into gaps of 4, 4 and 1.
Example
Free, and still not available
Think of a car park with ten empty spaces, each between two parked cars. There is room for ten cars. There is no room for one bus.
Memory cannot simply be shuffled together to close the gaps, at least not in languages like C: programs hold the addresses of their blocks, and moving a block would leave those addresses pointing at the wrong place.
There is no winner
In this sequence, first fit comes out best, and it usually does well in practice. But the sequence was chosen to show each strategy's typical weakness, and a different sequence ranks them differently.
| Allocator | Speed | Typical weakness |
|---|---|---|
| First fit | Fast: stops at the first match | Clutter builds up at the start |
| Next fit | Fast | Breaks up large gaps early |
| Best fit | Slow: checks every gap | Leaves many tiny, useless slivers |
| Worst fit | Slow: checks every gap | Uses up the large gaps |
What real allocators do
Real ones avoid the search altogether with a different idea: keep separate pools for different sizes.
Round each request up to a standard size
For example 16, 32, 64, 128 bytes, and so on.
Keep a list of free blocks for each size
A request for 50 bytes takes a block from the 64-byte list. No searching.
When a block is freed, put it back on its list
The next request of that size reuses it exactly.
Because every block in a pool is the same size, a freed one always fits the next request perfectly. The gaps problem disappears. The price is internal fragmentation: a 50-byte request sitting in a 64-byte block wastes 14 bytes inside it. That waste is small and predictable, which is a good trade.
Languages with garbage collection can go further. Since the runtime knows where every reference is, it can move the live blocks together and fix up the references, leaving all free memory in one piece. This is called compaction.
Key takeaways
- An allocator hands out contiguous blocks of memory and takes them back.
- As blocks are freed, free memory breaks into gaps, and each request must choose one.
- First fit takes the first gap that fits. Best fit takes the tightest. Worst fit takes the largest.
- Best fit leaves tiny slivers. Worst fit destroys large gaps. Both are forms of fragmentation.
- Real allocators mostly use pools of fixed sizes, trading a little wasted space for no searching.