Rayon Solver-Parallelism Lab Report

ergo epic RAYPAR (7MKIR7). Authors: offline harness + 80/40-path capture corpus.

TL;DR

The production drain’s 4.21/8 achieved parallelism is not caused by rayon overhead, per-item diagnostics, or memory bandwidth. It is caused by rayon’s work-stealing scheduler failing to load-balance under extreme path-cost skew. An LPT (longest-processing-time) static partition over the same 8 threads, same solver code, same captures achieves 7.80/8 efficiency (97%) vs rayon’s 4.91/8 (61%) — a 35% wall-time reduction with zero solver changes.

The single highest-impact intervention (RAYPAR-T3) is to replace the per-item rayon par_iter fan-out with an LPT-pre-balanced scoped-thread partition, using a resolve-time cost proxy (e.g. total word-boundary-price count per hop) to bin paths before the solve.

1. Method

Harness

degenbot-solvers/examples/rayon_scale_probe.rs reconstructs production ResolvedMixedPath inputs (V3 CL hops carrying the production build_cl_word_profiles + build_cl_crossing_table precomputes) from the committed heavy-CL capture fixture (tests/fixtures/heavy_cl_solve_captures.jsonl, 420 paths / 87 MB) and re-runs the production solver entry mixed::solve_path_with_min_profit under controlled thread counts.

The harness sweeps:

  • Thread counts: {1, 2, 4, 8} via per-pool ThreadPoolBuilder::num_threads.

  • Closure variants: bare solve vs production-diagnostics (span enter + 8 relaxed atomics + K-slowest heap + walk/gate stat reset-take) — to isolate per-item closure overhead.

  • Scheduling variants: rayon par_iter (work-stealing) vs std::thread::scope static partition (contiguous vs LPT-balanced bins).

  • Control experiment: pure-CPU spin workload through the same rayon pools — maps the machine’s scheduling baseline (no solver, no memory traffic).

Golden-lite gate

Each reconstructed path is solved once serially and its profit compared to the recorded capture golden within PROFIT_EPS = 100,000 wei. On the 40-path validation subset: 14/14 golden-bearing paths matched, 0 excluded.

2. Results

2.1 80-path corpus (bare solve, release build)

label

threads

wall_s

sum_item_s

efficiency

item_med_ms

serial-median

1

147.5

147.5

1.00

91.6

rayon-bare

4

41.0

154.8

3.77/4

95.6

rayon-bare

8

32.6

159.9

4.91/8

98.9

std-lpt

4

39.1

156.0

3.99/4

100.4

std-lpt

8

21.1

164.7

7.80/8

99.3

std-contig

8

45.4

157.3

3.46/8

102.8

Top-10 per-path medians (us, path_id): four paths at ~18s (all path 501 across different blocks), three at ~7.3s (path 500), three at ~6.6s (path 400). Top-8 share = 60% of total serial work. max_item = 18.1s.

2.2 40-path corpus (full variant sweep)

label

threads

wall_s

efficiency

rayon-bare

1

54.6

1.00

rayon-bare

4

17.7

3.25/4

rayon-bare

8

17.6

3.31/8

rayon-diag

8

17.7

3.32/8

std-lpt

8

17.4

3.34/8

control-spin

8

0.011

7.31/8

2.3 Production cross-check (KGXFT7 gate-on run, 50 drains)

  • Achieved parallelism: 4.21/8 (solve.cpu_us = 1,380s vs phase_us = 328s).

  • Per-drain efficiency spread: 2.08–7.46, median 4.74.

  • Heaviest drain: 71s CPU in 16.3s wall on 2,529 paths.

3. Attribution

Hypotheses tested:

Hypothesis

Verdict

Evidence

Rayon scheduling overhead

Falsified

Control spin scales to 7.31/8 (near-linear). Rayon provides no friction for uniform work.

Per-item diagnostics overhead

Falsified

diag vs bare: efficiency 3.32 vs 3.31 (statistical zero). Atomics, span enter, heap = negligible.

Memory-bandwidth saturation

Partially true (minor)

Per-item median rises 91.6ms→98.9ms (1→8 threads) = +8%. Cannot explain 3.3 vs 8.0 gap.

Work-stealing load imbalance under skew

CONFIRMED — dominant cause

LPT static partition at 8 threads: 7.80/8 vs rayon 4.91/8. Same threads, same solver, same bandwidth. 35% wall reduction.

Root cause

The heavy-CL capture workload has extreme cost skew: the top 8 of 80 paths (10%) account for 60% of total CPU. Path 501 alone costs ~18 seconds — longer than the ideal 8-thread makespan for 72 of the 80 paths.

Rayon’s work-stealing splits work in half lazily; when a worker steals, it takes the easy half (shallow on its work queue). The heavy items stay on the original worker’s queue and, being unsplittable (one path = one rayon task), they serialize the tail: 7 threads sit idle while one grinds through an 18s path.

LPT pre-balances: sort paths by descending cost, greedily assign each to the least-loaded bin. With 8 bins, the four 18s paths go to 4 different threads; the remaining 76 paths fill the gaps. No thread is left idle with an unsplittable giant while others wait.

Why production shows 4.21 (not 4.91)

Production drains average ~284 paths (vs the 80-path harness), and the closure adds span enter + atomics + heap + capture check + profit-envelope gate. The larger item count provides more stealing opportunities (partially compensating for the scheduling deficiency), but the fundamental skew — a handful of multi-second paths per drain — remains. The production K-slowest heap names these paths every drain; they are the same shapes as path 501 in the harness.

4. Intervention ranking

#

Intervention

Predicted wall impact

Complexity

Risk

1

LPT static partition (replace rayon par_iter with scoped threads + cost-proxied bin packing)

−35% solve wall at 8 threads

Medium (new dispatch path + cost proxy)

Low (cutover gate, A/B against rayon)

2

Solver-side CPU reduction on path 501-class paths (the 18s giants)

Multiplies through all threads at any efficiency

High (solver math)

Medium

3

Thread-count tuning vs 8-CPU cgroup quota

Marginal

Trivial

Low

4

Thread-local accumulators replacing per-item atomics

<1% (diag overhead is noise)

Low

Low

Recommended: T3 implements #1. Cost proxy for LPT binning at resolve time: ∑ word_boundary_prices.len() across the path’s CL hops (available without solving, correlates with walk combinatorics). The per-drain solve then uses std::thread::scope with 8 LPT bins instead of par_iter.

5. Environment

  • Host: AMD Ryzen 9 5900X 12-core / 24-thread.

  • cgroup: cpu.max = 800000 100000 → 8 CPUs quota.

  • Rayon pool (production): 8 threads (named degenbot-solve-{i}).

  • std::thread::available_parallelism() = 8 (cgroup-aware).

6. Artifacts

  • Harness: rust/crates/engine/degenbot-solvers/examples/rayon_scale_probe.rs

  • Fixture: rust/crates/engine/degenbot-solvers/tests/fixtures/heavy_cl_solve_captures.jsonl

  • Raw CSV: /tmp/raypar80.csv (80-path), smoke run inline (40-path).

  • ergo: epic 7MKIR7, task 5A3C2P (harness), task QXEVGN (this report).