Unify the Random Number Generator Used Across All BenchGen Targets

Description:

BenchGen currently relies on each target language's built-in random number generator to compute the next value of PATH, which ultimately guides the execution flow of generated programs. This leads to inconsistent control-flow behavior across languages, because each standard library uses different RNG algorithms, periods, and seeding mechanisms.

To ensure reproducibility and consistent control-flow behavior, BenchGen should provide a single, language-agnostic random number generator algorithm that target languages can reimplement faithfully.

---

Motivation

Our control-flow mechanism uses a PATH variable of type unsigned long, as explained in this wiki. The value of PATH must be computed deterministically from a pseudo-random stream. Today, C uses rand, but C++, Go, Julia, Zig, Odin, V, etc. do not implement rand() the same way. In practice, this means:

• different execution paths for the same benchmark across languages
• harder debugging and experiment reproducibility
• inconsistent PGO behavior

Thus, we need one portable RNG algorithm, explicitly implemented in every language backend.

---

Proposal: Adopt a Simple, Portable Linear Congruential Generator (LCG)

We propose shipping a tiny RNG based on a well-known 64-bit LCG. LCGs are:

• trivial to implement in any language
• deterministic across architectures
• extremely fast
• portable (no reliance on library RNGs)

A classic choice is the Numerical Recipes 64-bit LCG:

X_{n+1} = (6364136223846793005 * X_n + 1) mod 2^{64}

This RNG has good quality for synthetic benchmarks and avoids cross-language divergence.

---

Suggested API

To resemble C's rand(), we can expose:

C-like signature

unsigned long benchgen_rand(void);
void benchgen_srand(unsigned long seed);

Expected behavior

• benchgen_srand(seed) initializes a 64-bit global state:
  state = seed;

• each call to benchgen_rand() returns:
  state = (A * state + C) mod 2⁶⁴
return state >> 32; // a 32-bit "rand-like" value

• to compute a full 64-bit PATH value (like current C code):

  unsigned long rng() {
      unsigned long hi = benchgen_rand();
      unsigned long lo = benchgen_rand();
      return (hi << 32) | lo;
  }
  

Constants

A = 6364136223846793005ULL
C = 1ULL

These constants are widely used, fully portable, and documented.

---

Advantages

✔ deterministic across all languages
✔ trivial to port (2–3 lines of code per language)
✔ same outputs on x86_64, ARM64, RISC-V, etc.
✔ avoids relying on libc / stdlib RNG differences
✔ keeps interface similar to C’s rand()

---

Tasks

• Add a reference implementation in C.
• Specify the algorithm in the documentation.
• Implement in each backend: C++, Go, Julia, Zig, V, Odin, etc.
• Add a cross-language test suite that checks the first N outputs for a fixed seed.

---

Reference Implementation (C)

static unsigned long benchgen_state = 1;

void benchgen_srand(unsigned long seed) {
    benchgen_state = seed;
}

unsigned long benchgen_rand(void) {
    benchgen_state = 6364136223846793005ULL * benchgen_state + 1ULL;
    return benchgen_state >> 32;  // mimic C's rand() width
}