Let’s jump right in; the answer and explanation are hidden after the code.
Assuming all allocations succeed, can the following function still crash? Why?
1#include <memory>
2
3struct Node {
4 std::shared_ptr<Node> next;
5};
6
7void example(int n) {
8 std::shared_ptr<Node> head;
9 for (int i = 0; i < n; i++)
10 head = std::make_shared<Node>(Node{head});
11}
Yes, it can crash. If n is too big, this function can overflow the stack.
The tricky part is that I have not shown you the offending code. It is the
std::shared_ptr destructor, which eventually calls the Node destructor,
which recursively destructs the next shared pointer.
The shared_ptr destructor is implicitly invoked at the end of example() when
head goes out of scope. shared_ptr is standard library code. And Node’s
destructor is also implicitly generated. None of this is shown in the code
snippet above.
What surprised me is that the limit of how many nodes can be handled successfully can vary dramatically depending on the specific setup, the most important factors being the compiler optimization level and the available stack size.
On macOS using clang (8 MiB stack):
| Build Configuration | Max n |
Stack Space per Node |
|---|---|---|
| Debug (-O0 -g) | 22 732 | 368 bytes |
| Release (-O3) | 261 426 | 32 bytes |
Stack sizes can be dynamically adjusted at various levels (operating system / application / individual thread), but even the typical defaults vary drastically between platforms.
| Operating system | Main thread | New threads (std::thread / pthread) |
|---|---|---|
| Linux | 8 MiB | 8 MiB |
| Windows | 1 MiB | 1 MiB |
| macOS | 8 MiB | 512 KiB |
Running the same code on a macOS std::thread worker thread yields:
| Build Configuration | Max n |
|---|---|
| Debug | 1 456 |
| Release | 16 758 |
There is an 11.5x factor between optimization levels in these macOS measurements, and an additional 8x-16x variation in default stack sizes across the platforms and thread types above. On macOS, running on the main thread in a release binary can handle about 180 times as many nodes as running on a worker thread in a debug binary.
For reference, here are the measured values on Windows and Linux:
| Build Configuration | Windows (MSVC 2019, 1 MiB stack) | Linux (GCC 16.1, 8 MiB stack) |
|---|---|---|
| Debug | ~3 060 nodes (~340 B/node) | ~23 800 nodes (~352 B/node) |
| Release | ~21 460 nodes (~49 B/node) | ~261 900 nodes (~32 B/node) |
Debug builds using this pattern might only be able to handle a couple thousand items. That is definitely not what I would expect of modern software.
Investigating this has given me a deeper appreciation for why guidelines for safety-critical software (e.g. JPL’s Power of 10 rules, MISRA C) do not allow recursion.
In conclusion, I think understanding systems on a deep technical level is critical for good software engineering, as are testing and knowing the limits of your code. In the age of AI, agents can not only help you build features quicker, but they are also great assistants for learning and quick experimentation.