Fatal error: exception Stack_overflow from ocamlrun only under production-size inputs

Direct Answers

1. Increasing OCAMLRUNPARAM l is not a reliable production fix. It only postpones the overflow. The bytecode interpreter checks its internal guard at each function entry, but each recursive call still consumes C stack frames. Once the OS thread stack limit (ulimit -s, typically 8 MiB on Linux) is reached, the process receives SIGSEGV instead of a clean Stack_overflow exception, making debugging harder.
2. Switching to native code (ocamlopt) does not solve non-tail recursion. The default OS stack limit is higher (8 MiB vs. the bytecode default of 2 MiB), so the failure threshold moves, but the fundamental linear stack growth remains. Only tail-call optimization—which ocamlopt performs aggressively—eliminates the growth, and that requires the function to be written in tail-recursive form.
3. No documented formula exists for safe recursion depth per stack size. Frame size varies with function complexity, local variables, and compiler version. The documented approach is empirical measurement on the target platform.

Why Tail-Recursion Is the Only Reliable Fix

The bytecode interpreter executes every recursive call as a C function call. A list of 300,000 elements means 300,000 C stack frames. The default OCAMLRUNPARAM l=256k (256 kilowords = 2 MiB on 64-bit) allows roughly 25,000–50,000 frames depending on frame size—far below production scale. Raising l to, say, 1000k (8 MiB) may cover the current input, but:

• The runtime silently clamps l to the OS RLIMIT_STACK at startup without logging.
• If the OS limit is not also raised (ulimit -s unlimited or a higher value), the process segfaults.
• Each thread gets its own stack limit; total virtual memory commitment grows with thread count.

A tail-recursive rewrite with an accumulator and a final List.rev reduces C stack usage to O(1). The temporary list created by List.rev doubles heap allocation for that pass, so ensure OCAMLRUNPARAM h (heap size) accommodates it.

Verification Steps for This Deployment

1. Check the current OS stack limit:

   ulimit -s

   (value in kilobytes). Confirm OCAMLRUNPARAM l * 8 < ulimit -s * 1024.
2. Run the program with verbose stack reporting:

   OCAMLRUNPARAM l=256k,v=0x400 ./your_program

   Observe the reported stack size at startup.
3. Write a probe function that recurses until Stack_overflow, then binary-search the maximum depth for the current l value. Compare that depth with your production input size.
4. Compile the same module with ocamlopt and run without OCAMLRUNPARAM. If it still overflows, the recursion is not tail-recursive in native code either—confirming the rewrite is necessary regardless of backend.

Missing Diagnostic Detail

What is the exact recursion depth (list length) in the largest production input? If it exceeds ~50,000, the bytecode default cannot handle it even with a raised l unless the OS limit is also increased, and the segfault risk remains. This number confirms whether a configuration-only approach could ever be viable.