I optimized the wrong part of ries-rs first

ries-rs is my Rust reimplementation of Robert P. Munafo’s RIES: give it a number and it searches for equations with that number as a solution. Some searches were taking more than a minute. I wanted to know where the time went.

In the end, turbo was 4.1× to 20.8× faster than the serial path in four level-3 comparisons on an eight-core Apple M1. Those were timings of two different search paths. Turbo preserves the single best match, with lower ranks allowed to vary by thread count. Deterministic mode still provides repeatable result sets.

Where we started

RIES runs a pipeline: generate candidate equations, match each by refining LHS(x) = RHS to high precision, and rank the survivors into a bounded pool. A level sets how complex the equations are allowed to get; this post measures level 3.

I expected enumerating millions of expressions to be the expensive part. The profile of a level-3 search for a target without an obvious closed form showed where those seconds actually went.

Generation

≈ 1.0 s

Search

≈ 14.8 s

Original level-3 profile. The search made 22,817,186 Newton refinement calls and 17,586,629 pool insertions. The final pool held 16 matches.

Generation took about one second out of sixteen. What made me stop was the last counter. For every match left in the pool at the end, there had been more than a million insertions. I wanted to know what made so many candidates worth keeping, even briefly.

The existing --parallel mode did not help here — a surprise until I read my own code and realized it only parallelizes generation. The dominant matching phase stayed single-threaded on purpose, to preserve a guarantee I will come back to. So on a matching-bound workload, parallel mode was essentially break-even.

An optimization outside the bottleneck

A function in the generation hot loop allocated two small vectors every time it ran. The allocations were easy to spot, and in a loop that enumerates millions of expressions they looked expensive. I rewrote the function to allocate nothing and measured again. The difference was too small to measure. I kept the rewrite and went back to the pool.

Fixing the ranking model (which also fixed quality)

Once I looked at the pool, the thrashing made sense — and it pointed at a ranking bug, not just a speed bug.

The pool ranked matches first by exactness, then by absolute error. The problem: once a match is “exact” within floating-point tolerance, its remaining error is noise, down at the 10⁻¹⁶ level. Ranking exact matches against each other by that noise meant a complicated equation with a slightly smaller rounding residual would outrank a simple, beautiful one.

Concretely, for a target of 2π, a dense complexity-123 expression could beat plain x = 2π because its residual happened to be a few bits smaller. That is backwards. RIES is supposed to prefer simplicity.

The fix was to treat all sub-tolerance matches as equally exact and let complexity decide between them. This makes the pool prefer simpler equations and stabilizes its contents.

With complexity ranking, a pool full of exact matches also gives the search a cutoff: an equation more complex than the most complex match still in the pool cannot improve it. An intermediate candidate can still displace that worst match, and equal-complexity candidates still need the ranking tie-breaks. The implementation uses this ceiling to skip refinements, and can stop when the remaining candidates must exceed it.

Correction, September 21: this paragraph previously said “simplest.” The pool’s implementation and regression test use the worst retained exact match.

Parallel matching and reproducibility

The obvious way to attack twenty-three million independent Newton calls is to spread them across cores. It should be embarrassingly parallel.

Except ries-rs makes a promise, pinned by a test: parallel search returns the exact same result set as serial search, byte for byte. That promise is why --parallel only touches generation. It is valuable — it means a reproducible run is reproducible regardless of how many cores you have.

A naive parallel matcher breaks that promise. Split the candidates across workers, give each its own bounded pool, merge the results, and the marginal ranks diverge: each worker’s pool tightens its acceptance thresholds independently, so different workers keep slightly different sets. I tried it. It broke nine tests, and worse, in one early version it dropped the best match entirely. I reverted it.

I added a separate --turbo mode that preserves the best match but allows lower-ranked results to vary. Deterministic mode keeps its existing guarantee.

What turbo mode guarantees

--turbo parallelizes the matching phase across every core.

