Stack ADT & Call Stack Memory lab report

1. Title and aim

Empirical Analysis of the Stack Abstract Data Type: LIFO Semantics, Expression Parsing, and Call Stack Memory Consumption. Determine the physical activation record frame size F_frame from empirical call stack memory allocation across recursive execution depths.

2. Abstract

Seven benchmark trials were generated across recursive call depths n = 128 to n = 8192 frames (peak virtual thread stack allocation from 8320 bytes to 524416 bytes, or 512.12 KiB). An ordinary least-squares regression of peak stack memory M against recursion depth n yielded an empirical activation record frame size of 64.0000 bytes/frame, demonstrating exact agreement with the standard System V AMD64 ABI specification (difference = 0.0000%). The empirical telemetry proves that unoptimized linear recursion incurs strict O(n) auxiliary memory overhead, consuming memory bus bandwidth and risking fatal Stack Overflow (SIGSEGV) exceptions once depth exceeds the operating system thread stack limit, whereas Tail-Call Optimization (TCO) and explicit heap-allocated stacks eliminate unbounded hardware stack pointer growth.

3. Apparatus and fixed settings

• Virtual Thread Call Stack: Hardware-coordinated virtual memory segment growing toward lower addresses, governed by the RSP stack pointer and RBP base pointer registers.
• Activation Record Allocator: Microarchitectural call frame generator allocating 64-byte structured records containing return address, saved frame pointer, registers, and local variable slots.
• LIFO Operation Comparator: High-precision computational state monitor tracking push, pop, and peek transaction latencies and stack watermark depth.
• MMU Guard Page Watchdog: Hardware memory management unit boundary monitor detecting out-of-bounds stack pointer violations and triggering kernel SIGSEGV signals on overflow.
• Shunting-Yard Syntax Engine: Deterministic context-free grammar parser employing dual operand and operator stacks to validate balanced delimiters and evaluate infix arithmetic.
• Stack Watermark Profiler: Non-intrusive runtime telemetry instrumentation measuring peak byte displacements of the RSP stack pointer register relative to thread base.
• Thread execution stack allocated in private virtual address space with default 8 MiB limit and 4 KiB guard page.
• Standard System V AMD64 ABI activation record layout: 64 bytes per frame including return address, saved RBP, registers, and local slots.

4. Theory and graph choice

The Stack Abstract Data Type (ADT) is a fundamental linear data structure characterized by strict Last-In-First-Out (LIFO) semantics, where insertions (push) and removals (pop) occur exclusively at a single designated terminal location termed the top of the stack. Beyond application-level data storage, the Stack ADT forms the foundational hardware and operating system mechanism for managing program control flow, function call invocation, nested syntactic parsing, and recursive algorithm execution. In modern computer architectures, every running thread is allocated a private virtual memory segment known as the call stack, which grows downward toward lower memory addresses under the control of the hardware stack pointer register (RSP). Each function invocation allocates an Activation Record (or stack frame) containing the caller’s return instruction pointer, saved base pointer (RBP), callee-preserved registers, and local variable slots. While linear recursion provides elegant mathematical formulations for algorithmic problems, unoptimized recursive functions consume strict O(n) stack memory, creating significant memory bus churn and exposing software to fatal Stack Overflow exceptions once recursion depth breaches the operating system stack quota. This laboratory investigation combines virtual machine register telemetry, call stack memory profiling, and syntactic pushdown automata to measure physical activation record consumption, evaluate Tail-Call Optimization (TCO), and establish the microarchitectural boundaries of recursive computation.

The mathematical regression fits the linear model y = mx + b, where x = n represents the recursive call stack depth in frames, y = M represents peak memory consumption in bytes, m represents the physical activation record frame size F_frame, and b represents the initial runtime startup CRT stack overhead M_0 (theoretically M_0 = 128 bytes). The gradient has physical units bytes/frame.

5. Method

1. Configure the virtual machine runtime with standard 16-byte stack boundary alignment and verify that the base runtime startup frame M_0 is recorded at exactly 128 bytes.
2. Adjust the independent variable control slider to choose a target recursion depth n between 128 and 8,192 frames across the designated power-of-two benchmark points.
3. Trigger the recursive execution engine, initiating sequential CALL instructions that push return addresses, establish RBP frame links, and decrement the RSP register by 64 bytes per frame.
4. Upon reaching the base-case conditional termination, read the maximum byte displacement M = 64n + 128 bytes from the MMU telemetry profiler before unwinding the call stack.
5. Commit the independent depth n (frames) and dependent memory allocation M (bytes) into the laboratory notebook table and plot the corresponding data coordinate.
6. Construct the ordinary least-squares regression line M = F_frame · n + M_0 across all seven benchmark trials to extract the physical frame size F_frame and verify agreement with the ABI standard.

6. Observations and calculation table

All benchmark observations use strictly controlled memory buffers. Values are recorded deterministically from the algorithmic comparator register. Residuals are computed relative to the ordinary least-squares regression line.

Download the sample observations (CSV) ↓

7. Worked calculation for one observation

8. Graph, gradient and final calculation

Circular markers represent empirical benchmark observations. The solid line represents the ordinary least-squares asymptotic linear fit.

9. Uncertainty and comparison

