Architecture

This document describes how Fastmash is built: what each part does, how a command flows through it, and the principles behind the main design choices. It is written for contributors and for anyone evaluating the project. The glossary defines the terms used here.

At a glance

Design principles

The published 0.1.0 artifacts remain Linux-only. Native macOS development uses the built-in Sort route and private unlinked Spill storage, without a Sort supervisor. ADR 0010: Native Apple Silicon macOS sets its platform scope and the native artifact acceptance boundary.

These choices shape the whole codebase. Each is recorded as a decision in decision records.

1. Speed is the reason to switch. Fastmash exists because people run datamash in pipelines over large files. Performance work is measured on representative jobs against GNU datamash and against the previous Fastmash build. A change that makes an existing job materially slower needs an explicit, recorded justification.
2. The datamash command language is the interface. Existing commands, options and field selectors work unchanged. Fastmash reimplements the behavior; it contains no GNU code.
3. Portable results. One Fastmash version gives identical results on every supported machine for the same input and explicit settings. Arithmetic does not depend on the CPU’s floating-point unit or on the C math library, so a result computed on a laptop matches the one computed in CI.
4. Refuse rather than guess. If Fastmash cannot produce a result it can stand behind (an unsupported feature or locale, a checked resource limit, or a numerical result it cannot produce within its fixed rules), it stops with a clear message and exit status 77 instead of printing something plausible.
5. Grow as needed, and check. There are no fixed caps on record length, operation count or sample count. Storage grows with the job, every allocation is checked, and sorting spills to disk. The few remaining fixed limits (such as the 99-byte --format string) are documented.

Crates

How a command runs

Some points worth knowing when reading the code:

• Planning happens before input is read. The whole command is parsed and validated first, so most usage errors appear before any output. The preparation module (preparation.rs) checks control conflicts, selectors, result names and sorting eligibility in their required order, then returns one prepared request for the selected mode. Private payloads keep runners from receiving an unprepared request. Input headers, numerical admission and resource checks still happen at their existing execution points; preparation does not open inputs.
• Operations share work. When several operations read the same field, the conversion, running sums and retained samples are shared. median, q1 and q3 on one field sort one sample set, and the moment statistics share one pass over their inputs. The operation set (operation_set.rs) plans this sharing once the fields are known, reports what the command needs before input is read, and collects records, resets between groups and writes results.
• Groups are adjacent records. Without -s, a group ends when its key changes, and state for the next group starts fresh. That is what makes unsorted grouping a single streaming pass.
• Ordinary results are written progressively. Completed groups go to a small output buffer that is flushed as it fills (line by line on a terminal). A failure part-way through can leave earlier rows written, which is why the exit status must always be checked.
• Formats keep field boundaries. Ordinary text uses its separator rules. Explicit CSV decodes logical records and retains complete fields and original logical-record/physical-line locations; output encodes each field separately. Record views let calculations borrow shared storage, while retained full rows and admitted selection candidates own what must outlive that view.
• Comparison and health finish before reporting. Dataset comparison keeps complete keys, per-key operation state and required samples, preserving each key’s contribution order across each source. It finishes both scans and all changes before writing. Health collects field and width counters and bounded examples before emitting a readable or versioned TSV report. Neither adds spill for retained samples or a total-memory guarantee.

Sorting

-s sorts records by their grouping keys before grouping. Fastmash chooses a sort route for each command before it reads input (sort_route.rs: plan, then run): whether hash grouping comes first, and which sort follows it. The external route’s startup checks run then, with the others, so the sort after hash grouping is known before hash grouping starts:

