What is a Heap?
A heap is a memory management system that provides dynamic memory allocation services to applications. It sits as an abstraction layer between your application code and the operating system’s virtual memory manager, handling the complexity of memory allocation, tracking, and deallocation.
When you call heap functions like malloc(), HeapAlloc(), or the C++ new operator, you are requesting memory from a heap manager. The heap manager maintains pools of virtual memory and serves your requests efficiently without requiring direct OS calls for every allocation.
Why Do Heaps Exist?
Heaps exist to solve several fundamental problems with direct virtual memory management:
Problem 1: VirtualAlloc Granularity Limitations
The Windows VirtualAlloc() function, which is the primary way to obtain virtual memory, has significant granularity constraints:
- Commit Granularity: Memory must be committed in multiples of the page size (4 KB or 0x1000 bytes). Even if you need only 16 bytes, you must commit at least 4 KB.
- Reserve Granularity: Memory reservations must be aligned to 64 KB (0x10000 bytes) boundaries and rounded to 64 KB multiples.
This means using VirtualAlloc directly for small allocations would be extremely wasteful. Allocating 100 objects of 64 bytes each would require:
- Without heap: 100 * 4 KB = 400 KB committed (6,400 bytes used, 393,600 bytes wasted!)
- With heap: 6,400 bytes used from a single 4 KB or 8 KB commit (minimal waste)
Problem 2: Performance Overhead
VirtualAlloc is a system call that transitions from user mode to kernel mode. This context switch is expensive, typically taking hundreds to thousands of CPU cycles. For applications making thousands of small allocations, this overhead would be prohibitive.
The heap amortizes this cost by calling VirtualAlloc infrequently to obtain large regions of memory, then serving many small allocations from these regions without additional system calls.
Problem 3: Memory Management Complexity
Managing memory efficiently is complex. Applications would need to implement:
- Tracking which memory regions are free and which are in use
- Finding suitable free blocks for new allocations (allocation strategy)
- Merging adjacent free blocks to reduce fragmentation (coalescing)
- Splitting large free blocks when smaller allocations are requested
- Handling alignment requirements for different data types
- Managing metadata to track allocation sizes and boundaries
The heap manager provides all of this functionality transparently, freeing developers from reimplementing complex memory management for every application.
Problem 4: Thread Safety
In multi-threaded applications, memory allocation must be thread-safe. Multiple threads cannot simultaneously modify memory management data structures without synchronization. The heap manager implements this synchronization internally using locks or lock-free algorithms.
How Heaps Work
At a high level, heaps work by maintaining a pool of virtual memory obtained from VirtualAlloc():
- The heap reserves and commits large regions of memory (typically 1 MB segments)
- It subdivides these regions into smaller allocations as requested by the application
- Metadata structures track the state of each allocation (free or busy)
- Free lists organize available memory by size for quick allocation
- When memory is freed, it is returned to the free lists for reuse
- Adjacent free blocks may be coalesced to reduce fragmentation
Heap Memory Lifecycle
A typical heap allocation lifecycle looks like this:
// Application requests memory HANDLE heap = GetProcessHeap(); void* ptr = HeapAlloc(heap, 0, 256); // Heap manager: // 1. Searches free lists for suitable block // 2. If no suitable block exists, commits more memory // 3. Splits a larger block if necessary // 4. Returns pointer to application // 5. Updates internal metadata // Application uses the memory memset(ptr, 0, 256); // Application frees the memory HeapFree(heap, 0, ptr); // Heap manager: // 1. Marks block as free // 2. Attempts to coalesce with adjacent free blocks // 3. Adds block to appropriate free list // 4. May decommit memory if large regions are unused
Additional Heap Services
Beyond basic allocation and deallocation, heap managers provide additional services:
- Reallocation: Growing or shrinking existing allocations in place when possible (HeapReAlloc)
- Size Queries: Determining the size of an allocation (HeapSize)
- Heap Validation: Checking heap integrity to detect corruption (HeapValidate)
- Heap Walking: Enumerating all allocations for debugging (HeapWalk)
- Statistics: Providing information about heap usage and fragmentation
Types of Heaps in Windows
Windows provides several heap implementations:
- Process Heap: Every process has a default heap created at startup, accessible via GetProcessHeap()
- Additional Heaps: Applications can create additional heaps with HeapCreate() for specific purposes
- Low Fragmentation Heap (LFH): A specialized algorithm within the NT Heap for allocations under 16 KB
- Segment Heap: A newer heap implementation introduced in Windows 10, designed to replace the NT Heap
Heap Creation and Destruction
Applications can create private heaps for specific purposes:
// Create a private heap with 1 MB initial size
HANDLE myHeap = HeapCreate(
0, // Flags (0 = default behavior)
0x100000, // Initial committed size (1 MB)
0 // Maximum size (0 = growable)
);
// Use the heap
void* ptr = HeapAlloc(myHeap, 0, 128);
HeapFree(myHeap, 0, ptr);
// Destroy heap (frees all memory at once)
HeapDestroy(myHeap);
Private heaps are useful for:
- Isolating allocations for a subsystem that will be destroyed together
- Reducing contention in multi-threaded applications
- Enabling wholesale cleanup by destroying the entire heap at once
Benefits of Heap Abstraction
The heap abstraction provides critical benefits:
- Efficiency: Amortizes expensive VirtualAlloc calls across many allocations
- Flexibility: Supports arbitrary allocation sizes from bytes to gigabytes
- Simplicity: Simple API hides complex memory management details
- Performance: Optimized algorithms for common allocation patterns
- Safety: Metadata and validation help detect memory errors
- Scalability: Handles single-threaded and multi-threaded scenarios