Issue #664: 1BRC to the limit: no whole-file UTF-8 check, text checked only where it is new (measure first, incl. a type for unchecked text)

libraries, compiler, performance, decision · opened 2026-10-18 · updated 2026-10-18 · 1 comment

Split from #422 (owner, 2026-10-18). #422 now only lets a grammar read Bytes (ADR-366); everything about speed is here, and is to be pushed as far as it goes.

From zero

let data = fs::map(path, fs::Root::Anywhere)   // maps the file and checks all of it as UTF-8
let totals = Measurements::file(data)          // the grammar sees text

fs::map checks the whole mapping in one SIMD pass (checked_text, ADR-016 D1, D4), before the parse, so every ref String a grammar cuts from it is a view of the pages. A bad byte is IoError::NotText("… (at byte N)") before the first rule runs. tuned (Rust) checks nothing and turns only the 413 distinct names into text at the end - and reads a stray byte in a temperature as a wrong number.

ADR-016 §4 deferred “fuse the check into the piece”. ADR-366 now gives a grammar Bytes input with a check where text is made, so the shapes below can be built and measured.

What is known

Today (Nikaia 0.0.970, benches/brc/README.md, 1 M rows): 300.2 instructions a row; callgrind attributes 2.4 directly to simdutf8, plus an unsplit part of the 43.3 in “the rest, SIMD intrinsics”. #422’s “about 10” is from 0.0.424 and stale.
Not known, and it decides everything: whether checking each name separately (9-16 bytes a row, std’s short-input from_utf8) is cheaper than the whole-file SIMD pass. It may well be dearer. The only shape sure to be cheaper checks a name only when it is new: 413 checks instead of a billion. winnow-grammar does that for intern (its ADR 25 D4); Nikaia’s 1BRC does not intern, the name goes as ref String into a HashMap’s entry.

Shapes to measure

Each against today, same output byte for byte first, callgrind --branch-sim=yes, release, counts only (CLAUDE.md). Prototypes may be hand-edited generated Rust where the compiler cannot write them yet.

Per-name check. The grammar over the mapping’s bytes (ADR-366), NAME’s until checked per row, no whole-file pass.
Check on a miss, through the map. The name stays bytes until the map lookup; a hit compares bytes against a key that is already text, so it needs no check; only a miss checks before inserting. Prototype in Rust: HashMap<&str, Stats> looked up by &[u8] (hashbrown raw_entry/Equivalent, or a Borrow<[u8]> key wrapper).
Interning in the grammar. NAME as intern(until(…)) (winnow ADR 25 D4): the check on a miss inside the interner, the accumulator a Vec by Symbol::index(), the map gone. Measures what the slot table also saves against the hash map (#420’s chain).
The whole-file check, fused into the pieces (ADR-016 §4’s original idea): each par_fold piece checks its own range on the thread that parses it, cache-hot. Counts the same instructions as today; its point is the clock and the memory traffic, so this one is the exception where a timed run is reported beside the counts and explicitly marked as such, or it is dropped.
Upper bound: no check at all (unsound, measuring only), to say what any shape can at most win.

What a decision would need

A type for text not yet checked, if shape 2 wins. Something like a view that is bytes until a map lookup or an explicit .text() checks it. This is a language question (Part I 2.6): what it is called, what it can do without being checked (compare, hash, be a map key), and where the check happens. Prepare options with how others do it (Rust &[u8] + from_utf8, Go []byte vs string, Python bytes/str, Swift String.UTF8View), and the cost to programs that never need it.
fs::map as Bytes (a mapping without the check), needed by 1-3: a new function, or fs::map handing back something both a grammar and text use can take, with the check deferred to text use. Today’s Mapped derefs to str, so a lazy check could not report an error there.
The error a program sees for a bad byte moves from IoError::NotText at fs::map to ParseError at its offset (ADR-366 D3). A program that handles NotText would change; check examples/ and the tests.

To do

Measure 5 and 1, then 2, 3, 4. Results as one table in this issue.
If nothing beats today by a clear margin: close with the table, ADR-016 §4 records measured, not worth it.
Otherwise a decision basis for the owner (CLAUDE.md, Decision rounds): the winning shape, the type question if it needs one, fs::map’s form, the error change; then ADR, specification and a To build list here.

Depends on: winnow-grammar#24 (byte input in the backend) for 1-3 through the compiler; hand-written Rust prototypes do not need to wait. Related: #422, #420, #434, winnow-grammar#25.

Comments

keywan-ghadami, 2026-10-18

Measured (2026-10-18): 1BRC as a byte grammar costs more than as text today.

examples/1brc.nika was changed from fs::map to fs::read, so the grammar runs as MeasurementsOverBytes / parse_bytes_pieces (ADR-366). Same output. Counted with callgrind --branch-sim=yes over 1 M rows, after the hashbrown switch:

	instructions a row	mispredictions a row
as text over `fs::map`	273.4	1.58
as bytes over `fs::read`	456.6	4.68

Where the bytes version pays:

The UTF-8 check per name, 115.6 a row and 2.67 mispredictions. It replaces a whole-file check that cost 10.3. The ADR-366 D2 check calls is_ascii, and when a name is not ASCII, as many station names are, it falls to core::str::from_utf8 instead of simdutf8.
The digits, 42.5 a row, through ascii_run and str::parse.
The grammar runtime, 99.3 a row.

So the bytes path pays only once what ADR-366 §4 defers is built: a mapping as Bytes, and text not yet checked that a map lookup checks only on a miss. The check per name should at least go through simdutf8. This issue keeps that work.

Separately, the text path is being sped up in winnow-grammar. Hand variants of three changes counted 273.4 → 232.2 a row, with mispredictions 1.58 → 1.09:

cuts without boundary checks at positions next to an ASCII byte;
one static searcher per scan site;
fused runs of fixed-shape elements.

Generated by Claude Code

Back to Open Issues