What is Memory Compaction?
Learn what memory compaction is, how it consolidates free holes into one region, and why relocation requires updating references.
Expected Interview Answer
Memory compaction is the process of relocating allocated memory blocks so that they sit contiguously, merging the scattered free holes left between them into one large contiguous free region, which fixes external fragmentation but requires updating every pointer or address reference to the moved blocks.
Over time, as variable-sized blocks are repeatedly allocated and freed in a contiguous memory region, free space becomes broken into many small holes interspersed between still-allocated blocks, even though the total free memory might be large. Compaction walks through memory, slides the allocated blocks toward one end (typically the low end), and leaves all the freed space combined as a single block at the other end, so a large request that previously could not be satisfied by any individual hole now fits. The catch is that moving a block invalidates any raw pointer or physical address that referred to its old location, so compaction is only feasible when the system can find and update all references — either because addresses are indirected through a level of relocatable handles/tables, or because the OS controls all outstanding references (as with process address spaces under virtual memory, where only page tables need updating, not application pointers). This is why compaction is common in managed runtimes (garbage collectors) and in relocating physical page allocators, but rare in raw, pointer-based kernel heaps where blind pointer chasing is not possible; instead, those use paging or the buddy/slab allocators to sidestep the problem rather than compact after the fact.
- Directly eliminates external fragmentation by consolidating free memory
- Enables satisfying large allocation requests that scattered holes previously blocked
- Works cleanly when addressing is indirected (handles, page tables, GC roots)
- Explains why paging and slab allocators are often preferred over compaction in kernels
AI Mentor Explanation
Memory compaction is like a stadium reshuffling scattered occupied seats — singles and pairs of fans dotted across a stand — by moving everyone to one contiguous section, so all the empty seats end up merged together at the other end for a big group booking. The catch is that every fan being moved needs their ticket updated to the new seat number, or ushers directing them would send people to the wrong place. This reshuffle takes real effort mid-match, which is why stadiums try to seat groups together up front rather than compact seating after the fact.
Step-by-Step Explanation
Step 1
Identify holes
Scan memory to find allocated blocks and the free holes scattered between them.
Step 2
Slide blocks
Move allocated blocks toward one end of memory, closing the gaps between them.
Step 3
Merge free space
Combine all the freed space left behind into a single large contiguous free region.
Step 4
Update references
Fix every pointer, handle, or page table entry that referred to a block’s old address so nothing breaks after the move.
What Interviewer Expects
- Clear explanation that compaction targets external fragmentation specifically
- Understanding that moving blocks requires updating all references to them
- Why compaction is feasible with indirected addressing (handles, page tables, GC) but hard with raw pointers
- Awareness of the runtime cost of compaction (a stop-the-world-style pause)
Common Mistakes
- Confusing compaction with paging or the buddy system
- Forgetting that compaction cannot fix internal fragmentation
- Not mentioning the pointer/reference update problem as the core challenge
- Assuming compaction is free or instantaneous
Best Answer (HR Friendly)
“Memory compaction is like tidying up a messy shelf by sliding all the items together to one side, so instead of small gaps everywhere, you get one big open space that can actually fit something large. The tricky part is that anything pointing at an item’s old spot needs to be updated once it moves, which is why compaction works well in systems that track references carefully, like garbage collectors, but is harder in low-level code with raw memory addresses.”
Code Example
struct block { void *addr; size_t size; int allocated; };
/* Slide all allocated blocks to the low end; merge freed space at the high end.
References array lets us fix up every pointer after a block moves. */
void compact(struct block *blocks, int n, void ***refs_per_block, char *heap) {
size_t write_offset = 0;
for (int i = 0; i < n; i++) {
if (!blocks[i].allocated) continue;
if (blocks[i].addr != heap + write_offset) {
memmove(heap + write_offset, blocks[i].addr, blocks[i].size);
update_all_references(refs_per_block[i], heap + write_offset);
blocks[i].addr = heap + write_offset;
}
write_offset += blocks[i].size;
}
/* everything from write_offset to end of heap is now one free region */
}Follow-up Questions
- Why is compaction rare in low-level kernel heaps with raw pointers?
- How do garbage-collected runtimes make compaction safe?
- Why does virtual memory avoid the need for compaction of physical memory?
- What is the performance cost of running compaction, and when is it triggered?
MCQ Practice
1. What problem does memory compaction primarily solve?
Compaction consolidates scattered free holes between allocated blocks into one contiguous region, directly fixing external fragmentation.
2. What is the main challenge when compacting memory?
Since blocks are physically relocated, anything referencing their old address must be updated, which requires either indirection or full knowledge of all references.
3. Why is compaction more common in garbage-collected runtimes than in raw kernel heaps?
A garbage collector knows every reference to an object (via roots and the object graph), making it safe to relocate objects and fix up references; raw kernel pointers offer no such guarantee.
Flash Cards
What is memory compaction? — Relocating allocated blocks to consolidate scattered free holes into one contiguous free region.
What fragmentation type does compaction fix? — External fragmentation, not internal fragmentation.
What is the main cost of compaction? — Every reference to a moved block’s old address must be found and updated.
Where is compaction commonly used? — Garbage-collected runtimes and relocatable physical page allocators.