Recursive DFS III: Hyper-Dimensional Depth

In Part 2, we unlocked Tail Call Optimization and hit 2.1 billion recursive calls before slamming into C#'s maximum array size limit. That should have been the end of the experiment.

Then it hit me: the call stack wasn't stopping us anymore—only our data structures were. So we stripped those away too, down to a single bit per node. When we ran it again, the recursion didn't stop at 10 billion, or 100 billion. It just kept eating through our 192 GB of DDR5 RAM until the machine literally had no memory left to give. Yes, that's right—recursion all the way through. No iterations, no loops in C#—just a pure, elegant recursive expression. Welcome to Hyper-Dimensional Depth.

How Is This Even Possible? (Where We Left Off)

In C#, recursion is supposed to crash with a StackOverflowException after ~10,000 calls. You're told that if you want to scale, you have to rewrite your recursive function into an iterative while loop.

Why? Because in standard recursion, every time Dfs() calls itself, the CPU has to pause the current call, save its state, and wait for the child call to return. Those paused frames pile up on the Thread Stack—which is only 1 MB by default. Once that 1 MB fills up, it overflows and crashes.

Instead of giving up on recursion, we chipped away at every bottleneck step by step:

• In Part 1: We shrank our nodes from classes to struct, replaced HashSet<T> with bool[], and expanded the Thread Stack to ~2 GB. That took us from ~10,000 calls to 30 million.
• In Part 2: We stripped out List<int>, generics, and foreach so each stack frame took only ~48 bytes (return nodes.DfsRecursiveLinear(next, visited) + 1;). That pushed us to 44.72 million calls—where 44.72M × 48 bytes completely filled the 2 GB Thread Stack and threw StackOverflowException again.
• The TCO Breakthrough (Part 2): Why was the CPU still stacking frames? Only because of that + 1 at the end—every call had to stay paused on the Thread Stack waiting to add 1 when the child returned. When we removed the return value, the hatch released:

// Part 2: 2.1 Billion (limited by array size)
public static void DfsRecursiveLinear(
    this NodeLinear[] nodes,
    int index,
    bool[] visited)
{
    if ((uint)index >= (uint)nodes.Length || visited[index])
        return;

    visited[index] = true;

    int next = nodes[index].NextIndex;
    if (next >= 0)
        nodes.DfsRecursiveLinear(next, visited); // <-- Tail position: nothing left to do after!
}

Because the recursive call was now the very last instruction, the compiler triggered Tail Call Optimization (TCO)—which is technically an anomaly! Officially, C# does not support or document TCO (the Roslyn C# compiler doesn't even emit .tail IL instructions, so you're not supposed to be able to trigger it from C#). Yet under these exact conditions, the JIT/AOT compiler secretly rewrote the recursion into a jmp instruction in CPU registers—reusing the same single stack frame forever instead of pushing a new frame onto the Thread Stack.

Suddenly, the Thread Stack stopped growing. We tested 60 million... 100 million... 500 million... all the way to 2.1 billion calls.

Shifting From the Stack to the Heap

As we pushed past hundreds of millions of calls with TCO, we noticed something interesting: we were now able to use more and more system memory (the Heap).

With the Thread Stack out of the way (0 bytes added per call), the only memory growing was our nodes[] and visited[] arrays on the Heap. And at 2.1 billion, we didn't stop because of recursion—we stopped because of three data-structure limits on the Heap:

• NodeLinear[] - C# arrays on the Heap cap at ~2.1B elements (and already used 17 GB of RAM)
• bool[] - Another 2.1B element array on the Heap
• int indices - Max value of ~2.1B

But here's the thing: TCO itself has no limit. It's just a jmp instruction. Once we realized the limit was no longer the call stack—the limit was in the memory itself—we stripped our Heap data structures down to the bone.

The Stripping: Piece by Piece 🔪

To break past 2.1 billion calls and let TCO run until it exhausted all 192 GB of physical RAM, we had to eliminate every one of those three bottlenecks from our Part 2 implementation (NodeLinear[] nodes, int index, and bool[] visited). Here is how we stripped them away one by one:

1. Kill the NodeLinear[] Array on the Heap

In Part 1 and Part 2, to force Depth-First Search into its worst-case recursion depth (where visiting N nodes requires N deep recursive calls with zero early backtracking), our benchmark graph was a single continuous linear chain (Node 0 → Node 1 → Node 2 → … → Node N-1).

In Part 2, we represented that chain by allocating a massive NodeLinear[] array on the Heap, where each struct was 8 bytes (two 4-byte int fields) and every slot i simply stored NextIndex = i + 1:

• At 2.14 billion nodes (Part 2): 2,147,483,591 nodes × 8 bytes = 17.18 GB of Heap RAM—AND it slammed straight into C#'s maximum single-array limit (Array.MaxLength).
• At 1.52 trillion nodes (Part 3): Even if C# allowed it, storing a NodeLinear struct with 64-bit long fields (16 bytes per node) would require 1.52T × 16 bytes = 24.32 Terabytes of RAM!

Look closely at what nodes[index].NextIndex was actually doing on every recursive call: we were reading 8 bytes from DRAM just to look up slot index and get back index + 1. For a linear chain, we don't need to store edges in a Heap array at all—the next node's address is always index + 1, computed on the fly in a single CPU register instruction (inc rdi) with 0 bytes of RAM:

// ❌ BEFORE (Part 2): 8 bytes per node on the Heap (17.18 GB at 2.14B, capped at Array.MaxLength)
public struct NodeLinear
{
    public int Value;      // 4 bytes
    public int NextIndex;  // 4 bytes (always initialized to i + 1)
}

public static void DfsRecursiveLinear(this NodeLinear[] nodes, int index, bool[] visited)
{
    if ((uint)index >= (uint)nodes.Length || visited[index]) return;
    visited[index] = true;

    int next = nodes[index].NextIndex; // <-- 17 GB Heap lookup just to read (index + 1)!
    if (next >= 0)
        nodes.DfsRecursiveLinear(next, visited);
}

// ✅ AFTER (Part 3): NodeLinear[] array is GONE (0 bytes of RAM).
// The edge transition (index + 1) happens directly inside CPU register RDI:
public static void DfsLinear(int index, int maxDepth, bool[] visited)
{
    if (index >= maxDepth || visited[index]) return;
    visited[index] = true;

    DfsLinear(index + 1, maxDepth, visited); // <-- Procedural edge: 17 GB of RAM eliminated!
}

2. Upgrade from 32-Bit int to 64-Bit long Indices

Even with NodeLinear[] gone, passing int index and int maxDepth still traps us at the 32-bit signed integer ceiling: int.MaxValue = 2,147,483,647 (2³¹ − 1). The moment index + 1 increments past 2,147,483,647, a 32-bit signed int wraps around to -2,147,483,648.

