Differential tests

Every optimisation in this book is only allowed to be faster — never to change the answer. Each suite below runs a deliberately slow, obviously-correct implementation alongside the optimised one and compares them. This is chapter 42, executing in your browser rather than being described.

A golden corpus and a slow oracle

These are not recorded results. Press run and both implementations execute, right here, and get compared.

show passing checks

Golden corpus

D1 = "kubernetes deployment"
D2 = "docker deployment"
D3 = "kubernetes service"

kubernetes             → D1, D3
deployment             → D1, D2
kubernetes AND service → D3
"kubernetes deployment"→ D1

Small enough to verify by eye. That is the requirement — a golden corpus you cannot check by hand is just another implementation.

Differential testing

same query
    ├─→ reference engine  → expected
    └─→ optimised engine  → actual

           equal?
        yes → correct
        no  → investigate

The reference is allowed to be slow. It is allowed to be embarrassing. It is not allowed to be deleted, because it is the only thing that can tell you the fast path is still right.

Nothing has run yet. Press run the suite.

What differential testing is especially good at

area	reference	optimised
fuzzy search	brute-force edit distance over every term	Levenshtein automaton + trie/FST
postings compression	the in-memory objects	gap + vint + bit-packed bytes
term dictionary	a sorted array	trie → minimized automaton → FST
range queries	check every value	binary search / BKD
top-K	score every candidate	WAND with upper-bound pruning
distribution	one index	shards, replicas and a global merge