• Hash grouping comes first, before the choice between the native and the external route, when standard input is a regular file (projected_hash.rs). GNU datamash sorts with a stable sort -s, so each of its groups is exactly the records with one key tuple, in input order. Hash grouping collects each tuple’s records into that group’s own operation state as they arrive, keeping every group’s state in one flat array (the operation set’s plans are shared; each group has only its running values, plus a separate store for operations that keep values), then sorts only the tuples, in the sort’s order, and writes the groups through the same writer. It gives up before writing anything when the result might differ from the sort’s (a missing or NUL key, a key the collation refuses, any operation error), when the groups are estimated to hold fewer than eight records each or, while records of a group rarely come together, to hold more state than the processor’s caches (16 MiB), or when they outgrow the sort’s memory target. The estimate is judged after 8,192 records and at each doubling: the file’s records from its length, and its groups from those seen once and twice (the Chao1 estimate of the groups not yet seen, of which the rest of the file is expected to show a share). When it gives up, the input is read again from its start, header included, through the route the job would otherwise take. Piped input can be read again only if it was kept: in a language locale, whose sort holds whole records anyway, a replay reader holds what hash grouping reads in 1 MiB blocks charged to the same memory budget, and the native sort reads them back, releasing each, and then the rest of the pipe; its chunk leaves room for what is still held. A pipe has no length, so the rest of it is taken to be as long as what was read. In the C locales piped input sorts, because the held input would take several times the memory of a sort that keeps only the selected fields (FASTMASH_PIPE_GROUPING changes either). With -W, whose sort keys keep the blanks before each field that groups ignore, a group is keyed by its fields with those blanks, as the sort compares them, and hash grouping gives up where two keys differ only in the blanks, or where a -z record holds a newline. --vnlog and rand (one generator across all groups) always sort.
• The native route sorts in process. It covers counting and text operations, basic statistics, quantiles, modes, MAD and variance, and every operation in the language locales, whose text ordering comes from pinned Unicode ICU data built into the program rather than the host’s locale files. A language sort key (locale.rs) is the ICU collation key, at three levels, of the text with the characters glibc ignores (punctuation, most symbols and spaces, from glibc’s iso14651_t1_common in collation_glibc.rs) left out and those some locales weigh first replaced by the lowest weight, followed by glibc’s fourth level, written so that its bytes compare as glibc compares it item by item: the ranks of the ignored characters and the weighted characters between them, each after the count of letters without a fourth-level weight (Han, letters a locale adds) skipped before it, with runs of weighted characters written as counts.
• A chunk holds the records being sorted in one arena (each record’s grouping keys, then the fields its operations use, or the whole record with --full, in the language locales, or for numbers when the field separator could continue one, since a number is read on from its field’s start into the rest of the record as GNU datamash reads it) and a 16-byte entry per record: the first key’s eight-byte prefix, the key length and the arena offset. A stable radix sort orders the entries by prefix. Records whose prefixes tie on longer keys are sorted the same way by their next eight key bytes, round by round; complete keys are compared only in small groups and after 64 bytes of a key. Ties keep input order. In the language locales, collation keys are computed in batches on several threads. The chunk, with the batches’ share, stays within its memory target: 64 MiB at first. When a chunk fills, it may grow instead of spilling: to hold the whole input of a regular file (an estimate from the bytes read so far, at most the buffer GNU sort would use for the file), or to twice its size for piped input, when the memory read at that moment allows it. The chunk may take at most a quarter of the available memory, a share per processor of what is free under each cgroup memory limit (so that as many jobs as processors fit together), a share per running Fastmash of the host’s available memory, and half of any address-space limit, and only while less than half the swap is in use. A fact that cannot be read keeps the chunk as it is. FASTMASH_SORT_MEMORY_BYTES fixes the target instead. The last chunk is read in place, without copying records; earlier chunks are spilled and merged with it.
• Spill writes sorted runs to anonymous temporary files (O_TMPFILE, or where the filesystem lacks it a private file unlinked as soon as it is open), which the kernel removes automatically when Fastmash exits, however it exits.
• Quoted CSV sorting uses its own complete decoded-record route, without hash replay or a text-format fallback. Record bytes, field ends, original locations and required language comparison segments are packed into shared chunks. Calculations borrow each chunk through group completion, and selection owns records only when they enter its candidates. Actual capacities and reusable decoder/key scratch count against the ordinary sort-memory policy. Checked private spill framing preserves complete ragged fields and locations; bounded merge heads remain owned. An oversized record and merge heads can exceed the chunk target, and statistical samples retain their separate in-memory policy.
• The external route remains, in the C locales, for rand, the other means (geomean, harmmean, ms, rms), skewness, kurtosis, normality tests, paired statistics and sorted rmdup. Its temporary files go in a private directory in TMPDIR, which the supervisor creates and removes. Where it cannot run or work (the conditions are in sort_route::sort, sorted_input::available and fastmash_sort_process::available), these jobs take the native route.