By upgrading index and maxDepth from 32-bit int (Int32) to 64-bit long (Int64), our node counter widens to a full 64-bit CPU register (RDI and RSI on x86-64) with a maximum value of 9,223,372,036,854,775,807 (9.22 Quintillion nodes)—over 4.29 billion times larger than int.MaxValue:

// ❌ 32-bit signed int:  caps at             2,147,483,647 (~2.14 Billion)
// ✅ 64-bit signed long: caps at 9,223,372,036,854,775,807 (~9.22 Quintillion)
public static void DfsLinearLong(long index, long maxDepth, ChunkedBitArray visited)

3. Borrowing the Heap & Mapping ChunkedBitArray Bit-by-Bit

Now only visited remains on the Heap. Our goal here was to push as close to our 192 GB maximum system memory as physically possible. When we initially ran this on Windows, desktop OS overhead limited us to 1 trillion stack frames (~119 GB)—but when we switched to headless Linux, we were able to go even further, pushing all the way to 1.52 trillion stack frames and getting much closer to the 192 GB of memory we had available (more details on that later).

To reach that scale, we had to solve two fundamental memory problems:

Problem 1: Byte Addressing vs. Bit Addressing (1.52 TB vs. ~177 GiB / 190 GB)

Even though a visited flag is just 0 or 1, CPUs cannot address individual bits in RAM—the smallest addressable unit of memory is 1 byte (8 bits). Because of that, a standard C# bool[] uses 1 full byte per node, wasting the other 7 bits:

By packing 64 nodes into each 64-bit ulong (1 bit per node), we get an 8x compression—shrinking 1.52 trillion nodes from an impossible 1.52 TB down to 190 GB decimal (176.96 GiB binary), getting us as close as physically possible to our 192 GB of system memory once the OS kernel and .NET runtime are accounted for.

Problem 2: You Cannot Allocate One Continuous Array Across ~190 GB in Managed C#

Even after packing 64 nodes into each ulong, 1.52 trillion nodes still requires: 1,520,000,000,000 bits ÷ 64 bits/ulong = 23,750,000,000 ulong elements (23.75 Billion).

In C#, every managed array is indexed by a signed 32-bit int and hard-capped at Array.MaxLength = 2,147,483,591 elements (~2.14B). You cannot allocate a single continuous new ulong[23_750_000_000] on the .NET Heap!

The Solution: 3-Level Bit-Addressing Across 1,416 Heap Chunks (ulong[][])

To span nearly all of our 192 GB of system memory without hitting C#'s single-array cap, we built ChunkedBitArray (ulong[][] _chunks)—a 2D jagged array that slices the Heap into 128 MiB chunks:

• Each chunk holds 1 << 30 (230 = 1,073,741,824) bits (~1.07 billion nodes).
• Divided by 64 (26) bits per ulong, each chunk is a ulong[16,777,216] array = 134,217,728 bytes (128 MiB)—safely below .NET's 2 GB per-array limit.
• On Windows (1.00 trillion nodes), _chunks allocated 932 chunks (~119 GB). On headless Linux (1.52 trillion nodes), it scaled all the way to 1,416 chunks (_chunks[0] through _chunks[1415] = 176.96 GiB / 190 GB).

Normally, converting a flat index into a 2D chunk, word, and bit position requires integer division (/) and modulo (%)—and hardware integer division (idiv) is one of the slowest instructions on an x86 CPU (~15–40 cycles). Because we sized our chunks (230 bits) and words (26 bits) to exact powers of two, the binary bits of long index ARE the address! We slice the 64-bit integer into three bit-fields using 1-cycle shifts (>>) and bitwise masks (&):

1. Find the 128 MiB Chunk (int chunk = (int)(index >> 30)): Shifting index right by 30 bits discards the lower 30 bits (0..29). In binary, >> 30 is exact integer division by 2³⁰ (1,073,741,824). Every time index crosses another 1,073,741,824 nodes, chunk increments by 1—stepping from _chunks[0] all the way to _chunks[1415].
2. Mask the Offset Inside That Chunk (int bitIndex = (int)(index & 0x3FFFFFFF)): ChunkMask = (1 << 30) - 1 = 0x3FFFFFFF, which in binary is thirty 1s. Bitwise ANDing index & 0x3FFFFFFF strips off the chunk number in bits 63..30 and leaves only the bottom 30 bits—the exact remainder index % 1,073,741,824 (0 to 1,073,741,823).
3. Find the 64-Bit ulong Word (int word = bitIndex >> 6): Each ulong holds 64 = 2⁶ bits. Shifting bitIndex right by 6 bits (>> 6) divides by 64, extracting Bits 29..6—giving us the exact array slot 0 .. 16,777,215 inside _chunks[chunk].
4. Flip the Exact Bit Inside That ulong (int bit = bitIndex & 63; ... |= (1UL << bit)): 63 in binary is six 1s (111111). Masking bitIndex & 63 extracts Bits 5..0 (0 to 63). Then 1UL << bit shifts a single 1 into that exact bit slot, and |= flips that bit inside _chunks[chunk][word] without disturbing the other 63 nodes sharing the same ulong!

