Question 1201

Eight Megabytes Of Frames

A C++ DFS uses one stack frame per node. Built without optimization, each frame is 96 bytes: two 8-byte pointers, an int, an adjacency iterator, saved registers, and alignment padding. The thread runs with the common 8 MiB default stack.

How deep can the recursion go, and does a DFS over a 200,000-node path graph fit?

A

Effectively unbounded: Linux grows the main thread stack on demand, so 8 MiB is only an initial reservation.

B

About 87,000 frames, and it does not fit: the DFS reaches depth 200,000.

C

About 87,000 frames, but it fits, because DFS only keeps the current root-to-node path on the stack and a path graph is walked one node at a time.

D

About 1.05 million frames, so it fits comfortably: a call costs an 8-byte return address, and 8 MiB holds that many.