Performance and speedup

A software speedup, proved against the specification.

Improving performance means making the code run more efficiently without changing what it is supposed to do. We use Lean 4 and formal verification so an optimisation can be kept, and checked, as the software changes.

The compiler supplies the speed. The proof checks the behaviour.

Tell us about the workload

Why a speedup is hard to keep

The first difficulty is knowing the faster code still does what it was designed to do. A test only covers the cases it was written for. A change that works in one situation can still cause problems elsewhere.

The second is keeping the improvement as the software develops. A compiler update, a change to the build settings, or a small edit can affect how the program runs. We write the software in Lean 4 so the code and the specification are developed together, and a proof checks that the optimised code still behaves as the specification allows.

Where the speed comes from

01

A hot function

A parser, a validator, a routing rule, or another operation that runs often enough to matter. You do not need to rewrite the whole application to start.

02

The compiler

The candidate compiles to C, and C compiles to LLVM IR. Clang can vectorise a hot loop, for example at -O2 -mavx2. The proof is about the instructions that were emitted, not a vector version written by hand.

03

The whole system

LeanIn is an experimental concurrency runtime for Lean 4, with machine-checked proofs you can run yourself. In one pipelined HTTP test it handled around three times as many requests per second as Node 22. That figure depends on the workload, and it is not a guarantee.

A practical example

A JSON parser shows the same path on one program. The scanner’s byte transition is an executable definition in Lean, already proved against the reference. The rule is then written as C, in a fragment the Lean semantics can model.

Clang compiles it at -O2 -mavx2. The hot loop is vectorised by the compiler: three AVX2 lane masks classify quote, backslash, and control across a 32-byte window. The LLVM IR is captured and normalised, then parsed back into Lean. A machine-checked theorem relates the emitted instructions to the Lean definition. Every behaviour the code can exhibit is one the specification allows.

The worked example, including what the proof does not claim, is in how to achieve a software speedup with Lean 4. The pipeline itself is on the technology page.

How an engagement works

  1. Specify

    Write what the software needs to do in Lean. The specification is the behaviour later optimisations have to preserve.

  2. Implement

    Write a candidate implementation and optimise it with respect to that specification. Tests only cover the cases they were written for. The proof checks the behaviour the specification defines.

  3. Compile

    Compile through C to LLVM IR. A conditional refinement relates the emitted instructions, including SIMD, back to the Lean definition. Change the C, the flags, or the pragmas, and the proof fails instead of drifting.

  4. Measure

    Record a baseline before changing anything: throughput, response time, or the time one operation takes. Formal verification does not make the code faster. The compiler and the optimisations do.

LeanIn is the experimental runtime behind the system-level result above. Read the benchmarks, including the workloads where it is slower, before treating any figure as more than an experiment.

Tell us what you want to speed up

Send the function or the part of the system, and what it is supposed to do. A small, well-defined example is a good place to start.

Send us a message

Step 1 of 3