Loading learning content...
Your server has 64 GB of RAM. Your monitoring shows 32 GB is free. You try to allocate an array of 100 million integers—roughly 400 MB. The allocation fails.
How is this possible? With 32 GB of free memory, surely 400 MB is trivial?
The answer lies in memory fragmentation—a phenomenon where free memory exists but is scattered in pieces too small and non-contiguous to satisfy large allocation requests. Arrays, with their requirement for unbroken memory spans, are particularly vulnerable to this problem.
This page explores how fragmentation arises, why it worsens over time, and why this systemic issue pushes engineers toward data structures that don't require contiguous memory.
By the end of this page, you will understand internal vs. external fragmentation, how allocator behavior creates fragmentation over time, why long-running servers suffer most, and why non-contiguous structures like linked lists naturally resist fragmentation.
Memory fragmentation occurs when free memory is divided into small, non-contiguous chunks that cannot be combined to satisfy large allocation requests. There are two types of fragmentation:
External Fragmentation:
Free memory exists but is scattered throughout the heap in pieces too small for the requested allocation. Total free memory may be sufficient, but no single contiguous block is large enough.
Internal Fragmentation:
Memory is allocated but not fully used. Allocators often round up requests to convenient sizes (powers of 2, page boundaries, etc.), leaving unused space within allocated blocks.
External Fragmentation Example:
Memory Layout After Many Allocations/Deallocations:
Address: 0 100 200 300 400 500
┌──────────┬─────────┬─────────┬─────────┬─────────┬─────────┐
│ Used │ FREE │ Used │ FREE │ Used │ FREE │
│ 100 KB │ 50 KB │ 75 KB │ 25 KB │ 150 KB │ 100 KB │
└──────────┴─────────┴─────────┴─────────┴─────────┴─────────┘
Total FREE memory: 50 + 25 + 100 = 175 KB
Largest contiguous FREE block: 100 KB
Request 150 KB array: FAILS (despite 175 KB total free)
The 175 KB is fragmented into three pieces. No single piece is >= 150 KB.
| Aspect | External Fragmentation | Internal Fragmentation |
|---|---|---|
| Definition | Free memory scattered in non-contiguous chunks | Allocated memory not fully utilized |
| Cause | Random allocation/deallocation patterns | Allocator rounding up request sizes |
| Effect on arrays | Cannot allocate even when total free is sufficient | Each array wastes space from rounding |
| Visibility | Hard to detect without analysis tools | Predictable from allocator behavior |
| Solution | Compaction (expensive), avoid contiguous structures | Size-class allocators, custom allocators |
For arrays, external fragmentation is the critical problem. It means that even with abundant total free memory, large array allocations can fail because no contiguous region is large enough. This is fundamentally unsolvable without eliminating the contiguity requirement.
Fragmentation doesn't appear immediately. It's a progressive disease that worsens as programs run. Understanding the mechanism helps predict when and why it becomes problematic.
The allocation/deallocation cycle:
Programs continuously allocate and deallocate memory. Each allocation takes a contiguous block; each deallocation returns it. But deallocations don't happen in allocation order—they're random relative to the memory layout.
The Swiss cheese effect:
Time 0: Initial State (1MB contiguous heap)
┌─────────────────────────────────────────────────────────────────────┐
│ FREE (1 MB) │
└─────────────────────────────────────────────────────────────────────┘
Time 1: Allocate A (100KB), B (200KB), C (150KB), D (100KB)
┌───────┬──────────────┬──────────┬───────┬─────────────────────────────┐
│ A │ B │ C │ D │ FREE (450 KB) │
│ 100KB │ 200KB │ 150KB │ 100KB │ │
└───────┴──────────────┴──────────┴───────┴─────────────────────────────┘
Time 2: Free B
┌───────┬──────────────┬──────────┬───────┬─────────────────────────────┐
│ A │ FREE 200KB │ C │ D │ FREE (450 KB) │
│ 100KB │ │ 150KB │ 100KB │ │
└───────┴──────────────┴──────────┴───────┴─────────────────────────────┘
Now: Two non-contiguous free regions! Can't allocate 500KB despite 650KB free.
Time 3: Allocate E (50KB) in the hole, Free A
┌───────┬────┬─────────┬──────────┬───────┬─────────────────────────────┐
│ FREE │ E │ FREE │ C │ D │ FREE (450 KB) │
│ 100KB │50KB│ 150KB │ 150KB │ 100KB │ │
└───────┴────┴─────────┴──────────┴───────┴─────────────────────────────┘
Now: THREE free regions! Largest is 450KB. Can't allocate 600KB despite 700KB free.
Time 4: Allocate F (50KB), G (100KB), Free C, Free D
┌───────┬────┬────┬────┬──────────┬───────┬─────────────────────────────┐
│ FREE │ E │ F │ G │ FREE │ FREE │ FREE (450 KB) │
│ 100KB │50KB│50KB│100K│ 150KB │ 100KB │ │
└───────┴────┴────┴────┴──────────┴───────┴─────────────────────────────┘
Now: FOUR free regions! 800KB free but largest contiguous is 450KB.
The progression pattern:
Key insight: The longer a program runs, the more fragmented memory becomes. This is why servers that run for weeks or months experience issues that didn't exist on day one.
Languages with garbage collection (Java, C#, Go) can compact memory—moving objects to eliminate gaps. But this is expensive (pauses the program) and only partially effective. Languages without GC (C, C++, Rust) cannot move objects at all—pointers would become invalid. Compaction mitigates but doesn't solve fragmentation.
Not all allocation patterns create equal fragmentation. Variable-sized allocations—exactly what arrays enable—create the worst fragmentation.
Fixed-size allocations:
When all allocations are the same size (e.g., all 64 bytes), holes left by deallocations are exactly the right size for new allocations. No fragmentation develops:
┌────┬────┬────┬────┬────┬────┬────┬────┐
│ A │FREE│ C │FREE│ E │FREE│ G │FREE│ All slots 64 bytes
└────┴────┴────┴────┴────┴────┴────┴────┘
Every FREE slot can satisfy any new request (all are 64 bytes).
Variable-size allocations:
When allocations vary (some 64 bytes, some 1KB, some 100KB), small deallocations create small holes that can't satisfy large requests:
┌────┬───────────────┬─────────────┬───────────────────────┐
│ A │ B │ C │ D │
│64B │ 1KB │ 256B │ 10KB │
└────┴───────────────┴─────────────┴───────────────────────┘
After freeing A and C:
┌────┬───────────────┬─────────────┬───────────────────────┐
│FREE│ B │ FREE │ D │
│64B │ 1KB │ 256B │ 10KB │
└────┴───────────────┴─────────────┴───────────────────────┘
Want to allocate 300 bytes? Neither 64B nor 256B hole works.
Want to allocate 2KB? No contiguous block available.
| Allocation Pattern | Fragmentation Risk | Example Use Case | Mitigation |
|---|---|---|---|
| Fixed-size only | Minimal | Object pools, fixed records | None needed |
| Few discrete sizes | Low | Size-class allocators | Separate pools per size |
| Continuous range | High | String/array allocations | Difficult to mitigate |
| Bimodal (tiny + huge) | Severe | Mixed small objects + buffers | Separate heaps |
Arrays inherently enable variable sizes—that's their value. But this variability directly causes fragmentation. Every dynamic array resize, every string of different length, every image buffer of arbitrary size contributes to the fragmentation problem.
Fragmentation is worst in long-running processes—exactly the kind of systems that need to be most reliable. Servers, databases, and daemon processes that run for weeks without restart accumulate fragmentation that eventually causes failures.
The degradation timeline:
| Runtime | Memory State | Largest Free Block | Array Allocation Success |
|---|---|---|---|
| Fresh start | 1 contiguous block | ~Available RAM | All succeed |
| 1 hour | Few small gaps | ~90% of RAM | Most succeed |
| 1 day | Many gaps emerging | ~50% of RAM | Large arrays fail occasionally |
| 1 week | Heavily fragmented | ~20% of RAM-sized block | Frequent large array failures |
| 1 month | Severely fragmented | Tiny fragments only | Only small arrays succeed |
Real-world symptoms:
Case study: Redis memory fragmentation
Redis, the popular in-memory database, explicitly tracks fragmentation ratio:
# Redis INFO memory output
used_memory: 1000000000
used_memory_rss: 1500000000
mem_fragmentation_ratio: 1.50
A ratio of 1.50 means 50% overhead—1GB of logical data requires 1.5GB of physical memory due to fragmentation. Redis documentation recommends keeping this below 1.5; above 2.0 indicates serious problems requiring restart.
Many production systems rely on periodic restarts to "defragment" memory—a tacit admission that the problem is unsolvable with contiguous data structures. Rolling restarts, periodic recycling, and "memory hygiene" restarts are all symptoms of fragmentation-prone designs.
Modern operating systems provide virtual memory—an abstraction that makes each process believe it has a large, contiguous address space. This helps with fragmentation at the physical level but doesn't eliminate it.
How virtual memory helps:
Virtual Address Space (What Program Sees):
┌─────────────────────────────────────────────────────────────────┐
│ Contiguous virtual addresses 0x000000 through 0xFFFFFFFF │
└─────────────────────────────────────────────────────────────────┘
↓ ↓ ↓
Page Table (Maps virtual to physical)
↓ ↓ ↓
Physical Memory (Reality):
┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
│Prog│ OS │Prog│ OS │Prog│Free│Prog│ OS │Free│Prog│Free│ OS │Prog│
│ A │ │ B │ │ A │ │ B │ │ │ A │ │ │ B │
└────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
Physical pages are scattered but appear contiguous virtually
Virtual memory allows physically scattered pages to appear contiguous to the program.
Where virtual memory doesn't help:
1. Virtual address space fragmentation:
The virtual address space itself becomes fragmented. On 32-bit systems (before they became rare), this was critical—only 2-3 GB of address space, and large mappings could fail even with RAM available.
2. Huge allocations still need contiguous virtual range:
Even with virtual memory, allocating a 1GB array requires finding 1GB of contiguous virtual addresses. Virtual fragmentation can prevent this.
3. TLB and page table overhead:
Physically scattered arrays mean more TLB (Translation Lookaside Buffer) misses. Each cache miss in address translation adds latency. Algorithms that traverse large arrays suffer.
| Aspect | Helps With | Doesn't Help With |
|---|---|---|
| Physical fragmentation | Scattered physical pages appear contiguous | Doesn't reduce total memory usage |
| Address space | Large virtual range available | Virtual space itself can fragment |
| Process isolation | Each process has own space | Doesn't solve intra-process fragmentation |
| Performance | Enables using all RAM | TLB misses for scattered pages hurt |
Virtual memory is necessary for modern computing—without it, systems would be far more fragile. But it's a mitigation, not a solution. Arrays still require contiguous virtual addresses, and that requirement can still cause allocation failures.
The fragmentation problem stems directly from the contiguity requirement. Data structures that abandon contiguity sidestep the problem entirely.
Linked structures allocate in small, fixed-size units:
A linked list doesn't need contiguous memory for its elements. Each node is a small, independent allocation:
Linked List Allocation Pattern:
┌────┬───────────────┬─────────────┬───────────────────────┐
│Node│ B │ Node │ D │
│ A │ 1KB │ C │ 10KB │
│24B │ │ 24B │ │
└────┴───────────────┴─────────────┴───────────────────────┘
Nodes A and C are tiny (24 bytes each).
They can fit in ANY small gap.
No need to find large contiguous regions.
The fixed-size node advantage:
When all allocations are the same size (like linked list nodes), freed slots can always satisfy new requests of the same type. This is why node-based structures are called fragmentation-friendly.
Fragmented Memory with Fixed-Size Slots:
┌────┬────┬────┬────┬────┬────┬────┬────┐
│Used│FREE│Used│FREE│Used│FREE│Used│FREE│ All slots 24 bytes
└────┴────┴────┴────┴────┴────┴────┴────┘
New linked list node (24 bytes)? Fits in ANY free slot!
No fragmentation problem—every hole matches the need.
The memory that arrays leave unusable (fragmented gaps) is exactly where linked structure nodes fit. In heavily fragmented heaps, linked lists can continue growing when arrays cannot be allocated at all.
Memory allocators employ sophisticated strategies to combat fragmentation. Understanding these strategies reveals both their power and their limits.
Common allocator strategies:
| Strategy | Description | Helps With | Limitation |
|---|---|---|---|
| Best-Fit | Find smallest free block that fits | Minimal waste per allocation | Slow search, creates tiny unusable gaps |
| First-Fit | Use first free block that fits | Fast allocation | Creates many medium-sized gaps |
| Size Classes | Separate pools for each size range | Efficient for common sizes | Wastes memory for rare sizes |
| Buddy System | Split/merge powers-of-2 blocks | Efficient merging of adjacent blocks | Internal fragmentation from rounding |
| Slab Allocation | Pre-allocate pools of fixed-size objects | Excellent for same-size objects | Only works when sizes are known |
Why allocators can't fully solve the problem:
They manage, not eliminate: Allocators minimize fragmentation but cannot prevent it when variable sizes are allocated and freed randomly.
Trade-offs exist: Strategies that reduce fragmentation often increase memory overhead (size classes), slow down allocation (best-fit), or require knowing sizes in advance (slab).
Arrays break assumptions: Many allocator optimizations assume most allocations are small. Large arrays bypass these optimizations and go directly to the OS, which has coarser-grained control.
Adversarial patterns: No allocator strategy defends against all allocation patterns. There always exist patterns that fragment any given allocator.
Production systems often use specialized allocators (jemalloc, tcmalloc, mimalloc) that handle fragmentation better than default allocators. But even the best allocator cannot make large contiguous allocations immune to fragmentation—the fundamental requirement remains.
We have explored the third fundamental limitation of arrays: their vulnerability to memory fragmentation. This isn't a temporary or fixable problem—it's an inherent consequence of requiring contiguous memory in a shared memory space.
What's next:
We've now examined three major array limitations: fixed size, expensive modifications, and fragmentation vulnerability. In the final page, we'll synthesize these limitations into a comprehensive understanding of what arrays fundamentally cannot do efficiently, setting up the motivation for linked structures in the next chapter.
You now understand how memory fragmentation limits large array allocations and why this problem worsens in long-running systems. This systemic limitation, combined with fixed sizes and expensive modifications, establishes why arrays alone cannot serve all data storage needs.