Table of contents
Open Table of contents
Why Memory Matters
Memory is the most fundamental resource in computing. Every variable you declare, every object you create, every byte of data you process — it all lives in memory. And how you manage it determines whether your program runs in microseconds or milliseconds.
Here’s a mind-blowing fact: accessing data from L1 cache (~1 nanosecond) is 100,000x faster than accessing it from a hard disk (~10 milliseconds). That’s the difference between instant and noticeable.
Stack vs Heap: The Two Memory Worlds
The Stack: Fast and Organized
The stack is like a stack of plates — you can only add or remove from the top. It’s managed by the CPU hardware, making it incredibly fast.
void function() {
int x = 42; // Stack: 4 bytes
double y = 3.14; // Stack: 8 bytes
char name[50]; // Stack: 50 bytes
// All automatically freed when function returns
}Stack characteristics:
- Size: Typically 1-8 MB (Linux default: 8 MB)
- Speed: ~1 nanosecond (just moving a pointer)
- Lifetime: Tied to function scope
- Deallocation: Automatic (when function returns)
- Size must be known at compile time
Real-world analogy: The stack is like your desk. You put things on it while you’re working, and when you’re done, you clear everything at once. You can’t keep more on the desk than it can hold.
The Heap: Flexible and Slow
The heap is like a large warehouse — you can request any amount of memory at any time, but it takes more effort to manage.
void function() {
int* p = new int(42); // Heap: 4 bytes
double* arr = new double[1000]; // Heap: 8000 bytes
std::string* s = new std::string("hello"); // Heap: varies
// Must manually free when done
delete p;
delete[] arr;
delete s;
// Or use smart pointers (recommended)
auto p2 = std::make_unique<int>(42);
auto arr2 = std::make_unique<double[]>(1000);
}Heap characteristics:
- Size: Limited by available RAM (can be gigabytes)
- Speed: ~100 nanoseconds (malloc/free overhead)
- Lifetime: You control it
- Deallocation: Manual (or via garbage collection)
- Size can be determined at runtime
Stack Overflow
When you use too much stack space, you get a stack overflow:
void infinite_recursion() {
int data[1000000]; // 4MB on stack!
infinite_recursion();
}
// Or simply:
void large_arrays() {
int huge[10000000]; // 40MB — way too much for stack
}Error: “Segmentation fault” or “Stack overflow”
Solution: Use heap allocation for large data, or increase stack size (not recommended).
When to Use Which?
| Use Stack For | Use Heap For |
|---|---|
| Small, fixed-size data | Large data structures |
| Temporary variables | Data that outlives the function |
| Performance-critical code | Dynamic sizes |
| Simple types (int, float) | Complex objects (vectors, maps) |
Memory Layout of a C++ Program
When your program loads, the operating system divides memory into sections:
High Memory (0x7FFF...)
┌─────────────────────┐
│ Stack │ ← Grows downward
│ (local variables) │
│ │
│ ↓ │
│ ↑ │
│ ↑ │
│ Heap │ ← Grows upward
│ (dynamic memory) │
├─────────────────────┤
│ BSS │ ← Uninitialized global variables
├─────────────────────┤
│ Data │ ← Initialized global variables
├─────────────────────┤
│ Text │ ← Your program code (read-only)
└─────────────────────┘
Low Memory (0x0000...)int global_var = 42; // Data segment
static int static_var = 100; // Data segment
int uninitialized_global; // BSS segment
int main() {
int stack_var = 10; // Stack
int* heap_var = new int(20); // Heap
return 0;
}Virtual Memory: The Illusion of Infinite RAM
Virtual memory is one of the most elegant concepts in computing. It gives each program the illusion of having its own private address space, even though they all share physical RAM.
How It Works
Program's Virtual Address Space:
┌─────────────────┐
│ 0x0000...0000 │
│ │
│ Virtual Page 0 │ → Physical Frame 5
│ Virtual Page 1 │ → Physical Frame 2
│ Virtual Page 2 │ → On disk (swapped out)
│ Virtual Page 3 │ → Physical Frame 8
│ │
│ 0xFFFF...FFFF │
└─────────────────┘The page table maps virtual pages to physical frames:
Virtual Page 0 → Physical Frame 5
Virtual Page 1 → Physical Frame 2
Virtual Page 2 → Disk (swapped)
Virtual Page 3 → Physical Frame 8Page Faults
When a program accesses a page that’s not in physical RAM, a page fault occurs:
1. Program accesses virtual address
2. MMU (Memory Management Unit) checks page table
3. Page not in RAM → Page fault!
4. OS finds the page on disk
5. OS loads page into a free frame
6. OS updates page table
7. Program resumes (it doesn't even know this happened)Real-world impact: Page faults are expensive — ~10 milliseconds each. That’s 10 million times slower than a cache hit. This is why “working set” (the pages your program actively uses) matters so much.
Swap Space
When physical RAM is full, the OS moves less-used pages to disk (swap space):
Physical RAM (8 GB):
┌─────────────────────────────────┐
│ Active pages (6 GB) │
│ Less active pages (2 GB) │
└─────────────────────────────────┘
↓ When RAM is full
Swap Space on Disk (8 GB):
┌─────────────────────────────────┐
│ Swapped-out pages │
└─────────────────────────────────┘Warning: Heavy swapping = terrible performance. If your system is swapping constantly, you need more RAM.
Memory-Mapped Files
Virtual memory enables memory-mapped files — treating files as if they’re in memory:
#include <sys/mman.h>
#include <fcntl.h>
int fd = open("data.bin", O_RDONLY);
void* mapped = mmap(NULL, fileSize, PROT_READ, MAP_PRIVATE, fd, 0);
// Now you can access the file like a pointer
char firstByte = ((char*)mapped)[0];
// No read() syscall needed — the OS handles page faults
munmap(mapped, fileSize);
close(fd);Why it’s fast: The OS loads pages on-demand via page faults, avoiding the need to read the entire file upfront.
Cache: The Speed Multiplier
Cache is small, fast memory that sits between the CPU and RAM. It stores recently accessed data and nearby data (spatial locality).
The Cache Hierarchy
┌─────────────────────────────────────────────────────────┐
│ CPU Registers │
│ (0.3 ns, ~1 KB) │
├─────────────────────────────────────────────────────────┤
│ L1 Cache │
│ (1 ns, 32-64 KB) │
├─────────────────────────────────────────────────────────┤
│ L2 Cache │
│ (3-5 ns, 256 KB - 1 MB) │
├─────────────────────────────────────────────────────────┤
│ L3 Cache │
│ (10-20 ns, 8-32 MB) │
├─────────────────────────────────────────────────────────┤
│ Main Memory (RAM) │
│ (100 ns, 8-64 GB) │
├─────────────────────────────────────────────────────────┤
│ SSD │
│ (10,000 ns, 256 GB - 4 TB) │
├─────────────────────────────────────────────────────────┤
│ HDD │
│ (10,000,000 ns, 1-20 TB) │
└─────────────────────────────────────────────────────────┘Cache Lines
Cache doesn’t store individual bytes — it stores cache lines (typically 64 bytes):
Cache Line (64 bytes):
┌─────────────────────────────────────────────────────────┐
│ byte 0 │ byte 1 │ byte 2 │ ... │ byte 63 │
└─────────────────────────────────────────────────────────┘
↑
Your data is hereWhen you access arr[0], the cache loads arr[0] through arr[15] (assuming 4-byte integers). Accessing arr[1] through arr[15] is essentially free — they’re already in cache.
Real-world impact: This is why array traversal is fast (sequential access) but linked list traversal is slow (pointer chasing, poor spatial locality).
Cache-Friendly Code
// Bad: Column-major traversal (jumping in memory)
int matrix[1000][1000];
for (int j = 0; j < 1000; j++) {
for (int i = 0; i < 1000; i++) {
sum += matrix[i][j]; // Jumping 4000 bytes each time
}
}
// Good: Row-major traversal (sequential access)
for (int i = 0; i < 1000; i++) {
for (int j = 0; j < 1000; j++) {
sum += matrix[i][j]; // Sequential, cache-friendly
}
}Why it matters: Column-major traversal causes a cache miss on almost every access. Row-major traversal causes a cache miss every 16 accesses (64 bytes / 4 bytes per int).
Cache Miss Types
Cold Miss: First access to a cache line (unavoidable)
Conflict Miss: Two addresses map to same cache set (can be mitigated)
Capacity Miss: Working set larger than cache (need more cache)Memory Allocators
How you allocate memory matters more than you think.
malloc/free (C-style)
void* p = malloc(1024); // Allocate 1024 bytes
free(p); // Free
// Problems:
// - No type safety
// - Manual size tracking
// - Easy to forget to free (memory leak)
// - Easy to use after free (undefined behavior)new/delete (C++)
int* p = new int(42); // Allocate and construct
delete p; // Destruct and free
int* arr = new int[100]; // Allocate array
delete[] arr; // Free array
// Better, but still manualSmart Pointers (Modern C++)
// Unique pointer: sole ownership
auto p = std::make_unique<int>(42);
// Automatically freed when p goes out of scope
// Shared pointer: reference counting
auto p1 = std::make_shared<int>(42);
auto p2 = p1; // Reference count = 2
// Freed when last reference is destroyed
// Weak pointer: non-owning reference
std::weak_ptr<int> wp = p1;
// Doesn't increase reference countCustom Allocators
For performance-critical code, you might want a custom allocator:
// Arena allocator: allocate fast, free everything at once
class Arena {
std::vector<char> buffer;
size_t offset = 0;
public:
void* allocate(size_t size) {
void* ptr = buffer.data() + offset;
offset += size;
return ptr;
}
void reset() {
offset = 0; // Free everything at once
}
};
// Usage:
Arena arena;
int* p = (int*)arena.allocate(sizeof(int));
*p = 42;
// Don't need to free individual allocations
arena.reset(); // Free everything at onceReal-world use: Game engines, compilers, and databases often use arena allocators for performance.
Memory Leaks: The Silent Killer
A memory leak is when you allocate memory but never free it:
void leak() {
int* p = new int[1000];
// Forgot to delete[] p!
// Memory is leaked when function returns
}
// Over time, leaked memory accumulates
// Eventually: Out of memory → crashDetecting Leaks
# Linux/Mac: valgrind
valgrind --leak-check=full ./my_program
# Output:
# definitely lost: 4000 bytes in 1 blocks
# indirectly lost: 0 bytes in 0 blocks
# possibly lost: 0 bytes in 0 blocksPreventing Leaks
// Rule 1: Use RAII (Resource Acquisition Is Initialization)
{
auto p = std::make_unique<int[]>(1000);
// Automatically freed when scope ends
}
// Rule 2: Prefer stack allocation
void good() {
int arr[100]; // Stack, automatically freed
}
// Rule 3: Use containers instead of raw arrays
std::vector<int> vec(100); // Automatically manages memoryPractical Performance Tips
1. Minimize Dynamic Allocation
// Bad: Allocate in a loop
for (int i = 0; i < 1000000; i++) {
std::string s = "hello"; // Heap allocation each iteration
}
// Good: Pre-allocate
std::string s;
s.reserve(1000000); // Pre-allocate
for (int i = 0; i < 1000000; i++) {
s = "hello"; // No allocation
}2. Use Reserve for Containers
// Bad: Vector grows dynamically (multiple reallocations)
std::vector<int> vec;
for (int i = 0; i < 1000000; i++) {
vec.push_back(i); // May reallocate multiple times
}
// Good: Reserve upfront
std::vector<int> vec;
vec.reserve(1000000); // One allocation
for (int i = 0; i < 1000000; i++) {
vec.push_back(i); // No reallocation
}3. Avoid Cache Thrashing
// Bad: Random access pattern
std::unordered_map<int, int> map;
for (int i = 0; i < 1000000; i++) {
map[i] = i; // Random memory locations
}
// Good: Sequential access pattern
std::vector<int> vec(1000000);
for (int i = 0; i < 1000000; i++) {
vec[i] = i; // Sequential, cache-friendly
}Conclusion
Memory management is one of the most important skills for performance-critical programming. Understanding stack vs heap, virtual memory, cache hierarchy, and allocators gives you the tools to write fast, efficient code.
The key insights:
- Stack is fast, heap is flexible — use the right one for the job
- Virtual memory gives you infinite RAM — but page faults are expensive
- Cache is everything — optimize for locality
- Use smart pointers — avoid manual memory management
- Profile before optimizing — measure, don’t guess
The next time your program is slow, check the memory first. It’s usually the bottleneck.