Percentage difference = |estimate − theoretical value| / |theoretical value| × 100 = 0.0000%.

For n = 7 benchmark observations, Σresidual² = 0.00000; s² = Σresidual²/(n − 2). Gradient standard error = √[s²/Σ(x − x̄)²] = 1.3905e-10. Intercept standard error = √[s²(1/n + x̄²/Σ(x − x̄)²)] = 4.9712e-07.

Propagating the fit parameters yields a fit standard error of 1.3905e-10 bytes/frame, with an ideal coefficient of determination R² = 1.000000.

In microarchitectural call stack memory analysis, the activation record size F_frame = 64 bytes per frame under the System V AMD64 ABI is an exact deterministic specification. Unlike continuous physical instrumentation, there is no analog sensor noise, thermal fluctuation, or calibration drift in measuring discrete byte displacements of the hardware stack pointer RSP. However, in physical microprocessor execution, observable call stack latency and operating system memory footprint are modulated by hardware and kernel mechanisms: (1) Virtual memory demand paging and Translation Lookaside Buffer (TLB) misses, where physical 4 KiB memory pages are committed only when the stack pointer crosses a page boundary; (2) CPU L1 data cache line fills and dirty writeback traffic, as stack pushes write to memory lines while stack pops invalidate or reuse warm cache lines; (3) Compiler optimizations such as leaf function frame elision, tail-call elimination (which reuses the current frame instead of allocating a new one), and register variable allocation; and (4) Operating system stack canary guard pages, which trigger a kernel page fault (SIGSEGV) if stack depth expands beyond the designated thread memory quota (typically 8 MiB). Ordinary least-squares linear regression of peak stack memory allocation against recursion depth n in [128, 8192] frames yields an empirical frame scaling slope F_frame = 64.0000 bytes/frame with zero residual error (R² = 1.00000), verifying the linear call stack memory bound Θ(n) with mathematical precision.

10. Result and discussion

The empirical benchmark observations perfectly align with the hardware architecture of the thread call stack. Each function invocation executes the machine instruction CALL, pushing the 8-byte instruction return address onto the stack, followed by the function prologue (`push rbp; mov rbp, rsp; sub rsp, 48`), resulting in a constant 64-byte activation record per invocation level. The regression slope m = 64.0000 confirms that stack memory grows linearly at exactly 64 bytes per recursion depth. Furthermore, comparative analysis across execution paradigms reveals the crucial distinction between recursion classes: while linear recursion requires O(n) activation records, divide-and-conquer tree recursion bounds peak stack depth to O(log n) frames, and tail-recursive functions can be compiled via Tail-Call Optimization into constant-space O(1) iterative jumps (`jmp`), completely neutralizing stack overflow vulnerability. Finally, the grammar parser experiment demonstrates the essential role of the Stack ADT in compiling and evaluating nested syntax trees, maintaining LIFO state invariants across arbitrary context-free grammars.

11. Precautions and limitations

• Always define and rigorously test base-case termination conditions prior to executing recursive procedures to prevent infinite recursion and catastrophic thread stack exhaustion.
• Be vigilant of hidden deferred operations in recursive return statements (e.g., n * rec(n - 1)); deferred operations prevent compiler Tail-Call Optimization (TCO) and force O(n) activation frame allocation.
• Avoid allocating large local arrays or buffers on the call stack within recursive functions; allocate large working memory buffers on the heap to prevent premature stack overflow.
• When profiling thread stack memory in production environments, account for operating system guard page alignment (typically 4096-byte boundaries) and compiler-dependent red zone allocations.

The simulated execution model evaluates idealized thread call stack memory allocation under the System V AMD64 ABI specification with fixed 64-byte activation frames and an initial 128-byte runtime CRT base frame. In physical hardware, virtual memory pages (typically 4096 bytes) are committed by the operating system kernel on-demand via page fault demand paging, meaning physical RAM allocation increases in discrete page steps rather than continuous byte increments. Furthermore, modern optimizing compilers employ aggressive function inlining, leaf-function frame elision, and register parameter passing that can reduce or eliminate activation records for small functions, while debug builds with stack canaries and sanitizers (e.g., AddressSanitizer ASan) increase frame footprints significantly. The simulated benchmark environment reflects strict x86-64 System V AMD64 ABI memory alignment rules, where each activation record consumes exactly 64 bytes of thread stack memory (8 bytes return address, 8 bytes saved RBP, 16 bytes callee-saved registers, and 32 bytes local variable allocation and stack alignment padding). An initial 128-byte base frame represents the runtime C-runtime (CRT) startup wrapper. Consequently, peak stack allocation follows the exact linear relationship M(n) = 64.0000 · n + 128.0000 bytes, providing an ideal microarchitectural testbed for Ordinary Least-Squares regression.

12. Conclusion

This laboratory investigation quantitatively verified the memory architecture, activation record mechanics, and asymptotic behavior of the Stack Abstract Data Type. Through systematic benchmarking across recursion depths from 128 to 8192 frames, we verified the empirical frame size F_frame = 64.0000 bytes/frame with an ideal coefficient of determination R² = 1.00000. The investigation established the microarchitectural necessity of stack memory discipline, proving how unbounded recursion risks thread stack exhaustion and validating tail-call optimization and heap-backed data structures as vital engineering defenses in modern software runtimes.