The real difference between the stack and the heap in C++ is the lifetime. The stack objects live until the end of their scope, and they are created and destroyed for free. The heap objects live until you explicitly release them, and creating them costs time. Everything else, which means the speed, the fragmentation and the overflow, follows from that one fact, and choosing correctly is one of the biggest performance levers that a C++ programmer has.
The previous lesson in this module covered "What Is RAII and Why Is It C++'s Core Habit?", and this lesson is the last one in the Memory and Smart Pointers module.
Two places for objects
A local variable lives on the stack. A new expression allocates on the heap.
#include <iostream>
int from_the_stack() {
int value = 42;
return value; // the stack frame disappears on return
}
int main() {
int local = 7;
std::cout << "local: " << local << '\n';
std::cout << "from a function: " << from_the_stack() << '\n';
int* dynamic = new int(42);
std::cout << "dynamic: " << *dynamic << '\n';
delete dynamic;
return 0;
}The output shows both of them alive at the same time.
local: 7
from a function: 42
dynamic: 42The storage of the local variable is reclaimed automatically. The dynamic one is not, which is why it needs a delete.
The stack is fast and automatic
Creating a stack object is a single adjustment of a pointer, and destroying it is another. There is no allocation, there is no free list, and there is no bookkeeping.
#include <chrono>
#include <iostream>
#include <vector>
int main() {
const int iterations = 200000;
auto start = std::chrono::steady_clock::now();
int total = 0;
for (int i = 0; i < iterations; ++i) {
int scratch = i * 2; // stack: created and destroyed each time
total += scratch;
}
auto middle = std::chrono::steady_clock::now();
for (int i = 0; i < iterations; ++i) {
int* scratch = new int(i * 2); // heap: allocated and freed each time
total += *scratch;
delete scratch;
}
auto finish = std::chrono::steady_clock::now();
auto stack_ms = std::chrono::duration_cast<std::chrono::milliseconds>(middle - start).count();
auto heap_ms = std::chrono::duration_cast<std::chrono::milliseconds>(finish - middle).count();
std::cout << "total: " << total << '\n';
std::cout << "stack loop: " << stack_ms << " ms\n";
std::cout << "heap loop: " << heap_ms << " ms\n";
return 0;
}The exact numbers depend on your machine, but the ordering is consistent. The heap loop takes many times longer, because every iteration pays for an allocation and a deallocation.
The heap is flexible
The heap is the right place when the size is not known until run time, when the object has to outlive the scope that it was created in, or when many objects share a lifetime that is not tied to any one scope.
#include <iostream>
#include <memory>
#include <string>
#include <vector>
struct Record {
int id;
std::string name;
};
int main() {
std::vector<std::unique_ptr<Record>> records;
for (int i = 0; i < 3; ++i) {
auto record = std::make_unique<Record>();
record->id = i;
record->name = "record " + std::to_string(i);
records.push_back(std::move(record));
}
for (const auto& record : records) {
std::cout << record->id << ": " << record->name << '\n';
}
return 0;
}The output shows the three records in order.
0: record 0
1: record 1
2: record 2The size of the collection was decided at run time, and the records are owned by the vector.
Stack overflow
The stack has a fixed size, usually a few megabytes. Recursing too deeply, or allocating a very large local array, overflows it.
#include <iostream>
int depth_reached = 0;
int recurse(int depth) {
depth_reached = depth;
if (depth > 100000) {
return depth;
}
return recurse(depth + 1);
}
int main() {
std::cout << "stopping at a safe depth\n";
std::cout << "depth: " << recurse(0) << '\n';
return 0;
}A recursion that runs away will eventually exhaust the stack and crash the process rather than return. The fix is to use the heap, to convert the recursion into a loop, or to bound the depth as it is done above. A large local array has the same problem.
#include <iostream>
int main() {
// 8 megabytes on the stack: usually far too much
static char big[8 * 1024 * 1024];
big[0] = 'x';
std::cout << "first byte: " << big[0] << '\n';
return 0;
}Declaring the array as static moves it to the static storage area instead of the stack. Better still, use a std::vector.
Fragmentation and the heap's other costs
The heap is not free. The allocators keep free lists of blocks and they reuse them, and over time the free lists become fragmented, which means that free blocks exist but none of them is large enough for the next request.
There is also the cost of the pointer itself, the indirection on every access, and the cache behaviour of the data that is not next to anything else that you are using. A std::vector of the small objects is usually faster than a vector of the pointers, because the objects are next to each other.
Choosing where an object lives
the situation where it goes
--------------------------------------- ----------------------------
the local variables and the temporaries the stack, always the default
the size is known at compile time the stack
the size is decided at run time the heap, through a container
or a smart pointer
the object has to outlive the scope the heap
the object is shared between the threads the heap, with care
the object is large the heap, so that the stack
does not overflow
Quick reference
- The difference is the lifetime. The stack ends with the scope, and the heap ends when you say so.
- The stack allocation is a pointer adjustment, and the heap allocation goes through the allocator.
- The local variables and the temporaries live on the stack.
- The containers and the smart pointers allocate on the heap, and they manage the lifetime for you.
- The deep recursion and the large local arrays overflow the stack.
- The heap costs time, memory and fragmentation, so use it only when you need it.
Try it yourself: write a function that builds a vector of a size that is read from the command line, filling it with the values, and returns it. Compare the time that it takes with a version that uses a fixed-size stack array. Then write a recursive function that walks a linked structure and change it to an iterative one, and check that the deep-recursion version fails while the loop version does not.