Benchmarking against a real corpus
Step 11 of 12, and the engine stops being built and starts being measured. Steps 2 through 10 gave it an index that loads and saves, BM25 with Lucene’s two constants, phrase and boolean queries, typo tolerance, an HTTP front end, and documents added without a rebuild. None of that is worth anything if the answers are wrong or the queries are slow, and neither of those is settled by reading the code. This step measures them.
The starting state is tag search-ch10, the end of step 10: the engine in one src/main.rs, ninety-eight tests, an index file at version 3. The end state is tagged search-ch11. One structural change — the engine becomes a library — and one new command: cargo bench, which grows a corpus, measures latency against two baselines, checks recall against known answers, and counts what the index costs to keep.
A benchmark needs code it can import
Section titled “A benchmark needs code it can import”A Rust benchmark is a separate crate. benches/benchmark.rs compiles on its own, links against the project, and cannot see anything inside src/main.rs — so the engine moves. src/lib.rs now holds the index, the ranker, the query grammar and the tests; src/main.rs keeps what belongs to a binary: arguments, the demo, and the index file’s path. The move is mechanical — the engine’s logic is untouched, and the demo prints exactly what it printed at search-ch10 apart from one new hint line at the end.
The harness is criterion, added the way a benchmark tool should be added: a dev-dependency, so it never reaches the shipped binary.
cargo add --dev criterion@0.8[dev-dependencies]criterion = "0.8"
[[bench]]name = "benchmark"harness = falseharness = false tells cargo not to wrap the file in its own timing harness, because criterion is the harness. The sandbox for this page installs the crate as an ordinary dependency, which is what the one runnable block below needs:
[dependencies]criterion = "0.8"A corpus you can measure
Section titled “A corpus you can measure”The demo corpus is six files in a constant. Six files cannot produce a latency worth printing — a query over six documents finishes before the clock starts. A benchmark corpus needs hundreds or thousands of documents, a realistic term distribution, and one thing natural text does not have: known correct answers.
So the corpus is generated. Not gathered — generated, with a deterministic generator, a Zipf distribution over a 512-term dictionary, document lengths between 40 and 160 terms, and twenty-four queries whose relevant documents are planted on purpose. The words are labels — term0000, term0055 — and that is deliberate too: every label is its own stem, none is a stop word, and lowercasing changes nothing, so step 3’s tokeniser is the identity on this corpus. The benchmark measures the index, not the normaliser, and the run asserts that identity on the first fifty documents rather than assuming it.
use std::time::Instant;
const SEED: u64 = 31337;const VOCABULARY: usize = 512;const CORPUS: usize = 2000;
struct Rng(u64);
impl Rng { fn next_u64(&mut self) -> u64 { self.0 ^= self.0 << 13; self.0 ^= self.0 >> 7; self.0 ^= self.0 << 17; self.0 }
fn below(&mut self, bound: usize) -> usize { (self.next_u64() % bound as u64) as usize }}
fn term(index: usize) -> String { format!("term{index:04}")}
fn zipf_table(n: usize) -> Vec<f64> { let mut cumulative = Vec::with_capacity(n); let mut total = 0.0; for rank in 1..=n { total += 1.0 / rank as f64; cumulative.push(total); } let sum = cumulative[n - 1]; cumulative.iter().map(|value| value / sum).collect()}
fn sample_term(cumulative: &[f64], rng: &mut Rng) -> usize { let draw = (rng.next_u64() % 1_000_000) as f64 / 1_000_000.0; match cumulative.iter().position(|mass| draw <= *mass) { Some(rank) => rank.min(cumulative.len() - 1), None => cumulative.len() - 1, }}
fn main() { let mut rng = Rng(SEED); let cumulative = zipf_table(VOCABULARY);
let mut words = 0usize; let mut document = String::new(); for id in 0..CORPUS { let length = 40 + rng.below(121); document.clear(); for _ in 0..length { if !document.is_empty() { document.push(' '); } document.push_str(&term(sample_term(&cumulative, &mut rng))); } words += length; if id == 0 { println!("doc 0000: {document}"); } }
println!("corpus: {CORPUS} documents, {words} words, vocabulary {VOCABULARY}"); for rank in 0..5 { println!("rank {rank}: mass {:.4}", cumulative[rank]); }}doc 0000: term0003 term0000 term0013 term0101 term0069 term0000 term0034 term0051 term0000 term0000 term0255 term0000 term0057 term0005 term0002 term0001 term0004 term0000 term0022 term0018 term0001 term0038 term0097 term0000 term0003 term0064 term0316 term0000 term0010 term0009 term0000 term0004 term0153 term0003 term0263 term0004 term0427 term0004 term0297 term0005 term0001 term0007 term0011 term0083 term0012 term0180 term0066 term0166 term0004 term0088 term0142 term0061 term0012 term0000 term0404 term0450 term0012 term0007 term0095 term0012 term0481 term0489 term0002 term0006 term0001 term0015 term0123 term0008 term0014 term0004 term0088 term0002 term0003 term0000 term0001 term0262 term0075 term0036 term0189 term0032 term0011 term0219 term0001 term0183 term0027 term0000 term0000 term0005 term0000 term0393 term0026 term0000 term0075 term0235 term0323 term0049 term0065 term0005 term0235 term0023 term0256 term0149 term0090 term0011 term0000 term0005 term0007 term0063 term0000 term0105 term0114 term0003 term0039 term0000 term0001 term0000 term0002 term0003 term0001 term0006 term0424 term0001 term0000 term0020 term0000 term0003 term0052 term0223 term0008 term0209 term0006 term0001 term0014 term0182 term0002 term0008 term0003 term0000 term0021 term0004 term0001 term0255 term0029 term0002 term0018 term0168 term0177 term0005 term0002 term0012 term0224corpus: 2000 documents, 197401 words, vocabulary 512rank 0: mass 0.1467rank 1: mass 0.2201rank 2: mass 0.2690rank 3: mass 0.3056rank 4: mass 0.3350What the planting buys is exact ground truth. Each query term is written into five chosen documents eight times, against the one or two incidental mentions it collects everywhere else. Recall is then a measurement — of the 120 relevant documents, how many land in the top ten — not a matter of opinion. The typo is generated the same way: the first character of the label changed, one edit from the intended term.
The corpus is the same on every machine because the generator is a seeded linear congruential generator, and the same on every run for the same reason. That matters more than it sounds: a benchmark that measures different data each run is measuring the data as much as the code. What this corpus is not is natural language. It has no sentences, no punctuation, and no structure, and its build cost excludes the tokeniser’s share of a real collection. The numbers below are about the index; a gathered corpus would move them and would not change the method.
Measuring latency with criterion
Section titled “Measuring latency with criterion”Timing a loop by hand — Instant::now(), run it a thousand times, divide — measures whatever the machine was doing that second, including the warm-up. Criterion does the parts that are easy to get wrong: it warms the code up first, then collects a configurable number of samples over a configurable measurement time, reports the median with a confidence interval, and keeps a baseline so a second run prints the change against the first. black_box stops the optimiser from deleting the work: a query whose result is never used is a query the compiler is free to skip.
The block below is the baseline scorer — the same BM25 the engine uses, inline so the block stands alone — measured over a stand-in corpus of a thousand short documents, at two sizes:
// The brute-force scan — the engine's baseline, over a stand-in corpus of// one thousand short documents — measured the way the benchmark file// measures it: warmed up, sampled, and timed by criterion.
use criterion::Criterion;use std::hint::black_box;use std::time::Duration;
/// BM25's two constants, at the values Lucene ships.const K1: f64 = 1.2;const B: f64 = 0.75;
/// BM25's term-frequency component — the engine's formula, inline so this/// block stands alone.fn tf_score(tf: u32, dl: f64, avgdl: f64) -> f64 { tf as f64 * (K1 + 1.0) / (tf as f64 + K1 * (1.0 - B + B * dl / avgdl))}
/// The scan: count the term in every document, score what holds it, sort./// No index, no dictionary — the obvious way to search.fn scan(documents: &[Vec<&str>], term: &str) -> Vec<f64> { let n = documents.len(); // The idf needs the document frequency, and the only way to know it // is to look at every document first. let df = documents.iter().filter(|terms| terms.contains(&term)).count(); if df == 0 { return Vec::new(); } let weight = (n as f64 / df as f64).ln(); let avgdl = documents.iter().map(|terms| terms.len() as f64).sum::<f64>() / n as f64; let mut scored: Vec<f64> = documents .iter() .filter_map(|terms| { let tf = terms.iter().filter(|&&word| word == term).count() as u32; (tf > 0).then(|| weight * tf_score(tf, terms.len() as f64, avgdl)) }) .collect(); scored.sort_by(|a, b| b.total_cmp(a)); scored}
/// The stand-in corpus: a thousand documents of twenty terms each, words/// picked by a stride so that no term is in every document. Enough work/// to measure, small enough to fit in one block.const WORDS: [&str; 40] = [ "borrow", "checker", "owner", "value", "scope", "lifetime", "iterator", "lazy", "adapter", "closure", "capture", "thread", "channel", "mutex", "atomic", "future", "await", "spawn", "panic", "result", "option", "error", "match", "enum", "struct", "trait", "generic", "bound", "where", "impl", "reference", "mutable", "shadow", "tuple", "array", "slice", "vector", "hash", "string", "index",];
fn main() { let documents: Vec<Vec<&str>> = (0..1_000u32) .map(|doc| (0..20).map(|slot| WORDS[((doc * 7 + slot * 13) % 40) as usize]).collect()) .collect();
let mut c = Criterion::default() .warm_up_time(Duration::from_millis(500)) .measurement_time(Duration::from_secs(1)) .sample_size(50); // The same scan over a tenth of the corpus and over all of it: the // scan's cost is the corpus size, which is the whole problem an // index solves. c.bench_function("scan/100", |b| { b.iter(|| scan(black_box(&documents[..100]), black_box("borrow")).len()) }); c.bench_function("scan/1000", |b| { b.iter(|| scan(black_box(&documents), black_box("borrow")).len()) }); c.final_summary();}scan/100 time: [42.521 µs 42.691 µs 42.896 µs]
scan/1000 time: [416.72 µs 418.37 µs 420.23 µs]Found 2 outliers among 50 measurements (4.00%) 2 (4.00%) high mildTwo things in that output are the point. The scan over a hundred documents costs a tenth of the scan over a thousand: the baseline’s cost is the corpus size, which is the whole problem an inverted index exists to solve. And the numbers carry a [low mid hi] interval, not a single figure — a latency measured once is an anecdote.
One note on reading the real run below: the numbers come from the optimised bench profile, so they say nothing about cargo run, which builds the demo unoptimised. And because criterion keeps its own baseline, your second cargo bench prints change lines next to these numbers.
What the benchmark measures
Section titled “What the benchmark measures”The file below is benches/benchmark.rs at tag search-ch11, byte for byte. It grows the corpus, asserts the tokeniser identity, then measures seven things with criterion and prints three reports with Instant.
//! The benchmark. `cargo bench` runs it.//!//! Three questions, in order://!//! 1. **Latency.** How long the engine takes to build an index and to//! answer a query, measured by criterion — and how long the obvious//! implementation takes to answer the same query by reading every//! document. That second number is the comparison the index exists to//! win.//! 2. **Recall.** Whether the answers are right. The corpus is generated//! with queries whose relevant documents are known by construction, so//! recall is a measurement rather than a feeling.//! 3. **Memory.** What the index costs to keep: bytes on disk against the//! bytes of text it was built from.//!//! The corpus is deterministic — the same seed grows the same documents on//! every machine — so the recall numbers are the same everywhere. The//! latencies are not: they come from one machine, one run, and they move//! between runs and between machines. Criterion keeps its own baseline, so//! a second run prints a change line next to the first run's numbers.
use criterion::Criterion;use haystack::{idf, tf_score, tokenize, Index, B, K1};use std::hint::black_box;use std::time::{Duration, Instant};
/// The seed. A constant, so a benchmark run anywhere measures the same/// documents — a corpus that changed every run would be measured as much/// as the code was.const SEED: u64 = 31337;
/// How many distinct terms the corpus's dictionary holds.const VOCABULARY: u64 = 512;
/// How many documents the benchmark indexes.const CORPUS: u64 = 2_000;
/// How many queries carry known answers.const QUERIES: u64 = 24;
/// How many documents each labelled query is planted in.const RELEVANT: u64 = 5;
/// How many times the query term is planted in each relevant document —/// against the one or two incidental mentions everywhere else.const PLANTED: u64 = 8;
/// A 64-bit linear congruential generator. Not a good random number/// generator; a reproducible one, which is what a benchmark needs. The/// same seed produces the same sequence on every machine.struct Rng { state: u64,}
impl Rng { fn new(seed: u64) -> Self { Rng { state: seed } }
fn next(&mut self) -> u64 { self.state = self .state .wrapping_mul(6_364_136_223_846_793_005) .wrapping_add(1_442_695_040_888_963_407); self.state }
/// A number below `bound`. fn below(&mut self, bound: u64) -> u64 { self.next() % bound }}
/// The label of the term at `rank`: `term0000` for the most common,/// `term0511` for the least.////// The labels are not English, and that is deliberate. Every one is its/// own stem, none is a stop word, and lowercasing changes nothing, so the/// tokeniser is the identity on this corpus: the benchmark measures the/// index, not step 3's normaliser. The run asserts this below.fn term(rank: u64) -> String { format!("term{rank:04}")}
/// The Zipf weights, as a cumulative table: entry `i` is the total weight/// of terms `0..=i`. A uniform draw lands on the first term whose/// cumulative weight passes it, which makes common terms common — a/// handful of terms in a large slice of the corpus, a long tail of terms/// in a handful of documents each.fn zipf_table() -> Vec<u64> { let mut table = Vec::with_capacity(VOCABULARY as usize); let mut total = 0; for rank in 0..VOCABULARY { total += 1_000_000 / (rank + 1); table.push(total); } table}
/// The term a uniform draw lands on under the Zipf table.fn sample_term(table: &[u64], draw: u64) -> u64 { let total = *table.last().unwrap(); table.partition_point(|&weight| weight <= draw % total) as u64}
/// One generated document: the path it is indexed under, its text, and the/// terms that text is made of.struct Doc { path: String, text: String, terms: Vec<u64>,}
/// Grow `count` documents: lengths between 40 and 160 terms, every term/// drawn from the Zipf table.fn generate_documents(rng: &mut Rng, count: u64, table: &[u64]) -> Vec<Doc> { (0..count) .map(|id| { let length = 40 + rng.below(121); let terms: Vec<u64> = (0..length).map(|_| sample_term(table, rng.next())).collect(); Doc { path: format!("docs/doc{id:05}.md"), text: terms.iter().map(|&rank| term(rank)).collect::<Vec<_>>().join(" "), terms, } }) .collect()}
/// A query with known answers: the term as the index holds it, the/// documents it was planted in, and the same term with one character/// changed — what a reader types by mistake.struct Labelled { /// The term's rank in the vocabulary. rank: u64, /// The documents the term is planted in: the relevant ones. relevant: Vec<u64>, /// The term with its first character changed, one edit away. typo: String,}
/// One character of the label changed. On this dictionary the typo is one/// edit from the intended term and two from its neighbours, which is what/// makes the radius-2 measurement below interesting.fn typo_of(label: &str) -> String { let mut chars: Vec<char> = label.chars().collect(); chars[0] = 's'; chars.into_iter().collect()}
/// Grow `count` labelled queries, planting each one's term into fresh/// documents. The planting is what makes recall measurable: the relevant/// documents are known because they were chosen, not because someone read/// the text and decided.fn generate_queries(rng: &mut Rng, docs: &mut [Doc], count: u64) -> Vec<Labelled> { (0..count) .map(|_| { // A middle-of-the-dictionary term: common enough to have a // postings list worth ranking, rare enough not to be in // every document. let rank = 40 + rng.below(200); let mut relevant: Vec<u64> = Vec::new(); while relevant.len() < RELEVANT as usize { let candidate = rng.below(docs.len() as u64); if !relevant.contains(&candidate) { relevant.push(candidate); } } relevant.sort_unstable(); for &id in &relevant { let doc = &mut docs[id as usize]; for _ in 0..PLANTED { let at = rng.below(doc.terms.len() as u64) as usize; doc.terms[at] = rank; } doc.text = doc.terms.iter().map(|&rank| term(rank)).collect::<Vec<_>>().join(" "); } Labelled { rank, relevant, typo: typo_of(&term(rank)), } }) .collect()}
/// The baseline: for one term, read every document, count the term, score/// it, sort. No postings, no dictionary — the obvious way to search, and/// the honest comparison, because it is what an inverted index replaces.////// The documents arrive pre-tokenised, which flatters the baseline: a real/// scan would pay the tokeniser too. The comparison errs against the/// index, which is the safe direction to err in.fn brute_force(docs: &[Doc], rank: u64) -> Vec<(u64, f64)> { let n = docs.len(); // The idf needs the document frequency, and the only way to know it // is to look at every document first. let df = docs.iter().filter(|doc| doc.terms.contains(&rank)).count(); if df == 0 { return Vec::new(); } let weight = idf(df, n); let avgdl = docs.iter().map(|doc| doc.terms.len() as f64).sum::<f64>() / n as f64; let mut scored: Vec<(u64, f64)> = docs .iter() .enumerate() .filter_map(|(id, doc)| { let tf = doc.terms.iter().filter(|&&t| t == rank).count() as u32; (tf > 0).then(|| { ( id as u64, weight * tf_score(tf, doc.terms.len() as f64, avgdl, K1, B), ) }) }) .collect(); scored.sort_by(|a, b| b.1.total_cmp(&a.1)); scored}
/// The baseline as a program without an index actually runs it: read the/// text, split it into terms, count. No pre-tokenised shortcut, because/// there is nowhere to cache the terms — every query pays the tokeniser/// again. This is the slower of the two baselines and the honest one for a/// collection that arrives as text.fn brute_force_text(docs: &[Doc], rank: u64) -> Vec<(u64, f64)> { let n = docs.len(); let label = term(rank); // One pass: tokenise every document and count the term in it. The // document frequency falls out of the same pass. let counts: Vec<(u64, u32, usize)> = docs .iter() .enumerate() .filter_map(|(id, doc)| { let tf = tokenize(&doc.text) .filter(|word| word.as_str() == label.as_str()) .count() as u32; (tf > 0).then(|| (id as u64, tf, doc.terms.len())) }) .collect(); let df = counts.len(); if df == 0 { return Vec::new(); } let weight = idf(df, n); let avgdl = docs.iter().map(|doc| doc.terms.len() as f64).sum::<f64>() / n as f64; let mut scored: Vec<(u64, f64)> = counts .iter() .map(|&(id, tf, length)| { ( id, weight * tf_score(tf, length as f64, avgdl, K1, B), ) }) .collect(); scored.sort_by(|a, b| b.1.total_cmp(&a.1)); scored}
/// The median of a list of durations.fn median(mut times: Vec<Duration>) -> Duration { times.sort_unstable(); times[times.len() / 2]}
fn main() { let mut rng = Rng::new(SEED); let table = zipf_table(); let mut docs = generate_documents(&mut rng, CORPUS, &table); let labelled = generate_queries(&mut rng, &mut docs, QUERIES);
let text_bytes: usize = docs.iter().map(|doc| doc.text.len()).sum(); let slots: usize = docs.iter().map(|doc| doc.terms.len()).sum(); println!("corpus: {} documents, {} distinct terms, {slots} term slots, {text_bytes} bytes of text", docs.len(), VOCABULARY); println!( "queries: {QUERIES} labelled, {RELEVANT} relevant documents each, planted {PLANTED} times" );
// The tokeniser is the identity on this corpus — every label is its // own stem and none is a stop word — so the index's terms are the // generator's terms, and the baseline's counts are the index's. for doc in docs.iter().take(50) { let tokenised: Vec<String> = tokenize(&doc.text).collect(); assert_eq!(tokenised.len(), doc.terms.len()); for (word, &rank) in tokenised.iter().zip(&doc.terms) { assert_eq!(*word, term(rank)); } } println!("checked: the tokeniser is the identity on the first 50 documents");
let mut index = Index::new(); for doc in &docs { index.add_document(&doc.path, &doc.text); } println!( "index: {} documents, {} terms, average length {:.1}", index.documents(), index.terms(), index.average_length() ); let pair = adjacent_pair(&docs); let words = [term(pair.0), term(pair.1)]; let refs: Vec<&str> = words.iter().map(String::as_str).collect(); println!( "the phrase benchmark asks about \"{}\": {} documents", refs.join(" "), index.phrase(&refs).len() );
let mut c = Criterion::default() .warm_up_time(Duration::from_millis(500)) .measurement_time(Duration::from_secs(1)) .sample_size(50);
// The one-time cost: building the index over the whole corpus. Every // query after this is free of it, which is the trade the scaling table // below puts numbers on. { let mut group = c.benchmark_group("index/build"); group .sample_size(10) .measurement_time(Duration::from_secs(3)) .bench_function("2000", |b| { b.iter(|| { let mut index = Index::new(); for doc in black_box(&docs) { index.add_document(&doc.path, &doc.text); } index.terms() }) }); }
// The per-query costs. The index is built once, outside the closure: // a benchmark that rebuilt it would be measuring the build. let exact = term(labelled[0].rank); let common = term(0); let second = term(labelled[1].rank); let typo = &labelled[0].typo; c.bench_function("query/exact", |b| { b.iter(|| index.query(black_box(&exact)).unwrap().len()) }); c.bench_function("query/common", |b| { b.iter(|| index.query(black_box(&common)).unwrap().len()) }); c.bench_function("query/boolean", |b| { b.iter(|| { index .query(black_box(&format!("{exact} AND {second}"))) .unwrap() .len() }) }); c.bench_function("query/phrase", |b| { // A pair of terms that really are adjacent somewhere in the // corpus, found by a scan, so the phrase benchmark asks a // question that has an answer. let pair = adjacent_pair(&docs); let words = [term(pair.0), term(pair.1)]; let refs: Vec<&str> = words.iter().map(String::as_str).collect(); b.iter(|| index.phrase(black_box(&refs)).len()) }); c.bench_function("query/fuzzy", |b| { b.iter(|| index.query(black_box(&format!("{typo}~2"))).unwrap().len()) });
// The baseline: the same query, answered by reading every document. // Slower per query, and it never gets faster — but it has no build // cost and holds no index, which is the other half of the comparison. c.bench_function("brute/scan", |b| { b.iter(|| brute_force(black_box(&docs), black_box(labelled[0].rank)).len()) }); { let mut group = c.benchmark_group("brute/tokenise"); group .sample_size(10) .measurement_time(Duration::from_secs(3)) .bench_function("2000", |b| { b.iter(|| brute_force_text(black_box(&docs), black_box(labelled[0].rank)).len()) }); }
println!("\nthree corpus sizes, this machine:"); println!("the build column is the median of three builds; the query columns average the {QUERIES} labelled queries, five rounds for the index and the pre-tokenised scan, three for the tokenising scan"); println!( " {:>7} {:>10} {:>12} {:>12} {:>12} {:>8} {:>8}", "corpus", "build", "query avg", "scan avg", "scan+text avg", "vs scan", "vs scan+text" ); for &size in &[200u64, 2_000, 20_000] { let mut rng = Rng::new(SEED); let docs = generate_documents(&mut rng, size, &table); let mut builds = Vec::new(); for _ in 0..3 { let start = Instant::now(); let mut index = Index::new(); for doc in &docs { index.add_document(&doc.path, &doc.text); } builds.push(start.elapsed()); } // The same index for both query columns: the average of the // labelled queries is a workload, not a microbenchmark. let mut index = Index::new(); for doc in &docs { index.add_document(&doc.path, &doc.text); } let mut query_times = Vec::new(); let mut brute_times = Vec::new(); for _ in 0..5 { let start = Instant::now(); for query in &labelled { black_box(index.query(&term(query.rank)).unwrap().len()); } query_times.push(start.elapsed() / QUERIES as u32); let start = Instant::now(); for query in &labelled { black_box(brute_force(&docs, query.rank).len()); } brute_times.push(start.elapsed() / QUERIES as u32); } let mut text_times = Vec::new(); for _ in 0..3 { let start = Instant::now(); for query in &labelled { black_box(brute_force_text(&docs, query.rank).len()); } text_times.push(start.elapsed() / QUERIES as u32); } let query = median(query_times); let brute = median(brute_times); let text = median(text_times); let build = median(builds); println!( " {:>7} {:>10} {:>12} {:>12} {:>12} {:>7.0}x {:>7.0}x", size, format_duration(build), format_duration(query), format_duration(brute), format_duration(text), brute.as_secs_f64() / query.as_secs_f64(), text.as_secs_f64() / query.as_secs_f64() ); // The other half of the comparison: the build is paid once, the // per-query saving is paid back on every query. println!( " break-even against the tokenising scan: {:.0} queries", build.as_secs_f64() / (text.as_secs_f64() - query.as_secs_f64()) ); }
println!("\nrecall against the labelled answers:"); // Exactness first: the index and the brute-force scan must rank the // same documents in the same order, to the last bit of the score. let mut identical = 0; for query in &labelled { let ranked = index.rank(&term(query.rank)); let scanned = brute_force(&docs, query.rank); let same = ranked.len() == scanned.len() && ranked .iter() .zip(&scanned) .all(|((doc, _, score), (other, other_score))| { *doc as u64 == *other && score == other_score }); if same { identical += 1; } } println!( " ranked lists identical to the brute-force scan: {identical}/{QUERIES} queries" );
let exact_recall = recall_at(&index, &labelled, 0); let typo_one = recall_at(&index, &labelled, 1); let (typo_two_recall, typo_two_precision) = recall_at_typo(&index, &labelled, 2); let variants = index.fuzzy(&labelled[0].typo, 2).len(); println!( " the radius-2 typo matches {variants} dictionary terms ({} documents in the union)", index.query(&format!("{}~2", labelled[0].typo)).unwrap().len() ); println!( " recall@10, exact term: {:.2} ({} of {} relevant documents in the top ten)", exact_recall.0, exact_recall.1, QUERIES * RELEVANT ); println!( " recall@10, typo at radius 1: {:.2} ({} of {} relevant documents in the top ten)", typo_one.0, typo_one.1, QUERIES * RELEVANT ); println!( " recall@10, typo at radius 2: {:.2} ({} of {} relevant documents in the top ten)", typo_two_recall.0, typo_two_recall.1, QUERIES * RELEVANT ); println!( " precision@10, typo at radius 2: {:.2}", typo_two_precision );
let index_bytes = index.save_bytes().len(); println!("\nmemory: {text_bytes} bytes of text, {index_bytes} bytes of index ({:.1}x)", index_bytes as f64 / text_bytes as f64);
c.final_summary();}
/// The first pair of distinct terms that sit next to each other somewhere/// in the corpus.fn adjacent_pair(docs: &[Doc]) -> (u64, u64) { for doc in docs { for window in doc.terms.windows(2) { if window[0] != window[1] { return (window[0], window[1]); } } } (docs[0].terms[0], docs[0].terms[0])}
/// Recall at ten for the exact term of every labelled query: the share of/// the known relevant documents that land in the top ten results.fn recall_at(index: &Index, labelled: &[Labelled], radius: usize) -> (f64, u64) { let mut found = 0; let mut total = 0; for query in labelled { let asked = match radius { 0 => term(query.rank), _ => format!("{}~{}", query.typo, radius), }; let ranked = index.query(&asked).unwrap(); let top: Vec<u64> = ranked.iter().take(10).map(|(doc, _)| *doc as u64).collect(); found += query .relevant .iter() .filter(|doc| top.contains(doc)) .count() as u64; total += query.relevant.len() as u64; } (found as f64 / total as f64, found)}
/// Recall and precision at ten for the typo'd queries at a radius. The/// typo matches more than the intended term, so the extra documents are/// counted as false positives.fn recall_at_typo(index: &Index, labelled: &[Labelled], radius: usize) -> ((f64, u64), f64) { let mut found = 0; let mut total = 0; let mut hits = 0; for query in labelled { let asked = format!("{}~{}", query.typo, radius); let ranked = index.query(&asked).unwrap(); let top: Vec<u64> = ranked.iter().take(10).map(|(doc, _)| *doc as u64).collect(); found += query .relevant .iter() .filter(|doc| top.contains(doc)) .count() as u64; total += query.relevant.len() as u64; hits += top .iter() .filter(|doc| query.relevant.contains(doc)) .count() as u64; } ((found as f64 / total as f64, found), hits as f64 / (labelled.len() * 10) as f64)}
/// A duration in the unit that reads best: microseconds below a/// millisecond, milliseconds below a second, seconds above.fn format_duration(d: Duration) -> String { let micros = d.as_secs_f64() * 1_000_000.0; if micros < 1_000.0 { format!("{micros:.1} µs") } else if micros < 1_000_000.0 { format!("{:.2} ms", micros / 1_000.0) } else { format!("{:.2} s", micros / 1_000_000.0) }}The seven benches split into three groups. index/build/2000 is the one-time cost of building the index — measured by rebuilding it inside the loop, which is the only honest way to time a build. query/exact, query/common, query/boolean, query/phrase and query/fuzzy are per-query costs against an index built once, outside the closure: a benchmark that rebuilt the index per iteration would be measuring the build. The phrase benchmark asks about a pair of terms found by scanning the corpus for two different labels next to each other, so the question has an answer. brute/scan and brute/tokenise/2000 are the baselines: the same query answered by reading every document, once with the terms handed over pre-tokenised and once paying the tokeniser on every query.
The two baselines bracket the comparison honestly. The pre-tokenised one flatters the baseline — a real scan would tokenise too — so the gap it reports is a lower bound on the index’s advantage. Neither baseline reads from disk; a scan that opened each file per query would pay the I/O on top.
What the run printed
Section titled “What the run printed”cargo benchcorpus: 2000 documents, 512 distinct terms, 199797 term slots, 1796173 bytes of textqueries: 24 labelled, 5 relevant documents each, planted 8 timeschecked: the tokeniser is the identity on the first 50 documentsindex: 2000 documents, 512 terms, average length 99.9the phrase benchmark asks about "term0126 term0004": 6 documentsGnuplot not found, using plotters backendBenchmarking index/build/2000Benchmarking index/build/2000: Warming up for 500.00 msBenchmarking index/build/2000: Collecting 10 samples in estimated 4.1546 s (110 iterations)Benchmarking index/build/2000: Analyzingindex/build/2000 time: [37.163 ms 37.417 ms 37.751 ms]Found 1 outliers among 10 measurements (10.00%) 1 (10.00%) high severe
Benchmarking query/exactBenchmarking query/exact: Warming up for 500.00 msBenchmarking query/exact: Collecting 50 samples in estimated 1.0227 s (57k iterations)Benchmarking query/exact: Analyzingquery/exact time: [17.740 µs 17.796 µs 17.850 µs]Found 2 outliers among 50 measurements (4.00%) 2 (4.00%) low mild
Benchmarking query/commonBenchmarking query/common: Warming up for 500.00 msBenchmarking query/common: Collecting 50 samples in estimated 1.0572 s (17k iterations)Benchmarking query/common: Analyzingquery/common time: [63.293 µs 63.536 µs 63.779 µs]Found 2 outliers among 50 measurements (4.00%) 2 (4.00%) high mild
Benchmarking query/booleanBenchmarking query/boolean: Warming up for 500.00 msBenchmarking query/boolean: Collecting 50 samples in estimated 1.0053 s (110k iterations)Benchmarking query/boolean: Analyzingquery/boolean time: [8.8532 µs 8.9012 µs 8.9717 µs]Found 5 outliers among 50 measurements (10.00%) 1 (2.00%) high mild 4 (8.00%) high severe
Benchmarking query/phraseBenchmarking query/phrase: Warming up for 500.00 msBenchmarking query/phrase: Collecting 50 samples in estimated 1.0024 s (110k iterations)Benchmarking query/phrase: Analyzingquery/phrase time: [9.0706 µs 9.1805 µs 9.3401 µs]Found 2 outliers among 50 measurements (4.00%) 1 (2.00%) high mild 1 (2.00%) high severe
Benchmarking query/fuzzyBenchmarking query/fuzzy: Warming up for 500.00 msBenchmarking query/fuzzy: Collecting 50 samples in estimated 1.0867 s (550 iterations)Benchmarking query/fuzzy: Analyzingquery/fuzzy time: [1.9009 ms 1.9114 ms 1.9223 ms]
Benchmarking brute/scanBenchmarking brute/scan: Warming up for 500.00 msBenchmarking brute/scan: Collecting 50 samples in estimated 1.0398 s (15k iterations)Benchmarking brute/scan: Analyzingbrute/scan time: [67.493 µs 68.453 µs 69.649 µs]
Benchmarking brute/tokenise/2000Benchmarking brute/tokenise/2000: Warming up for 500.00 msBenchmarking brute/tokenise/2000: Collecting 10 samples in estimated 3.9754 s (220 iterations)Benchmarking brute/tokenise/2000: Analyzingbrute/tokenise/2000 time: [17.668 ms 17.883 ms 18.216 ms]Found 2 outliers among 10 measurements (20.00%) 1 (10.00%) high mild 1 (10.00%) high severe
three corpus sizes, this machine:the build column is the median of three builds; the query columns average the 24 labelled queries, five rounds for the index and the pre-tokenised scan, three for the tokenising scan corpus build query avg scan avg scan+text avg vs scan vs scan+text 200 3.43 ms 1.9 µs 7.1 µs 1.76 ms 4x 950x break-even against the tokenising scan: 2 queries 2000 35.86 ms 12.4 µs 73.2 µs 17.73 ms 6x 1433x break-even against the tokenising scan: 2 queries 20000 452.67 ms 119.4 µs 1.05 ms 176.80 ms 9x 1480x break-even against the tokenising scan: 3 queries
recall against the labelled answers: ranked lists identical to the brute-force scan: 24/24 queries the radius-2 typo matches 23 dictionary terms (1996 documents in the union) recall@10, exact term: 1.00 (120 of 120 relevant documents in the top ten) recall@10, typo at radius 1: 1.00 (120 of 120 relevant documents in the top ten) recall@10, typo at radius 2: 0.03 (4 of 120 relevant documents in the top ten) precision@10, typo at radius 2: 0.02
memory: 1796173 bytes of text, 1764944 bytes of index (1.0x)Read the per-query numbers first. An exact term costs about 18 µs; the same query for the most common term in the dictionary, which sits in all 2,000 documents, costs about 64 µs; a boolean query over two mid-frequency terms costs about 9 µs. The cost follows the postings list, not the syntax — the boolean query is cheaper than the single common term because it matches fewer documents. The fuzzy query costs about 1.9 ms, a hundred times an exact lookup, because it scans the dictionary by edit distance instead of looking a term up: typo tolerance is a dictionary scan, and its cost grows with the dictionary, not the corpus.
The baselines bracket that: 68 µs for the pre-tokenised scan, 17.9 ms for the one that tokenises. Against the scan that already holds its terms, the index is four times faster on this corpus; against the scan a program without an index actually runs, it is a thousand times faster.
Recall against known answers
Section titled “Recall against known answers”Latency is the easy half. The recall report answers the other question, and its first line is the one that matters most:
ranked lists identical to the brute-force scan: 24/24 queriesFor every labelled query, the index’s ranked list — document order and scores, to the last bit of the floating point — is identical to what reading every document produces. The index does not approximate; at two thousand documents it is exactly the brute-force answer, faster. That is the property an inverted index is supposed to have, and it is checkable rather than assumed.
Then the ranking question, measured against the planted documents:
recall@10, exact term: 1.00 (120 of 120 relevant documents in the top ten) recall@10, typo at radius 1: 1.00 (120 of 120 relevant documents in the top ten) recall@10, typo at radius 2: 0.03 (4 of 120 relevant documents in the top ten) precision@10, typo at radius 2: 0.02All 120 relevant documents make the top ten for the exact query, and for the typo’d query at radius one — one edit is precise here. Radius two collapses, and the report says why: the typo matches 23 dictionary terms, because the labels share their first four characters and differ in one digit each, and those 23 terms hold 1,996 of the 2,000 documents between them. The top ten is then mostly noise, and four relevant documents survive by luck.
That is a property of this dictionary, not of the radius rule. Whether a radius is wide or narrow depends on how close the dictionary’s terms sit to each other, and 512 labels that differ in one or two positions by construction is the adversarial case — the same dial on the demo corpus’s 84 terms, where step 8 measured valu~2 reaching three terms, gives a very different answer. What the measurement shows is that the radius is a precision dial, and what one notch of it costs on a dense dictionary: recall and precision both fall to noise.
The honest comparison
Section titled “The honest comparison”The scaling table puts the three costs side by side at three corpus sizes:
corpus build query avg scan avg scan+text avg vs scan vs scan+text 200 3.43 ms 1.9 µs 7.1 µs 1.76 ms 4x 950x 2000 35.86 ms 12.4 µs 73.2 µs 17.73 ms 6x 1433x 20000 452.67 ms 119.4 µs 1.05 ms 176.80 ms 9x 1480xThree things stand out. The build is the only cost that grows without being asked — 3 ms, 36 ms, 453 ms — and it is paid once, which is why the break-even line under each row reads two or three queries: against the tokenising scan, the index repays its build almost immediately. The per-query advantage over the pre-tokenised scan grows with the corpus but modestly, 4x to 9x, because that baseline is unusually fast: integer comparisons over terms already in memory. And the query average grows with the corpus too, because these query terms sit in more documents as the collection grows — the index’s query cost follows the postings list, and a term in a third of the collection has a third of the collection to rank.
The last line of the report is the storage cost:
memory: 1796173 bytes of text, 1764944 bytes of index (1.0x)The index file comes out slightly smaller than the text, which is a property of this corpus rather than of the format: the labels are eight characters long, which is generous for a word, and the index spends four bytes per occurrence where the text spends nine per slot. What the number does say is that this index is not a compression scheme. It stores every occurrence position explicitly, and on this corpus that comes out even.
What this step does not do
Section titled “What this step does not do”The corpus is generated, not gathered, and the article says so wherever the numbers appear. The latencies are one machine, one run, in the optimised bench profile; they will differ on yours, and the recall numbers will not. Nothing here measures a cold cache, concurrent queries, the cost of loading the index from disk, or the HTTP layer from step 9 — all real costs, none of them this step’s. Criterion stays a dev-dependency, so the shipped binary carries no benchmark code. And recall is measured at ten; what happens at rank fifty is a different question.
Step 12 closes the track: what Lucene does that this engine doesn’t — segments, compression, and the ranking models — with the measurements from this step as the baseline for the comparison. The track overview keeps the full list current as articles land.