Here the earlier ranking fix paid off. Because exact matches now rank by complexity instead of by residual noise, an exact match is discovery-order-independent — whoever finds it scores it the same way. And an exact match’s right-hand side always sits well inside any worker’s search window, so no worker can miss one that the serial path would have found.

The documented guarantee is:

Turbo returns the same single best match as serial search. The global best is rank one within whichever worker owns it, so it is never evicted; and a worker that sees a subset of the candidates uses a search radius at least as wide as serial’s, so it cannot miss what serial found. After merging, the best result sorts to the top.

What turbo does not promise is the lower-ranked tail. When more matches qualify than you asked for, each worker keeps only its own top-k, so the merged tail is a valid top-k but not necessarily the same one, and it can vary with thread count. It also uses more memory, because it materializes the full candidate set instead of streaming it.

My first draft claimed turbo returned the same exact-match set as serial. A counterexample ruled that out: under classic ranking there can be hundreds of equally-simple exact forms, and the parallel workers each kept a different sixteen. The documentation and tests now specify the narrower guarantee: the single best match.

The final numbers

These are the original timings for ries-rs 2.0.2 at level 3, with sixteen matches requested. I used a native release build on an eight-core Apple M1 MacBook Air with 16 GB of RAM. Each time is the median of three runs. Both modes could use their normal pruning rules, with first-match stopping disabled.

Target	Serial	Turbo	Speedup
2.506314 (no obvious closed form)	16.4 s	4.0 s	4.1×
π/2	10.4 s	1.9 s	5.5×
3.301	30.7 s	4.3 s	7.1×
2π (slowest serial run)	71.3 s	3.4 s	20.8×

The 20.8× result compares two different matchers. For 2π, the serial path crosses its two-million-expression guard and matches left-hand sides as it generates them. Turbo keeps the expressions in memory, sorts the left-hand sides by complexity, and sends bands to worker pools. The batch matcher can skip refinements using the complexity ceiling described above. The serial streaming matcher works in generation order and lacks that cutoff. The comparison captures both parallel work and work avoided.

I checked the work directly in a separate 2π rerun of 2.0.2. Serial called Newton refinement 97.3 million times. Turbo called it 1.14 million times. Both returned x = 2π first. To inspect those counters, check out commit 0904c3e in a clone of the ries-rs repository and build its native CLI. Disable report mode so the pool holds sixteen entries:

git checkout --detach 0904c3e
cargo build --release --locked --bin ries-rs
./target/release/ries-rs 6.283185307179586 -l3 -n16 \
  --report false --deterministic --json
RAYON_NUM_THREADS=8 ./target/release/ries-rs 6.283185307179586 -l3 -n16 \
  --report false --turbo --json

Turbo’s best match agreed with serial’s on every target in the table. Turbo also used more memory. The original level-3 measurements were about 420 MiB for turbo versus roughly 260 MiB for serial. Turbo is opt-in, and --deterministic disables it.

These measurements are for the native release. The browser demo uses a separately bundled sequential build; its footer identifies that version. It does not run turbo mode.

Where it can still go

The search still generates expressions up to the level’s complexity limit. How it orders and filters those expressions determines how often it has to run Newton’s method.

Load balancing. Turbo splits work into complexity-ordered bands. Equal numbers of expressions can take very different amounts of time to match. Finer-grained scheduling could help when a few expensive bands dominate the run.

Search order. The original RIES is fast partly because it searches in complexity order and stops early. The complexity-ceiling pruning I added skips some work. Organizing the whole search around complexity could avoid more Newton refinements, but would require changing the search algorithm.

The streaming path is still serial. At very high levels the engine streams to bound memory, and turbo can’t help there yet because there is no materialized candidate set to divide. A streaming parallel matcher is harder but possible.

Requesting more matches fills the pool with noise. Asking for sixteen results when a number only has two simple forms means the pool pads the rest with complex junk, which keeps the pruning ceiling high and defeats early exit. Smarter handling of “this number simply doesn’t have sixteen good answers” would help the common interactive case.

You can try the solver on the project page, run it in the browser demo, or read the search model and turbo contract in the repository.