Are we fast yet? Benchmarking interactive exact scheduling

Firefox has a website called Are We Fast Yet?. It tracks, benchmark by benchmark, whether the browser has caught up to its rivals — publicly, honestly, including the runs where the answer is "not yet." We like that culture. So this is our version for the interactive scheduling engine: the numbers, the methodology, the places we win by a mile, and the honest edges we haven't sanded off yet.

The short answer: for the interactive job — recolour the whole rota on every click, exactly — yes, we're fast. The long answer is more interesting, because "fast" for an engine like this isn't one number.

What "fast" even means here#

Most solver benchmarks measure one thing: time to a solution. Hand the engine a rostering problem, wait, get a rota. On that axis everyone is fast — a single valid rota is milliseconds of work for any modern constraint solver, ours included. It's not the interesting question.

The interesting question is the one the demo asks on every click: across all valid rotas, which cells are forced, which are impossible, and which are still free? That three-colour map is a different beast — computing it exactly is NP-hard in the worst case — and it's the thing a manager actually needs when they're deciding one cell at a time.

So we hold ourselves to three numbers, not one:

1. The map — batch time to compute the full three-colour verdict for a whole roster. This is the head-to-head against other solvers.
2. The click — latency for one interactive move: pin a nurse, recompute what's still possible, repaint. This is the number the product lives or dies on.
3. The thousandth click — does the engine still behave on a long session, or does it slow down and fall over? Benchmarks almost never measure this. For an interactive tool it's decisive.

Here's where we stand on each.

1. The map: against the industry standard#

We benchmark against Google OR-Tools (CP-SAT) — the open-source constraint solver most of the industry reaches for. Every engine solves a byte-identical instance, and we cross-check the three-colour verdict cell-for-cell, so the comparison can't be gamed by cutting a corner on correctness.

Wall-clock to compute the complete three-colour map — single-threaded for us, all sixteen cores for OR-Tools:

The gap is not subtle. The small roster's entire three-colour map takes our engine 4 milliseconds; OR-Tools' best strategy takes half a second — about 130× slower. On the medium roster it's 12 ms versus 11 seconds — nearly 900×. And those are OR-Tools' good numbers, on all sixteen cores; ours are on one.

The row that matters most is the last — a real zero-slack regional hospital, 1,764 cells, coverage so tight that almost every cell is forced. This is the case that breaks general solvers, and it does: given a full three minutes on every core, OR-Tools certifies 100 of the 1,764 cells with its optimised strategy, and 1 with the textbook one. Reasoning Layer certifies all 1,764 — in 128 milliseconds. That's not "faster." That's finished versus not.

A fairness check. You could reasonably object that this pits our whole optimised engine against OR-Tools out of the box. So here's the cleanest apples-to-apples we can run: hold the strategy fixed — the textbook "ask twice per cell" probe — and swap only the solver underneath. On that byte-identical algorithm, our in-house CDCL beats OR-Tools' CP-SAT by 10.9× on the small roster, 18.5× on the medium, and 23.2× on the multi-shift regional. Same questions, same order, nothing different but the engine answering them. Our headline numbers are faster still because the real engine does more than probe — it fronts the solver with cheap polynomial filters (we get to those below) — but even stripped to the plain strategy, the core is an order of magnitude quicker.

And we check our work. On every instance both engines finish, their three-colour verdicts agree cell-for-cell. Speed means nothing if the answer is wrong, so we verify it isn't — the comparison can't be won by cutting a corner on correctness.

Why the gap? The map is a pile of tightly-related SAT questions, and our engine is a native CDCL solver that carries its learned clauses from one question to the next — every "no such rota" it proves makes the next question cheaper. CP-SAT is a heavier, more general machine that largely re-derives each query from cold. On the first rota that generality is free; on the thousandth closely-related query it's the whole cost.

2. The click: and it gets faster as you go#

The batch map is the stress test. The product is the click. So we captured a real session — a manager pinning nurses through a 137-click walk of a live multi-shift roster (54 nurses over 18 days, ~2,900 cells — larger than the benchmark set above) — and timed every recompute end to end.

Every click came back in under 1.7 seconds, ~330 ms on average, and — the part we didn't expect the first time we saw it — latency drops as the session goes on, from ~720 ms early to ~50 ms by the end.

That's the opposite of how "generate then edit" schedulers feel, where every edit triggers another full regeneration and the tool gets no smarter as you work. Ours gets faster the more you decide, for a concrete reason: each pin shrinks the set of still-open cells the engine has to reclassify. Early on, most of the grid is yellow and there's a lot to check. Thirty pins later, the space has collapsed toward a handful of valid rotas, most cells are already settled, and each new click only has to re-examine what's genuinely still in play. The engine reuses the previous answer and computes the delta, not the whole board from scratch.

