internal versus external fragmentation

Fragmentation is wasted memory that you have but cannot use, and it comes in two distinct flavours that are easy to confuse. Imagine moving house with cardboard boxes. Internal fragmentation is when you put a small item in a big box and the box is mostly empty air — the space is used (the box is taken) but wasted inside. External fragmentation is when your boxes are all packed but scattered across the room with awkward gaps between them, so although there is plenty of total empty floor, no single gap is big enough to fit the wardrobe. Same total waste, completely different shape of problem.

Precisely, in an allocator: internal fragmentation is the unused space inside an allocated block — the gap between what the program asked for and the larger block it actually received. It comes from rounding up to a size class or alignment (asking for 50 bytes and getting a 64-byte block wastes 14), or from a header the allocator stores alongside your data. The waste lives inside blocks that are in use. External fragmentation is unused space outside allocated blocks — total free memory is ample, but it is broken into many small non-contiguous free blocks, so a large request fails even though the sum of free bytes would cover it. It builds up over time as a mix of different-sized objects are allocated and freed, leaving a Swiss cheese of holes.

Each placement and structure choice fights one at the expense of the other. Best-fit and tight size classes reduce internal waste but can multiply tiny external holes; coarse size classes and the buddy system's power-of-two rounding accept internal waste to make coalescing simple and keep external fragmentation low. Coalescing adjacent free blocks is the main weapon against external fragmentation, but it cannot help if a long-lived block sits in the middle pinning everything. The honest framing: a general-purpose allocator that cannot move live objects can never drive both to zero — it can only choose where to spend the waste. (A moving/compacting garbage collector can eliminate external fragmentation precisely because it is allowed to relocate objects, which malloc is not.)