// ChunkedBitArray: 1 bit per node, scales right up to max system memory with 0 GC
public class ChunkedBitArray
{
    private const int BitsPerChunk = 1 << 30;       // 1,073,741,824 bits (128 MiB) per chunk
    private const int ChunkMask = BitsPerChunk - 1; // 0x3FFFFFFF (lowest 30 bits)
    private readonly ulong[][] _chunks;

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public bool Get(long index)
    {
        int chunk = (int)(index >> 30);             // Level 1: Which 128 MiB chunk? (Bits 63..30)
        int bitIndex = (int)(index & ChunkMask);    // Intra-chunk offset (Bits 29..0)
        int word = bitIndex >> 6;                   // Level 2: Which 64-bit ulong?  (Bits 29..6)
        int bit = bitIndex & 63;                    // Level 3: Which bit (0..63)?   (Bits 5..0)
        return (_chunks[chunk][word] & (1UL << bit)) != 0;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public void Set(long index)
    {
        int chunk = (int)(index >> 30);
        int bitIndex = (int)(index & ChunkMask);
        int word = bitIndex >> 6;
        int bit = bitIndex & 63;
        _chunks[chunk][word] |= (1UL << bit);
    }
}

Memory savings on the Heap:

• bool[] at 1.52 trillion: ~1.52 TB (impossible ❌)
• ChunkedBitArray at 1.00 trillion (Windows): ~119 GB (932 chunks × 128 MiB, 0 GC triggered ✅)
• ChunkedBitArray at 1.52 trillion (Headless Linux): ~190 GB decimal / 176.96 GiB binary (1,416 chunks × 128 MiB—pushing right up to our 192 GB physical RAM limit with 0 GC triggered ✅)

The Hyper-Dimensional Algorithm: Bare Metal 🔩

// Hyper-Dimensional DFS: 1.52 TRILLION recursive calls
[MethodImpl(MethodImplOptions.AggressiveOptimization)]
public static void DfsLinearLong(
    long index,
    long maxDepth,
    ChunkedBitArray visited)
{
    if (index >= maxDepth || visited.Get(index))
        return;

    visited.Set(index);

    // Linear graph: next = index + 1
    // This is in tail position - TCO kicks in
    DfsLinearLong(index + 1, maxDepth, visited);
}

That's it. No node array. No unnecessary allocations. Just pure recursion hitting the metal. (Full C# benchmark source: LargeStackBenchmark_BonusRound.cs & LargeStackBenchmark_Program.cs on GitHub.)

🚀 C# AOT Results: Hyper-Dimensional Depth

Running C# 14 (.NET 10 Native AOT) on a minimal Headless Ubuntu Server 24.04.5 LTS environment to get as much of our 192 GB of system memory as possible:

Let that sink in for a second: it took nearly 11 and a half minutes (11.27 min / 676.08 seconds) of continuous, flat-out execution on a 5.7 GHz Ryzen 9 9950X3D to complete 1.52 trillion recursive calls—which is still insane when you realize the CPU was executing 2.25 billion recursive calls every single second without a single loop or a single Garbage Collector pause! And on Windows 11, our initial run was twice as slow—taking 15.20 minutes just to reach 1 Trillion calls (compared to 7.41 minutes on Headless Ubuntu) before Windows' ~38 GB desktop OS overhead ran out of physical RAM.

The Key Insights

1. TCO Has No Depth Limit (Zero Stack Frames Accumulated)

Tail Call Optimization transforms a recursive call into a register jmp instruction. Instead of pushing a new activation record onto the Thread Stack on every step, the CPU reuses the exact same stack frame Trillions of times. At 1.52 trillion calls, net Thread Stack growth is literally 0 bytes. The only limits left are:

• Physical RAM to record which nodes have been visited
• Memory bandwidth & CPU clock cycles (patience!)

2. Data Structures & 32-Bit Indexing Were the Real Bottleneck

We didn't hit a wall at 2.1 billion in Part 2 because of recursion—we hit it because C# arrays are indexed by a 32-bit signed int (Array.MaxLength = 2,147,483,591) and because our pre-allocated graph array filled RAM. By computing edges procedurally (index + 1), upgrading node indices to 64-bit long, and slicing the Heap into 128 MiB chunks, recursion scales until physical DIMMs are full.

3. Bit-Level Packing Is an 8x Memory Multiplier with Zero GC Pressure

Because CPUs cannot address below 1 byte, a standard bool[] wastes 7 out of every 8 bits—meaning 1.52 trillion nodes would require an impossible 1.52 TB of RAM. Packing 64 nodes into each ulong word (1 bit per node) with power-of-two bit-shifting (>> 30, >> 6, & 63) compresses 1.52 trillion nodes into 190 GB decimal (176.96 GiB binary) with zero hardware division instructions (idiv) and 0 Garbage Collector wake-ups (0 / 0 / 0 across Gen 0, Gen 1, and Gen 2).

4. Rock-Solid Linear Performance (O(N) Across Trillions of Calls)

From 3 billion to 1.52 trillion calls, throughput remained completely flat—~1.10 billion ops/sec (0.91 ns/call) on Windows 11 and ~2.25 billion ops/sec (0.445 ns/call, just 2.39 CPU cycles per recursive call!) on Headless Ubuntu Linux. Double the depth, double the time. No cache thrashing, no GC pauses, no degradation.

5. The OS Tax & Page Tables Matter at Terabit Scale (Windows 11 vs. Headless Linux)

When you're trying to use every last gigabyte of 192 GB of DDR5 RAM, the operating system itself becomes a primary variable:

• Reclaiming ~38 GB of RAM: Windows 11's desktop compositor and background services consumed ~35–42 GB at idle, capping us at 1.00 trillion calls (119 GB). Switching to Headless Ubuntu Server 24.04.5 LTS dropped user-space idle memory to just 54 MiB—freeing the headroom needed to reach 1.52 trillion stack frames (176.96 GiB / 190 GB).
• Cutting Execution Time in Half (15.2m → 7.41m at 1T): On Linux, by stripping redundant bounds checks and backing our bitset with 2 MiB Transparent Huge Pages (THP) instead of 45 million separate 4 KiB page table entries, we eliminated TLB page-walk stalls and shrunk the hot loop to just 9 x86-64 instructions (32 bytes)—running 2.05x faster than our original Windows run!

⚔️ Cross-Language Showdown: How Does C# Stack Up Against 11 Other Languages?

After pushing C# to 1.52 trillion recursive calls, the obvious next question was: "How do every other major systems, managed, functional, and scripting language perform on the exact same 192 GB Headless Ubuntu server?" We wrote and benchmarked the exact same recursive traversal across 12 languages, grouped into three architectural tiers (you can find the source code for all the benchmarks we ran on GitHub at github.com/rbtLong/hpc-dfs-iii).

Tier 1: Bare-Metal Systems Languages (Fortran 2008, Rust, C++20, C (C23), Zig)

Why They Are Tier 1 & Their Stack / Memory Allocation Advantage: Tier 1 languages compile directly to native machine code with zero virtual machine and zero Garbage Collector built in. That gives them two hardware advantages when pushing recursion to the limit of physical RAM:

• Unrestricted Stack & 64-Bit Flat Addressing: Unlike managed runtimes (where single arrays and Span<T> are capped at 32-bit int.MaxValue = ~2.14B elements and thread stacks are locked down), Tier 1 languages can address all 192 GB of RAM as a single flat 64-bit pointer held directly on the stack with 0 bytes of object headers. Even more remarkably, if you unlock the Linux stack limit (ulimit -s unlimited) and disable TCO in C (clang -O2 -fno-optimize-sibling-calls), the Linux kernel lets C dynamically grow its actual hardware Thread Stack (VmStk) to 156.46 GiB—pushing 10.50 Billion real 16-byte callq stack frames directly onto the Thread Stack!
• Zero Runtime Footprint (+35 Billion Extra Nodes at the Ceiling): Because Tier 1 binaries have only ~2 MiB of process overhead (no CLR or JVM host reserve), under TCO (0 bytes/call) they were able to push slightly past C#'s 1.520 Trillion (176.96 GiB) all the way to the physical kernel ceiling of 1.555 Trillion recursive calls (181.03 GiB) before the Linux kernel's ~3 GiB safety watermark stepped in.

Tier 1 Quirks Uncovered:

• Fortran 2008 & unsafe Rust Tied for #1 (1.90–1.91 cycles/call): Both gfortran -O3 and rustc emitted a 7-instruction (25-byte) loop that hoisted the constant 1 outside the loop and incremented index++ before the memory or, hitting 2.82 Billion ops/sec (9.00–9.03 min at 1.52T; 9.20–9.22 min at 1.555T).
• The LLVM 2x bts Unrolling Quirk (Where C# Beat Default -O3 C, C++, and Zig): Out of the box at -O3, Clang/LLVM unrolled the tail call 2x using back-to-back bts (Bit Test and Set) instructions that stalled AMD Zen 5's Store-to-Load Forwarding buffer—dropping C, C++, and Zig to 2.04–2.10B ops/sec (slower than C# Native AOT's 2.25B ops/sec). Disabling LLVM's 2x unroller (unroll(disable) / .never_inline) restored all three to 2.76–2.80B ops/sec.
• Safe Rust's Bounds-Check Tax: Idiomatic safe Rust (&mut [u64] slice) could not elide its slice bounds check inside the recursive loop, running at 2.39B ops/sec (10.59 min at 1.52T)—just 40 seconds ahead of C#.

How Did C# Hold Its Own Against Bare-Metal C, C++, and Rust?

Looking at the Tier 1 results above, it is remarkable that C#—a fully managed, garbage-collected language—was able to go toe-to-toe with bare-metal systems languages like C, C++, Rust, Zig, and Fortran across 1.52 Trillion recursive calls. Dissecting the hardware counters and compiler disassembly (objdump -d -M intel) reveals three key insights into how C# held its own—and why C itself wasn't in 1st place:

1. How C# Competed with Zero GC Overhead (9 Instructions vs. 7 Instructions): Every other language in Tier 1 (Fortran, Rust, C++, C, Zig) has no Garbage Collector at all. C# runs inside the .NET runtime with a live Garbage Collector—yet because our traversal allocates zero managed objects and eliminates stack frames via TCO, the GC stayed completely asleep (0 collections across 1.52 trillion calls).
   • It finished right on the heels of Safe Idiomatic Rust (10.59 min for Safe Rust vs. 11.27 min for C# at 1.52T—separated by just 0.15 CPU cycles per call, since Safe Rust's &mut [u64] slice emits a 2-instruction bounds check inside the loop).
   • And why did tuned Fortran, unsafe Rust, C++, and C run ~20% faster than C# (~9.0–9.15 min vs. 11.27 min, or 1.90–1.94 cycles/call vs. 2.39 cycles/call)? Disassembly showed the entire gap came down to just 2 extra x86 instructions in C#'s loop (9 instructions vs. 7 instructions): .NET's compiler reloaded the constant 1 (mov ecx, 1) inside the loop instead of hoisting it into a register beforehand, and used a separate lea rax, [r8+rax*8] instruction to calculate the memory address before or QWORD PTR [rax], rcx instead of folding the address math directly into the or instruction.
   • To prove the .NET runtime itself added zero hidden tax, we pasted C#'s exact 9-instruction assembly loop into a C program and compiled it with clang -O3: C executed those 9 instructions at 2.27B ops/sec (2.37 cycles/call)—matching C#'s 2.25B ops/sec (2.39 cycles/call) to within 1.2%!
2. Why Out-of-the-Box clang -O3 C, C++, and Zig Actually Ran Slower Than C# (The LLVM 2x bts Unrolling Trap): Notice the second C row near the bottom of the Tier 1 table: when compiled with standard clang -O3 out of the box, C (2.04B ops/sec, ~8.18 min at 1T) actually ran slower than C# (2.25B ops/sec, 7.41 min at 1T)! Why?
   • In a normal 1x loop, each call sets one bit in memory using a bitwise shift (shlx) and a direct memory read-modify-write (or QWORD PTR [mem], reg).
   • However, at default -O3, LLVM's optimizer tried to be "too clever": after turning the tail call into a loop, it unrolled the loop 2x (handling 2 nodes per iteration) and replaced shlx + or with x86's bts (Bit Test and Set) instruction. Specifically, Clang loaded the 64-bit word from cache into register r9 (mov r9, [rsi+r8*8]), executed two back-to-back bts r9, rdi instructions on that same register r9, and wrote r9 back to memory (mov [rsi+r8*8], r9).
   • Why did that hurt performance? Because bts both modifies register r9 and writes the old bit into the CPU Carry Flag (EFLAGS.CF), the second bts cannot execute until the first bts finishes, and the memory write cannot enter the CPU's Store Queue until both serial bts instructions complete. Because 64 consecutive recursive calls all hit the exact same 64-bit word in L1 cache, delaying the memory write stalls AMD Zen 5's Store-to-Load Forwarding (STLF) buffer on the next iteration—dropping default -O3 C, C++, and Zig from 1.94 cycles/call down to 2.56–2.64 cycles/call (2.04–2.10B ops/sec).
   • Once we told Clang not to unroll the loop (adding #pragma clang loop unroll(disable) in C, -mllvm -unroll-count=1 in C++, and @call(.never_inline, ...) in Zig), LLVM stopped using bts, emitted the clean 7-instruction shlx + or loop, and C jumped by +32% to 2.78B ops/sec (9.15 min at 1.52T).
3. Why Tuned C Landed in 4th Place Behind Fortran and unsafe Rust (Instruction Scheduling Inside the 7-Instruction Loop): Even after fixing the unroller, why wasn't C in 1st place? In truth, the top five tuned bare-metal languages—Fortran (9.00 min), unsafe Rust (9.03 min), C++20 (9.08 min), C23 (9.15 min), and Zig (9.17 min)—finished in a virtual photo finish across 1.52 trillion calls, separated by less than 0.04 CPU cycles (~6 picoseconds) per call! The tiny ~9–15 second edge held by Fortran (gfortran -O3) and unsafe Rust (rustc -O3) over C came down to instruction ordering inside their 7-instruction loops: both GCC's Fortran backend and Rust scheduled the index increment (inc rdi) before the memory or QWORD PTR [rdx+rax*8], rcx instruction, allowing the CPU to increment the counter and prepare the loop branch in parallel while the Load-Store Unit executed the memory update—whereas Clang scheduled add rax, 1 after the memory or.

Best of all, our C# solution isn't some exotic dialect or foreign low-level DSL. It's the same C# we all know and love—complete with rich high-level language features—just using hot-path HPC primitives like ref struct, scoped Span<T>, Unsafe, and TCO that any C# developer can reach for when performance matters.

Tier 2: Managed VMs, Functional Actor Runtimes & Goroutines (Scala 2.13, Elixir / BEAM, Java 21, Go 1.24)

Tier 2 languages run on managed runtimes with Garbage Collectors—and when pushed to hyper-dimensional recursion depth, they expose some of the wildest runtime quirks in computer science:

• Scala 2.13 (@tailrec on OpenJDK 21): Even though the JVM has no TCO bytecode instruction, Scala's compiler (scalac) rewrites @tailrec self-recursion at compile time into a JVM bytecode backward jump (goto 0). Quirk: A 1D Array[Long] hits the JVM's 32-bit array index cap at 137.44 Billion bits (70.77s). A 2D Array[Array[Long]] on the JVM heap reaches 1.00 Trillion in 12.50 min, but crashes with OutOfMemoryError at 1.52T because ParallelGC reserves Young Generation space inside -Xmx182g. Only by bypassing the JVM heap with off-heap sun.misc.Unsafe did Scala reach 1.52 Trillion in 13.58 min—with C# AOT finishing 2.31 minutes (+20.8%) faster!
• Elixir 1.14 / Erlang OTP 25 (BEAM JIT): As a pure functional VM without loops, BEAM guarantees O(1) Last Call Optimization—holding its stack at just 54 words (432 bytes total!) across 1.00 Billion calls in 8.07s. Quirk (The 60-Bit Fixnum Overflow): Because the 64-bit BEAM VM uses 4 tag bits per word, immediate integers (Fixnum) are only 60 bits signed! Shifting 1 <<< bit on bit positions 59..63 (7.8% of calls) overflows Fixnum and allocates heap Bignum objects—triggering 35,623 Minor GCs per 1 Billion calls!
• Java 21 (OpenJDK HotSpot C2 — Standard Un-Optimized Recursion): Because Java intentionally omits automatic TCO so stack-walking APIs preserve every frame (32 bytes/call), a standard, un-optimized recursive call burns stack memory on every step. Quirk (The 176 GiB Thread Constructor Escape Hatch): Default -Xss1m crashes at 23,607 calls, and the JVM CLI parser rejects any flag above -Xss1g (26.84M calls). By passing a 64-bit long (176 GiB) to Java's 4-argument new Thread(group, target, name, stackSize) constructor, we bypassed the CLI parser and mapped a 176 GiB native OS thread stack—allowing standard recursive Java 21 to push 5.50 Billion real stack frames in 68.05s (164.99 GiB RAM, 0 GC) before exhausting our 192 GB RAM (276x shallower and 27.9x slower per call than C#). Note: While Java can easily adopt our zero-GC 1-bit slab memory map (long[][]), replicating our jump-based execution in Java is much harder (since Java has neither TCO nor a working goto keyword), though not strictly impossible!
• Go 1.24 (gc Dynamic Goroutine Stack — Standard Un-Optimized Recursion): Everyone expects standard recursion in Go to beat Java because Go goroutines dynamically double their stacks on the heap. Quirk (Go's Hardcoded 32-Bit maxstackceiling = 2 GB Wall): On defaults (1 GB decimal limit), standard recursive Go panics at 8,388,399 calls when its 512 MiB stack tries to double to 1,024 MiB (1,073,741,824 > 1,000,000,000!). Even when we called debug.SetMaxStack(180 GiB), standard recursive Go still crashed at exact call 33,554,004 (0.57s, 1.00 GiB stack) because Go's runtime source (runtime/stack.go:336 & runtime/proc.go:166) uses a 32-bit uint32 in func stackalloc(n uint32) and hardcodes maxstackceiling = 2,000,000,000 bytes! However, Go can do much better: if you apply our exact same 1-bit slab memory layout ([][]uint64) and jump-based execution approach (using Go's native goto), Go completely bypasses the goroutine stack limit and can achieve the same 1.52 Trillion depth and match—or even beat—C#'s execution speed!

Breaking Down Tier 2: C# vs. Scala, C# vs. Java & Go, and How They Can Be Optimized

Before diving into the numbers below, an important fairness note: for Java and Go, the table above measures a standard, un-optimized implementation (just as a naive explicit Stack<T> without TCO caps out far shallower at ~134M–268 Million due to the 2 GB T[] heap object limit and heap double-dipping, and even Part 2's TCO with a naive 1D bool[] memory map stopped at 2.14 Billion). We have not yet optimized Java or Go with custom control-flow jumps—and as we break down below, both languages can perform dramatically better when given the same memory map and execution approach (with the exception of Java's control flow, which is much harder to pull off, though not strictly impossible):

• C# vs. Scala (11.27 min vs. 13.58 min at 1.52T): Scala is the only JVM language here that reached the trillions out of the box because scalac rewrites @tailrec self-recursion at compile time into a bytecode backward jump (goto 0), completely avoiding stack frames. However, when using a 2D chunked array (Array[Array[Long]]) on the JVM heap, Scala hit 1.00 Trillion in 12.50 min (1.33B ops/sec) and then crashed with OutOfMemoryError at 1.52T because ParallelGC reserves Young Generation space inside -Xmx182g. Even after we rewrote Scala to bypass the JVM heap using off-heap sun.misc.Unsafe, Scala took 13.58 min (1.87B ops/sec) to reach 1.52T—meaning C# finished 2.31 minutes (+20.5%) faster while keeping its GC completely idle.
• C# vs. Standard Java 21 (276x Deeper & 27.9x Faster — And Why Optimizing Java Is Harder, Though Not Impossible): Because javac and OpenJDK HotSpot intentionally omit automatic TCO, every standard recursive call in Java pushes a 32-byte (256-bit) activation record onto the thread stack. Even after we bypassed the JVM CLI parser's -Xss1g cap using the 4-argument new Thread(..., 176 GiB) constructor to map a 176 GiB native OS thread stack, standard Java burned 256 bits of stack memory for every 1 bit on the heap—maxing out at 5.50 Billion calls in 68.05s (80.8M ops/sec), or 276x shallower and 27.9x slower per call than C#.
  Can Java do better? Yes—on memory layout immediately, though execution is much harder: Java can adopt our exact same zero-GC 1-bit slab memory map on the heap (long[1485][16777216]) with 0 GC pauses because mutating primitive long bits allocates zero objects. However, applying our jump-based execution approach in Java is much harder because Java lacks TCO and banned the goto keyword in .java source code—meaning you either have to flatten your algorithm into a state-machine loop (while + switch / labeled continue) or use a post-compile bytecode weaver to inject raw 0xA7 (goto) opcodes into the .class binary (which is exactly what scalac does under the hood!). Hard—yes—but not impossible.
• C# vs. Standard Go 1.24 — Why Un-Optimized Go Performed Worse Than Java (Tested Twice!), and How Optimized Go Can Match or Beat C#: On paper, everyone expects Go to crush Java in deep recursion because Go goroutines allocate dynamically growable stacks on the heap instead of fixed OS thread stacks. When we tested a standard, un-optimized recursive implementation in Go against Java twice, we uncovered a surprising reversal:
  1. Test 1 (Out-of-the-Box Defaults): On default settings, Go (8.39 Million calls under its default 1 GB stack limit) easily beat default Java (23,607 calls under its default 1 MiB -Xss1m limit), just as most engineers would predict.
  2. Test 2 (Unlocked Runtimes — Where Standard Go Collapsed at 33.55M!): When we unlocked both runtimes—giving Java a 176 GiB thread stack via new Thread(..., 176 GiB) and calling debug.SetMaxStack(180 GiB) in Go—standard Java soared to 5.50 Billion calls (80.8M ops/sec), while standard Go panicked and died at exact call 33,554,004 (52.3M ops/sec)—meaning unlocked Java beat un-optimized Go by 164x in depth and 1.55x in speed!
  Why did standard, un-optimized Go hit a wall at 33.55M? First, auditing Go's runtime source (runtime/proc.go:165 and runtime/stack.go:336) revealed that maxstackceiling is hardcoded to 2,000,000,000 bytes (2 GB) and func stackalloc(n uint32) uses an unsigned 32-bit uint32—so when Go's power-of-two stack doubler (256 MiB → 512 MiB → 1.00 GiB at 33,554,004 calls) tries to double to 2.00 GiB (2,147,483,648 bytes), it exceeds 2,000,000,000 and panics regardless of debug.SetMaxStack(). Second, Go had to pause execution 19 separate times to allocate a 2x larger heap stack and copy every frame over (runtime.copystack).
  Can Go do better? Absolutely—in fact, Go can achieve the exact same optimization and performance (or even better!): Unlike Java, Go compiles directly to native machine code, supports unboxed 64-bit primitive slices ([][]uint64), and has a real, first-class goto LABEL statement built right into the language! By adopting our exact 1-bit slab memory layout and replacing the recursive call with a direct goto jump (or an AST pre-build weaver via go generate), Go uses 0 bytes of goroutine stack, never triggers runtime.copystack or GC pauses, and can reach the full 1.52 Trillion depth at native machine speed—matching or potentially even edging out C# in raw execution!

Tier 3: Dynamic Scripting & Bytecode Runtimes (Node.js v22 V8, Python 3.12 CPython)

What happens when you throw hyper-dimensional recursion at the world's two most popular dynamic scripting engines? We uncovered a hilarious reversal between Node.js (Google V8) and Python 3.12 (CPython):

• Node.js v22.14 (Google V8 12.4 JIT — The Signed 32-Bit Flag Overflow): Even though ES6 (ES2015) mandated Proper Tail Calls (PTC), V8 refused to ship it. Every recursive call pushes 80 to 136 bytes onto the V8 stack, crashing at 7,384 calls on the default 984 KiB stack. Quirk: When we passed --stack-size=180000000 (180 GB), Node.js threw RangeError: Maximum call stack size exceeded on line 0 before main() even started! Why? Because V8 multiplies v8_flags.stack_size * KB (int32_t * 1024) using signed 32-bit integer arithmetic—so any value above 2,097,151 KiB (2.00 GiB) overflows int32_t into a negative number! At its hard 32-bit ceiling (--stack-size=2097151), Node.js permanently dies at 26,843,490 calls.
• Python 3.12.3 (CPython — The PEP 652 Heap Frame Plot Twist That Beat Go and Node.js!): Python has no TCO and stops at 997 calls by default (sys.getrecursionlimit() = 1000). In older Python (≤ 3.10), raising sys.setrecursionlimit() caused a fatal C stack overflow (SIGSEGV) around ~30,000 calls. Quirk: Starting in Python 3.11/3.12 (PEP 652), CPython stopped pushing Python-to-Python calls onto the C hardware stack (VmStk stays flat at 132 kB!) and instead allocates linked _PyInterpreterFrame structs (168.66 bytes/frame) on the 64-bit process Heap! With sys.setrecursionlimit(1_000,001,000), Python 3.12 completed 1,000,000,000 (1.00 Billion) recursive calls in 117.52 seconds (157.20 GiB RAM, 0 GC)—outlasting Node.js by 37x and Go by 30x in recursion depth! (Though reaching 1.52 Trillion in Python would still require an impossible 238.7 TiB of RAM!)

Breaking Down Tier 3: C# vs. Node.js, C# vs. Python, and Node.js vs. Python

• Why Node.js (V8) Cannot Do TCO Here: Wait—didn't the ECMAScript 6 (ES2015) specification officially mandate Proper Tail Calls (PTC) in strict mode ("use strict")? Yes, it did! However, Google's V8 team (which powers Node.js and Chrome) refused to ship it in production—briefly putting it behind an experimental --harmony-tailcalls flag before ripping that flag out of V8 entirely. V8's engineers objected that implicit tail call elimination silently drops stack frames, breaking Error.stack traces, Chrome DevTools profiling, and call-stack debugging (leaving Apple's JavaScriptCore in Safari/WebKit as the only major JS engine that ever shipped ES6 PTC).
• C# vs. Node.js v22 (56,625x Deeper Unlocked & 41.5x Faster per Call): Even though V8 compiles our recursive DFS with its Maglev/TurboFan JIT, refusing to emit TCO forces Node.js to push an 80 to 136.5 byte native stack frame onto the hardware thread stack on every single call—crashing at just 7,384 calls out of the box (--stack-size=984). Worse yet, when you try to unlock Node.js's stack on a 192 GB server, V8 parses --stack-size (in KiB) by multiplying v8_flags.stack_size * 1024 inside a signed 32-bit integer (int32_t)—which overflows into a negative number above 2,097,151 KiB (2.00 GiB) and crashes before main() even starts! That hard-caps Node.js at 26,843,490 calls (0.46s @ 25M = 54.3M ops/sec). Because V8 has to push 80-byte (640-bit) stack frames to RAM and execute stack-guard checks on every call while C# executes a 0-byte register jmp and flips 1 bit, C# (1.52 Trillion at 2.25B ops/sec) ran 41.5x faster per call, used 640x less memory per node, and went 56,625x deeper than unlocked Node.js (and 205,850,487x deeper than default Node.js)!
• C# vs. Python 3.12 (1,520x Deeper, 265x Faster, and 1,349x Less Memory per Node): Out of the box, CPython stops at 997 calls (RecursionError). When unlocked (sys.setrecursionlimit(1_000_001_000)), Python 3.12 reached 1.00 Billion calls—but because Python has no TCO and runs inside a bytecode evaluation loop, every recursive step still allocates 168.7 bytes (1,349 bits) on the Heap and crawls at 8.5M ops/sec. At the 1.00 Billion mark where Python needed 117.52 seconds and 157.20 GiB of RAM, C# traverses those same 1.00 Billion nodes in 0.44 seconds using just 119 MB of RAM—running 265x faster per call, using 1,349x less memory per node, and scaling 1,520x deeper (1.52 Trillion vs. 1.00 Billion).
• Node.js vs. Python 3.12 — How "Slow" Interpreted Python Crushed JIT-Compiled Node.js by 37x in Depth: This was the biggest upset in Tier 3. In raw execution speed, Node.js's V8 JIT (54.3M ops/sec) is 6.4x faster than Python 3.12's bytecode interpreter (8.5M ops/sec), and on default settings Node.js reaches 7.4x deeper (7,384 vs. 997). Normally, you would bet everything that V8-powered Node.js would obliterate Python when unlocked. Yet when we unlocked both runtimes, Python 3.12 (1.00 Billion calls) beat Node.js (26.84 Million calls) by 37.25x in recursion depth! Why? Because Node.js binds JavaScript recursion directly to the C++ hardware thread stack (RSP) and traps that stack behind a 32-bit 2 GiB flag ceiling—leaving 98.9% of our 192 GB of RAM completely unreachable. Python 3.12 (PEP 652), by contrast, decoupled Python-to-Python calls from the C hardware stack (keeping its OS thread stack flat at just 132 kB) and moved its _PyInterpreterFrame activation records onto the 64-bit process Heap. Even though Python's Heap frames were more than twice as large as V8's stack frames (168.7 B vs. 80.0 B) and 6.4x slower per call, placing them on the unrestricted 64-bit Heap allowed Python to utilize 157.20 GiB of system memory and outlast both Node.js (37x) and Go (30x)!

But Wait—Isn't Using the Heap "Cheating"? 🤔

You might be thinking: "Hold on—you allocated a ChunkedBitArray on the Heap. Doesn't using the Heap violate the rules of recursion vs. iteration?"

No. In fact, this question exposes the single biggest misconception in the entire "Recursion vs. Iteration" debate. Every graph traversal—whether recursive or iterative, and whether written in C#, Java, Go, or bare-metal C—has to manage two completely separate kinds of state:

1. Control Flow (Where am I in the traversal?): Which node am I currently visiting, and how do I advance to the next one?
2. Visited State (Which nodes have I already seen?): The visited lookup structure that prevents infinite cycles. Every approach stores visited on the Heap because a multi-gigabyte graph cannot fit inside a default 1–8 MB Thread Stack.

1. The "Iterative Stack" Is ALSO on the Heap—And Without TCO, It Doesn't Even Come Close to 2.14 Billion!

When mainstream engineering advice tells you, "Convert your recursive DFS into a while loop using an explicit Stack<T> to avoid a StackOverflowException," what is new Stack<T>() actually doing under the hood?

Stack<T> is a Heap-allocated object wrapping a Heap-allocated T[] array! Converting recursion to an explicit Stack<T> does not eliminate stack memory—it merely moves the call stack off the CPU's Thread Stack and onto the Heap. Remember: in Part 2, 2.14 Billion (2,147,483,591) was the TCO Recursive limit with a naive 1D bool[] / NodeLinear[] memory mapping (where TCO used 0 bytes of stack, and our linear Stack<int> test only survived to 2.14B because it immediately Pop()ped the current node before Push()ing the next one—holding just 1 element = 4 bytes in the stack, which is functionally manual TCO!). When a naive Stack<T> is NOT using TCO and actually has to push and hold active frames on the Heap as it descends (just like a real call stack in backtracking or post-order DFS), it is double-dipping on the Heap and crashes far shallower than 2.14 Billion:

• Memory Double-Dip (64–128+ bits vs. 0 bits per node): Pushing 64-bit long node indices (8 bytes) or (long node, int state) frames (16 bytes) onto an explicit Stack<T> burns 64 to 128+ bits per node on the Heap on top of the graph and visited state. At 1.52 trillion nodes, an explicit Stack<long> would require an impossible 12.16 to 24.32 Terabytes of Heap RAM just for the traversal stack—whereas TCO recursion uses 0 bytes of control-flow memory!
• Why Naive Stack<T> (No TCO) Crashes at ~134M – 268 Million (or 1.07B Max): By default in .NET, no single array object on the Heap can exceed 2 GB (2,147,483,591 bytes)—the exact same 2 GB wall as the Thread Stack! Because Stack<long> (or Stack<Node> references) stores 8 bytes per element (or 16 bytes per state frame) inside a single contiguous T[] array on the Heap, 2 GB / 8 bytes caps Stack<long> at just ~268 Million (268,435,456) elements—and 16-byte frames cap out at ~134 Million (or ~15–30 Million when paired with Part 1's naive Heap graph)! Even if you enable <gcAllowVeryLargeObjects> on 64-bit .NET, Stack<T> grows its backing T[] array by powers-of-two doubling (2x) (134M → 268M → 536M → 1,073,741,824 = 1.07 Billion)—where the very next 2x resize overflows 32-bit signed int capacity math while simultaneously demanding both the old multi-gigabyte array and the new 2x array on the Large Object Heap and thrashing the GC!

2. Why "Using the Heap" Alone Couldn't Save Standard Recursion in Java, Go, Python, or Node.js

If putting visited on the Heap were a "cheat code," then standard recursive Java, Go, Python, and Node.js—all of which also used the Heap for their visited state (and in Go and Python, even used the Heap for their call stacks!)—would have effortlessly reached 1.52 trillion calls out of the box too. Instead, when running a standard recursive function call without manual control-flow rewriting, look at what happened to them on Control Flow (#1):

• Go Literally Allocates Its Call Stack on the Heap—And Standard Recursion Still Died at 33.55 Million: A Go goroutine's stack is not a fixed OS thread stack; it is a dynamic buffer allocated directly on Go's managed Heap. Yet because the Go compiler does not perform automatic Tail Call Optimization on a standard recursive call, every step pushed a 32-byte frame onto that Heap-backed goroutine stack, forced 19 stop-and-copy Heap reallocations (runtime.copystack), and hit Go's hardcoded 2 GB per-goroutine stack ceiling (maxstackceiling) at just 33.55 million calls! (Whereas if you adopt our [][]uint64 1-bit slab map in Go and manually replace the recursive call with Go's native goto statement, Go bypasses the goroutine stack entirely and can achieve the exact same zero-GC 1.52T layout and match or even beat C#'s speed!)
• Java Had the Exact Same Heap ChunkedBitArray—And Standard Recursion Died at 5.50 Billion: We gave Java the exact same 1-bit-per-node ChunkedBitArray on the JVM Heap (which also runs with 0 GC pauses since mutating pre-allocated primitive long[][] arrays allocates zero objects) and even mapped a massive 176 GiB custom thread stack (-Xss176g). Yet because Java lacks TCO—and even banned goto in .java source code—standard recursion in Java burned 256 bits of stack RAM for every 1 bit of Heap bitmap, exhausting 171.68 GiB of stack memory at 5.50B calls (276x shallower than C#), unless you resort to complex loop-switch rewriting or raw JVM bytecode hacking.
• Python 3.12 Stores Stack Frames on the Heap—And Exhausted 192 GB at 3.09 Billion: Since PEP 652, CPython allocates its interpreter stack frames (_PyInterpreterFrame) on the Heap rather than the C hardware stack. Even with Heap-allocated frames and a Heap-allocated bitset, the lack of TCO meant Python burned ~56 bytes of Heap per recursive call—running out of all 192 GB of physical RAM at 3.09 billion calls.
• Even With TCO, Heap Architecture Matters (Scala & Elixir): Elixir has TCO, yet its immutable functional Heap had to copy 1 KiB sub-binaries and run GC sweeps, collapsing to 13.4M ops/sec. Even Scala 2.13 (which has @tailrec) paid a ~5 GiB JVM GC reservation penalty on its 2D Heap array (long[][]) and finished over 2.3 minutes slower than C#.

3. Non-GC Languages (C, C++, Rust, Zig) vs. Managed C#: Manual Release & RAII

What about the bare-metal Tier 1 languages (C, C++, Rust, Zig, and Fortran)? They also have to allocate the ~181 GiB (190 GB) visited bitset on the Heap (via mmap, calloc, or std::alloc::alloc_zeroed).

The difference is what happens over the lifetime of that allocation:

• In Non-GC Systems Languages (Manual Deallocation & RAII): Because C, C++, Rust, Zig, and Fortran have no Garbage Collector, you are 100% responsible for the lifecycle of those 181 GiB of physical pages. In C, Zig, and Fortran, you must explicitly release the memory back to the OS kernel (free() / munmap() / defer allocator.free() / deallocate()) or risk leaking the entire system's RAM. In C++ and Rust, this is enforced deterministically through RAII (Resource Acquisition Is Initialization)—using destructors (~BitSet() / std::unique_ptr) in C++ or the Drop trait in Rust to automatically unmap the Heap slabs the instant the traversal scope exits.
• In C# (.NET 10) — Deterministic RAII-Style Cleanup Plus Zero-GC Execution: In standard managed code, allocating 177 GiB across 1,416 Heap arrays would normally make developers terrified of Garbage Collector pauses. Yet because we pre-allocated our fixed-size 128 MiB slabs up front and allocated 0 bytes inside the recursive hot loop, .NET's GC never woke up once (Gen 0/1/2: 0 / 0 / 0) across all 1.52 trillion calls. And when the traversal finishes, our ChunkedBitArray and FlatNativeBitArray implement IDisposable (using using var visited = ..., C#'s deterministic disposal pattern) and invoke madvise(..., MADV_DONTNEED) / NativeMemory.AlignedFree to zap and return all 177 GiB of physical pages to the OS kernel immediately—giving us deterministic RAII-grade resource cleanup without giving up a managed language!

Test Environment

Closing Thoughts (For Now...)

Graph Traversal Is the Bedrock of Modern Computing

Depth-First Search is one of the very first, most basic algorithms we learn in computer science. So why go back to it and push it to such an extreme? Because graphs and trees are the cornerstone—the invisible bedrock—of modern computing. Whichever direction you look, graphs are the underpinning that drives everything we build:

• AI & Deep Learning: Neural networks, computation graphs, backpropagation (which is literally reverse post-order DFS), transformers, and Tree-of-Thoughts (ToT) reasoning.
• UI / UX & Rendering Engines: React's Fiber tree, Angular's component hierarchy, browser DOM and layout trees, and desktop UI scene graphs.
• The Internet, Networks & Maps: Packet routing, network topologies, GPS navigation and map routing graphs, distributed service meshes, and dependency graphs.
• File Systems, Storage & USB / Device Peripherals: Directory hierarchies, storage B-trees, OS hardware device trees, and USB / PCIe bus and peripheral topology trees.
• Circuit Boards & Robotics: PCB trace routing and circuit netlist graphs, chip layout, robot kinematic chains, and motion-planning / pathfinding state graphs.
• Call Graphs, Execution Paths & Concurrency: Function call chains, compiler ASTs and control-flow graphs, thread execution trees, deadlock cycle detection, and garbage collector mark-sweep reachability graphs.

What 1.52 Trillion Calls Taught Me

Even though this result was entirely unexpected, the irony is that tail call optimization and bit-mapped memory layouts have been around since the very beginning. Neither of them is a new idea. Yet pushing this one fundamental recursive algorithm all the way to 1.52 trillion calls gave me a much deeper, first-principles understanding of the HPC memory layouts of each language—and proved that under the hood, they are not all the same.

What stood out most is that C# is genuinely unique in its versatility. It held its own right alongside the heavyweight Tier 1 systems languages—C, C++, Rust, and Fortran—at the absolute edge of our 192 GB hardware ceiling. That doesn't mean C# is a replacement for bare-metal systems languages everywhere, but it demonstrates something remarkable: even in a language that carries a full-featured Garbage Collector, you can write code that does not touch the GC at all (0 wake-ups across 1.52 trillion calls).

Of course, that doesn't take anything away from the real advantages of a language like Rust. In fact, I am a big fan of Rust and have built a couple of systems in Rust specifically because it offers a deterministic, rock-solid runtime profile with strong compile-time guarantees that C# wasn't designed to match when you need long-running, pause-free determinism (though even Rust can still leak memory if reference cycles or allocations are misused).

At the same time, Rust has its own real trade-offs: the borrow checker has multiple layers of complexity that often force your architecture itself to become complex—and as we saw in our benchmark (where safe idiomatic Rust ran 17.6% slower than unchecked Rust due to slice bounds checks), if you aren't careful you can still end up with sub-optimal machine code while fighting the borrow checker at the same time. For example, in one of my recent Rust projects, I built a controller whose sole job was to talk to a physical hardware controller driving a device. I deliberately avoided bringing in tokio or async network I/O because yielding to network traffic would have made execution unpredictable and non-deterministic—defeating the entire reason I chose Rust! Instead, I kept the Rust controller strictly deterministic, wrote directly to a Unix Domain Socket (UDS) as a clean architectural seam, and handled all the network orchestration at the C# layer, which was built for it. It was a fantastic solution—and this deep-dive into how different runtimes behave at their physical limits makes it crystal clear why choosing the right seam between languages works so well.

I still cannot believe we reached a point where trillion-scale recursion is truly possible. What I once assumed was a hard, inescapable limit of recursion turned out not to be a hardware limit at all—the solution to this problem wasn't some new invention. It was always there... I just never knew...

More than anything, discovering that a basic algorithm we all learned in school was hiding this kind of scale right in plain sight shows just how much I still do not know. Once you see it though, your world changes and you cannot unsee it. And there is still much more work to do—stay tuned for Part 4, where we go even deeper! :)