The sort supervisor

When the external route is used, Fastmash does not run sort directly. It starts fastmash-sort-supervisor, which runs sort with a fixed argument list in a private temporary directory and guarantees clean-up even if the main program is killed.

The control channel is a small fixed-format message protocol defined in crates/sort-process/src/lib.rs. The supervisor uses Linux pidfds and close_range, so this route needs Linux 5.11 or later.

Numbers

Numerical behavior is where Fastmash differs most from a straightforward port.

• Representation. Values are 80-bit extended precision (64-bit significand), the same range and precision GNU datamash uses on x86-64, so results agree closely with it.
• Software arithmetic. Instead of the x87 floating-point unit and the C math library, Fastmash implements the arithmetic itself. This is what delivers portable results: the output does not depend on the CPU model, the compiler, or the libm version.
• log and exp. The geometric mean, the normality tests and similar statistics need transcendental functions. Fastmash aims for the correctly rounded 80-bit result: fast paths prove their result with a certificate and otherwise fall back to arbitrary-precision evaluation. A few boundary cases that cannot be settled within fixed limits are refused (status 77).
• Ordered evaluation. Sums are accumulated in input order and formulas follow the same order of operations as GNU datamash, because reordering floating-point arithmetic changes results.
• Versioned numerical rules. Parsing, arithmetic, special values, formatting and refusals are specified together as a numerical profile. Any change to observable numerical output is a deliberate, versioned change listed in the changelog.
• Fast paths. Common cases, such as decimal inputs that can be summed exactly, take specialized paths that give the same result faster.

Errors and exit statuses

Diagnostics are written to standard error as fastmash: message, sometimes followed by a hint: line suggesting a fix. When one failure follows another (for example a failed write of the output after an error), the more serious status wins: 70 over 77 over 1 (failure::combine). A diagnostic that cannot be written makes the status 1. Other internal failures are reported with status 77 (for example an internal conversion failure) or, since panics abort, end the process with SIGABRT; all of them are bugs.

Safety

• unsafe code is limited to operating-system interfaces (Linux system calls for standard streams, process supervision and temporary files), one fixed-size arena allocation in the numerics crate, one x86-64 div instruction for 128-by-64-bit division in decimal parsing, guarded by an assertion of its precondition, an x86-64 cache prefetch hint when a sorted chunk is read, which never dereferences its address, a glibc mallopt call at startup that caps malloc arenas under an address-space limit, and unchecked slicing of a sort run file’s read buffer, whose bounds are kept as a documented invariant (checked slicing cost 4% on a spilling job). The conversion and numeric-contract crates forbid unsafe entirely. Every other crate denies unsafe operations inside unsafe fn without an explicit block and warns on any unsafe block without a // SAFETY: comment, which CI treats as an error.
• Overflow checks stay on in release builds, and panics abort.
• No network, no shell. Fastmash never makes network connections and never passes input to a shell. The only child processes are the sort supervisor and the system sort it starts, with a fixed argument list.
• Dependencies are few and pinned. See Cargo.toml.

Dependencies

Where to start reading

Decision records

Architecture decisions are recorded in decision records. Read them before proposing a change to one of the principles above.