A few hundred milliseconds a click — sub-second on all but the earliest few — on a real hospital-sized roster, on a single core, getting quicker the deeper you go. That's the number the "recolour on every click" promise rests on.

3. The thousandth click: staying fast#

Here's the axis benchmarks skip, and the one that nearly bit us.

An interactive engine that leaks memory isn't fast — it's a countdown. It can post beautiful per-click latencies and then fall over at click sixty when the process runs out of RAM, taking every open session with it. "Time to first answer" tells you nothing about that. So we treat steady-state memory over a long session as a first-class benchmark number, right next to latency.

Getting there took real work on the engine's internals — an incremental solver that reuses warmth across clicks has to be disciplined about releasing the state it no longer needs, and a subtle leak deep in the constraint machinery meant it wasn't. We hunted it down by instrumenting the running process rather than guessing, and fixed it at the root.

The result, on that same 137-click session:

• Memory: flat at ~2.3 GB, start to finish. No creep, no step-function jumps, no drift — click 1 and click 137 sit at the same footprint.
• No degradation. Latency improves over the run (above); it doesn't rot.
• 137 clicks and counting, where an unbounded version would have died around 60.

Flat memory and falling latency across a long session is, for an interactive engine, the whole game. A solver that's quick on a cold benchmark but bloats under real use isn't fast where it counts.

Why the engine is quick#

None of the above is a trick; it's the shape of the engine. Three ideas do the work:

An exact certifier, warm. Underneath is a native CDCL SAT solver that we drive directly, keeping its learned clauses hot across the thousands of related queries a session generates. It is the sole authority on every verdict — no approximation ever decides whether a cell is forced.

Cheap filters in front of it. Most cells in a real roster are easy — obviously forced or obviously free — and it would be wasteful to spend a SAT proof on each. So a stack of polynomial pre-filters skims those off first: a lower-bounded network-flow relaxation of the coverage constraints, a per-nurse automaton for the temporal rules (no double shifts, rest windows), symmetry collapsing over interchangeable nurses, and a witness-swap argument that proves a cell "free" by exhibiting one valid exchange. Each is sound — it can only ever hand the certifier less work, never a wrong answer.

Deltas, not redraws. The interactive path never recomputes the board. It reuses the previous three-colour state, applies the one new pin, and reclassifies only the cells that could have changed — which is why the click gets cheaper as the session narrows.

The division of labour is the point: heuristics make it fast, the CDCL certifier makes it exact, and the two never trade places.

Where we're not fast yet#

Are We Fast Yet? is only worth reading because it publishes the losses too. Here are ours.

• The worst case is still NP-hard. Computing the complete map is NP-hard for every engine, ours included; a single forced cell can, in principle, demand an exponentially long certificate, and no solver escapes that. On the instances we benchmark — up to and including the zero-slack regional hospital — the exact engine certifies every cell (all 1,764 of the hardest one, in 128 ms). But "we finished all of these" is not "we finish everything," and we won't dress it up as the second thing.
• The multi-shift cold render is our slow spot. Most maps land in milliseconds; the multi-shift regional takes ~5 seconds. Multi-shift rosters add a per-day auxiliary variable for each nurse that blunts the polynomial filters, so more of the board falls through to the SAT certifier. It's the one instance where the first paint is a short wait rather than an instant — the clicks after it are still sub-second.
• One core. Every number here is single-threaded. OR-Tools was handed sixteen cores and still lost, badly — but the honest reading is that our parallelism is headroom we haven't spent yet, not a box we've ticked.

None of these dents the product claim — sub-second exact recolouring on every click, flat memory across a long session — but they're the honest edges of it, and the roadmap.

See for yourself#

The benchmark is reproducible: the problem instances are committed, every engine solves the same bytes, and our verdicts are checked cell-for-cell against OR-Tools'. We didn't pick the instances that flatter us — the multi-shift regional hospital is the one we're slowest on, and it's right there in the table.

The best benchmark, though, is your hand on the grid. ▶ Open the live scheduler, pin nurses, and watch the board recolour — and watch each click come back a little quicker than the last.

When you want to see it against your roster — your roles, your ratios, your rules — 👉 sign up for a demo. Bring the instance that scares your current scheduler; that's the one we want to run.

Are we fast yet? For the job that matters — keeping every valid schedule visible, exactly, in real time — yes. And we left the receipts.