fragmentation (internal and external)

Picture a long shelf where books are placed and removed over and over. After a while there are gaps everywhere — plenty of total empty space on the shelf, but no single gap wide enough for the big new book you want to add. The space is there; it is just scattered. Fragmentation is the heap version of this: usable memory broken into pieces too small or too scattered to satisfy the requests you actually make.

There are two flavors. External fragmentation is the shelf-gaps picture: free memory exists in total, but it is split into many small non-adjacent blocks, so a large request fails even though the sum of free space would be enough. It builds up over a long run of mixed-size allocations and frees, where freed blocks of different sizes leave a patchwork of holes. Internal fragmentation is different: it is wasted space inside a block you were given. An allocator usually rounds your request up — to satisfy alignment, or because it only manages blocks in certain size classes — so asking for 33 bytes might hand you a 48-byte block, and those extra 15 bytes are reserved for you but unusable. They are not lost forever (you get them back when you free), but while the block is live they count as overhead.

What it costs: external fragmentation can make a program fail to allocate, or force the allocator to ask the operating system for more memory, even though it is technically holding enough free bytes; internal fragmentation inflates how much memory a program uses beyond the data it actually stores. Allocators fight back by coalescing adjacent free blocks into larger ones and by choosing fit strategies, but no general allocator eliminates fragmentation entirely. When a program allocates and frees in very regular patterns, a memory pool or arena allocator can sidestep fragmentation by handling all the blocks the same way.