Nikaia
Menu
v0.0.1343pre-alpha GitHub

ADR-375: A Bytes Searches for a Set of Bytes by What the Program Wants, Not by How Wide It Looks

Status: Accepted; D5 (a search’s positions are facts) added October 20, 2026; D6 (how find_all goes from one hit to the next) added October 21, 2026 (the first part of the API record ADR-371 D4 asks for: searching whole buffers; vectors a program holds are decided after it) Date: October 20, 2026 Answers: how a program finds the bytes of a small set in a buffer as fast as the machine it is built for allows, without naming a vector width Related: ADR-371 (vector lanes are std’s), ADR-002 D6 (the CPU level is the build command’s), ADR-320 D6 (find from a position), D7 (a Bytes is read as a run of bytes), D13 (no read past the end), ADR-374 (a position in text), Part III’s Seq

1. Question

let seps = bytes::ByteSet([';', '\n'])
for p in data.find_all(seps) { … }

The fastest programs over a large input compare 16 to 64 bytes in one instruction. A width written in the source is wrong on every machine whose registers are of another width, and most of what such programs do - find the bytes of a set, count them, cut at them - gives the same answer at any width. The width belongs to the build (ADR-002 D6); the program says what it is looking for.

2. Decisions

D1 — A search over a whole buffer is the first level; the width is never in it.

std searches a buffer for the bytes of a set at the width the build’s CPU level makes best, handles the end of the buffer itself, and gives the same result at every width. No name says SIMD or parallel: how the search runs is the build’s, and parallel is the word for threads (par_fold, par_iter).

Why. On 1BRC the step that mattered was not the width: replacing a call per row with a scan over many rows moved a hand-written Rust program by 64 to 85 instructions a row, and 32 lanes against 16 by about 8. A search over the whole buffer takes that gain without a vector in the program, and is right on a machine of any width, SVE’s and RISC-V V’s included, whose width is known only on the machine.

D2 — The set is a type, bytes::ByteSet, built once, of any bytes.

bytes::ByteSet([';', '\n']) is a set of bytes, 0x00 to 0xFF, prepared once for the search it will serve. It may hold any number of bytes. A set the build proves empty (ByteSet([])) is refused (NK1287); one that is empty at run time is a set like any other, in which nothing is found: find is null, find_all yields nothing, split yields the whole buffer as its one piece.

Why. The preparation - a few comparisons, or two lookup tables over the low and the high four bits for a large set - is done once instead of at every call in a loop, as .NET’s SearchValues and Rust’s memchr::memmem::Finder are. A Bytes holds no scalars, and the formats it is read for search for bytes above 0x7F (0xFF markers, length and type bytes), which the same comparisons find at no other cost. A set written empty is a mistake the build can show; one that a program computes may be empty for good reasons, and “found nothing” is already what each search says. Rejected: ASCII only, which matters for text, where a byte at 0x80 or above may lie inside a scalar, and is decided with text’s search; a set that is null where it is empty, which asks for a ?? even after a set of literals; a set rebuilt from a list at every call.

D3 — find gives the first, find_all every one, and split the pieces between.

data.find(seps; from: i)          // i64?                   the first at or after i
data.find_all(seps; from: i)      // Seq[i64]               every one, in order
data.split(seps)                  // Seq[ref(data) Bytes]   the pieces between

find takes a u8, as it does today, or a ByteSet. find_all yields the positions of every byte of the set at or after from, rising. split yields the pieces between them, each a view of data, by text’s split rules: two neighbouring bytes of the set give an empty piece between them, one at the end an empty last piece, and an empty data one empty piece. Which byte a position holds is data[p].

Why. One name per thing a search is for, each with costs of its own: the first stops at it, all of them walks the buffer, and the pieces are what a reader of fields wants without keeping a start by hand. split is the one text already has; a Bytes reads as text does where it can (ADR-320 D7). Rejected: a list (Vec[i64]), which costs eight bytes a hit where most programs read each once - collect makes one; an Array whose length follows the block or is fixed by the call, which puts a width back into the program; pairs of position and byte, which every consumer takes apart; pieces that carry the byte they ended at; a name for each count of results (find_first_of, count_of, contains_any). Counting is find_all(seps).count() (D4); whether it gets a name of its own, and whether rfind takes a set, is not decided here.

D4 — A sequence never loses where it came from; a consumer right after a std producer is the one the ledger names.

A Seq is not in a program’s type grammar, so at every consumer the producer is known. Where the ledger gives a producer a consumer of its own, a consumer written right after it is that one, never the general walk: data.find_all(seps).count() counts per block and makes no position, first, nth and last skip whole blocks. A step between them (filter, map, take) makes another producer, and the general walk then applies.

Why. The program writes what it wants and the language promises the way std takes, which is what makes the first level worth having: a count written as a walk is not a walk. A promise held only by an optimiser is one a reader cannot rely on; one held by the type is kept at every call. Rust keeps the same kind of promise for str::Chars::count.

D5 — A position a search hands back lies in the buffer, and a proof may use it.

for s in b.find_all(seps; from: f) {
    n += b[s]            // f <= s < b.len(): no check
}

Each position find_all(set; from: f) yields is a fact for the walk: f <= s and s < b.len(), where b is the buffer it was called on and no write to b stands between. std’s ledger states it on the sequence’s elements, as ensures states it on a result (ADR-314), and the walk reads it on the name a for binds.

Why. The bound is what the search means; making a program restate it as an assert only adds a check where none is needed, and an assert that only the search could prove is checked at every turn. Rust leaves the same index checked unless LLVM sees the search’s body. Rejected: an assert in the program; a type of positions that carries its buffer, which is more than one loop needs. Other searches - find over a set, split’s pieces, text’s search - take the same entry when a program needs it and an assert cannot give it; until then they give none.

D6 — How find_all goes from one hit to the next is the program’s to say.

for sep in buf.find_all(bytes::ByteSet([';']); scan: bytes::Scan::AfterHit) { … }

find_all takes scan: bytes::Scan. Scan::ByBlock, the default, keeps the mask of a block and reads the next block when its hits are spent. Scan::AfterHit compares the half block that starts right after each hit and takes its first, and reads whole blocks only where that half holds none. Both yield the same positions, and D4’s consumers count, skip and find the last by whole blocks under either.

Why. The two cost differently, and which costs less depends on how far apart the hits lie, which only the program knows. By block a hit costs a lowest bit and a cleared one, but the test whether the mask is spent goes one way a varying number of times and then the other, and is mispredicted about once a block. After a hit every hit costs a compare, but where the next hit is mostly within half a block the test goes the same way almost every time and is predicted. Counted over 1BRC’s rows (one ; in about 14 bytes) after a hit saves about 0.25 mispredicted branches a row at 2 to 8 instructions more; over separators every 7 bytes it costs 12 to 42 instructions a row more for the same saving, so that it loses at the baseline level. Rejected: after a hit for every search (it makes a dense search up to twice as costly); std switching between them by the hits it has seen (a threshold fitted to the programs measured, and a branch on it); a search from a position with find in the program’s loop (it gives up D5’s facts, which find does not have, and D4’s consumers).

3. Consequences

4. What this does not decide

This site is open source. Improve this page.