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.
The changes below made the measured level-3 searches 4.1× to 20.8× faster on an 8-core Apple M1. The new, optional turbo mode preserves the single best match; lower-ranked results can vary with 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.
A level-3 search for an “ugly” target — a number with no clean closed form — looked like this on my 8-core machine:
Generation: ~1.0 s
Search: ~14.8 s
Newton calls: 22,817,186
Pool insertions: 17,586,629 (final pool size: 16)Two things jumped out.
First, generation was not the problem. I had assumed that enumerating millions of expressions was the cost. It was about one second of sixteen. The real cost was the matching phase: twenty-three million Newton-Raphson refinements, each trying to solve LHS(x) = RHS to high precision.
Second, the result pool was thrashing. To return sixteen matches it performed seventeen million insert-and-evict cycles. The pool was doing enormous work to keep almost nothing.
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
My initial instinct was to optimize a function in the generation hot loop that allocated two small vectors on every call. I rewrote it to allocate nothing. It is a better function, and I kept it.
It made no measurable difference to the benchmark, because generation was never the bottleneck.
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
Level 3, sixteen requested matches, 8 cores, serial deterministic versus turbo (full exhaustive search, no early stopping). Apple M1, 16 GB RAM, MacBook Air, macOS, native release build; times are the median of three runs:
| Target | Serial | Turbo | Speedup |
|---|---|---|---|
2.506314 (no clean form — worst case) |
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π |
71.3 s | 3.4 s | 20.8× |
Reproduce with ries-rs 2.0.2 (commit 0904c3e), median of three exhaustive runs: ries-rs 2.506314 -l3 -n16 --deterministic vs. --turbo.
A few caveats. The speedup grows with search size: 2π is the largest workload (about 71 s serial) and parallelizes best (20.8×), while the smaller 2.506314 search (about 16 s) reaches 4.1× — the spread is load-balancing overhead on small workloads, not varying core counts, and 2.506314 (no clean closed form, a genuine grind) is the fairest single number. Turbo’s best match is identical to serial’s on every target here; that rank-1 parity is pinned by a regression test. Turbo costs memory for the speed: about 420 MiB at level 3 versus roughly 260 MiB for serial’s memory-bounded streaming path. It 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 remaining cost is in the search model: the search is exhaustive and error-first by design — it refines every plausible candidate to high precision, then ranks. Most of what follows is a consequence of that.
Load balancing. Turbo splits work into complexity-ordered bands, but the high-complexity bands carry far more work than the low ones, so work-stealing leaves smaller searches under-parallelized — which is why 2.506314 reaches only 4.1× while 2π reaches 20.8×. Finer-grained scheduling would lift the small-workload cases toward the large ones.
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.