Open and answer this issue on GitHub.
ready · opened 2026-10-19 · updated 2026-10-20 · 5 comments
The 1BRC comparative study (phase 3) wrote a hand-tuned fast.nika that scans bytes itself. Without a grammar, its only way onto all cores was static pieces: cut PIECES = 8 ranges at line starts, pieces.par_iter().map fn(p) { scan(b, p) }.collect(), merge the list. Measured (callgrind): one table per piece, made and cleared each time - the memset alone costs 2.6 instructions/row at 8 pieces and 19.5 at 16 pieces of 32 768 slots. The hand-tuned Rust programs instead keep one table per thread and claim 1 MiB chunks with an atomic fetch_add. Nikaia had no core count, no Par::fold, and par_fold (Part II 10.7) exists only inside a grammar and cuts one piece per core before the work starts (ADR-296 D11).
crates/nikaia-std/src/par.rs: Par has map, filter, for_each, collect, count, … but no fold.available_parallelism in std; ADR-296 D11 names a cpu::count() that was never built.src/rt.rs fold_pieces: Parallelism::Auto = available_parallelism() pieces (not the user-pool size), cut before the work, run on rayon’s global pool, merged first piece first.; are named with a value - a bare unordered is not a form the language has.ADR-372; specification Part II 10.7 and 12.6.
task::cores() -> i64: the user pool’s size (user-pool, 0 = the threads the process may run on, affinity and quota counted); 1 at user_parallelism = no.xs.par_iter().fold(init, step, merge): init a type or fn { … } called once per accumulator; nothing shared.b.par_pieces(sep): a Par[Bytes] of pieces ending just after sep.par_fold too.order: par::Order - Kept (default: contiguous runs, merged in input order; associativity only) or Any (one accumulator per worker; the program promises order does not matter).workers: (default task::cores()) and piece: tune, change no result; below 1 panics naming the option.user_parallelism = no each is one sequential fold.par_fold failure is reported at the smallest position under either order.task::cores() in crates/nikaia-std/src/task.rs (+ ledger entry): the user pool’s thread count at yes, 1 at no. Test: a program printing task::cores() gives 1 at user_parallelism = no and N with user-pool = N in nikaia-runtime.toml.par::Order (Kept | Any) in std::par, and Par::fold(init, step, merge; order:, workers:) in par.rs. Kept: rayon fold + ordered reduce (contiguous runs, input order). Any: one accumulator per worker thread (e.g. rayon::broadcast/per-thread slot), pieces claimed through an atomic index, merged as workers finish. Checker: init/step/merge asked as par_iter lambdas (NK2209, NK2107); init accepts a type name or fn { … }. Tests: sum over 0..1_000_000 equals the sequential sum at both orders and both user_parallelism values; a fold collecting into a list keeps input order under Kept; empty input returns init’s value; workers: 0 panics naming workers.piece: option on par_iter (rayon with_min_len/with_max_len around it). Test: piece: 1 and piece: 1_000_000 give the same result.Bytes::par_pieces(sep: u8; piece:): pieces of about piece bytes (runtime default, ~1 MiB), each extended to just after the next sep; every byte in exactly one piece, none empty. Tests: concatenation of the pieces equals b for inputs with/without a trailing sep, with no sep at all, and with piece: 1; b.par_pieces(b'\n').fold(…) counting lines equals b.count(b'\n') (+1 for an unterminated last line).par_fold claims pieces while it runs (winnow-grammar fold_pieces, Nikaia’s lowering): pieces of piece: bytes claimed dynamically with the existing seam repair; order: and workers: passed through; run on Nikaia’s user pool, sized by task::cores(), not available_parallelism(). Kept: per-run accumulators merged in input order. Any: one per worker. Tests: existing par_fold tests unchanged at both orders; error position equals the sequential parse’s when two pieces fail (D8); piece: 64 on a multi-MiB input gives the sequential result.fast.nika with b.par_pieces(b'\n').fold(Table, …, Table::merge; order: par::Order::Any); re-measure (callgrind counts plus perf task-clock at 1/16 codegen units) against the static-pieces version and record the comparison here. This is the measurement still owed for D4/D5 (Kept vs Any on a costly accumulator).Not decided here (ADR-372 §5): pieces of String at a char, NUMA/heterogeneous scheduling, the default piece size (a measurement’s). A public atomic fetch_add on SharedMut was not taken up.
Steps 1–3 are built in 137c6b0 (version 0.0.1141). task::cores(), par::Order, Par::fold(init, step, merge; order:, workers:) and par_iter(piece:) are in, with tests in crates/nikaia/tests/parallel_folds.rs.
Kept is rayon’s fold followed by an ordered reduce_with. Any keeps one accumulator per pool thread.workers: and piece: below 1 stop the program at both user_parallelism values.Par is itself a Par, so fold can follow map and filter.Still open:
step returns the accumulator. Its own example, fn(acc, r) { acc.record(r) } with Summary::merge, and the grammar’s par_fold both change the accumulator in place and return nothing. What is built follows the text, so the example does not compile. Which form is meant is put to the owner.fn(A, A) -> A) and #758 (a lambda’s result type from return).Bytes::par_pieces, par_fold claiming pieces as it runs (winnow-grammar), and 1BRC.Generated by Claude Code
Decided (0.0.1142): step and merge may each return the accumulator or change it in place; their result type says which.
How it came up: ADR-372 D2 said that step returns the accumulator, and steps 1–3 were built that way. The ADR’s own example, Part II’s par_fold, and examples/1brc.nika (fn record(ref mut self, m: Reading), fn merge(ref mut self, other: Summary)) change the accumulator in place instead. The owner chose to allow both forms.
fold/fold_mut).fold paragraph.step: fn(A, T) -> A or fn(ref mut A, T).merge: fn(A, A) -> A or fn(ref mut A, A); in the in-place form the second argument may be taken by value or as ref.step and merge choose their form independently.NK1102.Par::fold, par_fold and a grammar’s fold.To build (D9):
step and merge from their result types. A lambda whose body returns nothing makes its first parameter ref mut. Refuse any other result type with NK1102.
fn(n, x) { "a" } is refused with NK1102.std (par.rs): run an in-place step or merge as |mut a, x| { step(&mut a, x); a }. Do the same for par_fold and a grammar’s fold.
xs.par_iter().fold(Summary, fn(acc, r) { acc.record(r) }, Summary::merge) gives the same result as the returning form, under order: Kept and order: Any, and at user_parallelism = no.examples/1brc.nika still runs byte for byte as before.Then steps 4–5 as before: Bytes::par_pieces once #754 is built, then par_fold claiming pieces in winnow-grammar.
Generated by Claude Code
D9 is built (0.0.1144, commit df1a0f4). Par::fold, par_fold and a grammar’s fold now accept a step and a merge that either return the accumulator or change it in place.
How it is built:
check_core_fold_form in check_core_args.nika decides the form of each function from its result type. A lambda’s own last-expression type is now recorded (flow.lambda_tails).nikaia_std::par::in_place(&mut a, x, f).mut or ref mut self, and a merge may take its second argument as ref.Tests:
parallel_folds and fold_lambdas cover all four pairings, both as lambdas and as declared functions, under Kept and Any, at user_parallelism = no and yes.par_fold with declared in-place functions is tested.NK1102 is tested for a bad step, a bad merge, and a function that returns nothing without mut.examples/1brc.nika lowers to the same Rust as before.Still open from D9:
fn { 0 }), the accumulator’s type is unknown, so fn(n, x) { "a" } is not refused there. Refusing it needs a typed integer literal at that point.fn(n, x) { n += x });acc on to a function that takes it mut.Next: steps 4–5 (Bytes::par_pieces, then par_fold claiming pieces in winnow-grammar), after #754.
Generated by Claude Code
Steps 4 and 5 are built in part (0.0.1147: Nikaia commits 6ab6b4e and e1e5c2b, winnow-grammar commit 0fb343f).
b.par_pieces(sep; piece:).
sep and are claimed while the work runs, one rayon job each.piece: defaults to 1 MiB.no, the same pieces run in order on one thread.no and yes, under Kept and Any.par_fold(...; order:, workers:, piece:) is parsed, checked and lowered.workers threads.examples/1brc.nika gives the same output across the four combinations tested in one_brc.rt::Parallelism::Claimed { piece, order } is on branch ccr-ebde3d88-1ym9db. Pieces are claimed while the work runs, and the seam repair stays. Every piece is parsed, and the first failing piece’s error is returned.Still open:
par_fold cuts its pieces before the work starts (Pieces(workers)). Moving it to 0fb343f takes three things:
grammar.rs in_pieces, pass Parallelism::Claimed;one_brc, grammar_lowering, grammar_bytes and parallel_folds again.fast.nika with these pieces and measure it again.Found on the way: #760 (text += f"…" does not compile).
Generated by Claude Code
Step 6 is done. Nikaia now pins winnow-grammar 0fb343f (0.0.1148), so a grammar’s par_fold claims its pieces while it runs. benches/brc/fast.nika is in the repo (commit 63951bd), together with brc.sh and the README table.
Callgrind, 1M rows, instructions and mispredicts a row:
| 1 unit | 16 units | tokens | |
|---|---|---|---|
| AI variant 2 | 147.4 / 0.38 | 147.4 / 0.38 | 1775 |
fast.nika |
174.1 / 1.02 | 173.3 / 1.10 | 1288 |
fast.nika, overflow checks off |
152.8 / 0.95 | 151.0 / 0.95 | |
| AI variant 2, v3 | 132.7 / 0.27 | 132.7 / 0.27 | |
fast.nika, --cpu=x86-64-v3 |
167.8 / 1.02 | 167.1 / 1.01 |
The gap is the checks: about 6.4 overflow tests a row (22 instructions) and about 37 instructions of bounds, shift-count and conversion tests. The temperature costs 50 instructions against 26, the stats update 20 against 14, and the bounds of the long-name slice 14 a row. The parallel build gives the same output; it is not counted per row.
Defects found on the way: #762 (D9 with mut parameters), #763, #764, #765, #766. Fixed on the way: dede34d (0.0.1149).
Left on #717: open points 1 and 2 of the D9 comment, and #762. Proving away the checks is not this issue’s work; it follows separately.
Generated by Claude Code