# A CSV engine, one idea at a time
Five self-contained programs, each one idea faster than the last, from the
parser everyone writes first to a 900 MB/s typed query. Every step compiles
alone, passes the same RFC-4180 correctness gate before it may benchmark, and
prints its own numbers — the tutorial arc *is* the performance story.
Measured on an Apple M-series laptop (Apple clang 17, `-std=c++20 -O2`,
single thread), bench.csv = 1,000,000 rows / 50.1 MB, best of 3:
| step | idea added | MB/s | Mrows/s | heap allocs/pass |
|---|---|---|---|---|
| 1 `step1_naive` | getline + string copies + `stod` | 130 | 2.6 | 4,011,191 |
| 2 `step2_mmap` | mmap + one-pass RFC-4180 state machine | 544 | 10.9 | 1 |
| 3 `step3_zerocopy` | fields = `string_view` into the mapping | 1,344 | 26.8 | 1 |
| 4 `step4_swar` | 8-bytes-at-a-time SWAR scanning | 1,365 | 27.2 | 1 |
| 5 `step5_typed` | `from_chars` + open-addressing GROUP BY | 900* | 18.0 | 0 |
\* step 5 runs a real query — `SELECT category, COUNT(*), SUM(value) GROUP BY
category` — end to end: **7.0× faster than the same query on the step-1
parser**, with the sums bitwise-equal and the counts matching the data
generator's reference exactly.
## Run it
```
python3 gen_data.py # writes bench.csv (50 MB, gitignored) + edge.csv
./bench.sh # builds all five, verifies, benchmarks, prints the table
```
## What each step teaches
**Step 1 — correct first.** getline + copies. The subtlety most homemade
parsers miss: a CSV *record* is not a *line* — quoted fields may contain
newlines, so lines get re-joined while a quote is open. Slow, allocation-heavy
(4M allocations), and the baseline everything is measured against.
**Step 2 — map, don't read.** mmap gives the file as one byte range: no
`read()` copies, no istream, no line-reassembly — a four-state RFC-4180
machine walks the bytes once. 4.2×. A surprise the allocation counter caught:
heap traffic was *already* near zero here, because the reused field buffer +
small-string optimization absorb the copies. What remains is pure byte
traffic — which motivates step 3 precisely.
**Step 3 — coordinates, not copies.** Fields become `string_view`s into the
mapping: the parser's only output is pointers and lengths. Escaped quotes are
*deferred* — the view keeps raw bytes plus a `needs_unescape` flag, and only a
consumer that wants cooked text pays (~1% of fields here). Lifetime is safe by
scope: the mapping outlives every view. Proof over promise: pass 2 over the
same file performs **zero** per-row allocations. 2.5× again — 10× cumulative.
**Step 4 — measure, then decide.** The SWAR kernel (broadcast-XOR + the
zero-byte trick) scans 8 bytes per iteration and is the technique behind the
fast-parser literature. On this data it buys **5%**, not the famous 2–4× —
mean field length is 7.1 bytes, so nearly every scan hits a delimiter in the
first word and the per-field fixed costs dominate. The step stays in the
series because *both* facts matter: how the trick works, and when it doesn't.
**Step 5 — the payoff query.** Typed extraction with `std::from_chars`
straight off the views (no NUL-terminated copies, no locale), GROUP BY through
a 64-slot linear-probe table keyed by `string_view` (no `unordered_map`, no
per-node allocations). Correctness is cross-checked three ways: fast vs naive
sums bitwise-equal, group counts identical, and both match `gen_data.py`'s
printed reference.
## Scope and design notes
- RFC 4180: quoted fields with embedded commas/CRLF, doubled-quote escapes,
CRLF and LF terminators, optional trailing newline. Not handled: other
delimiters/encodings, header typing, ragged-row policy — engine, not ETL.
- The allocation counter overrides global `operator new/delete`, so hidden
copies have nowhere to hide; every step reports it.
- `std::from_chars<double>` works on Apple clang 17 despite
`__cpp_lib_to_chars` being undefined; the build breaks loudly if absent.
Production code targeting older libc++ would vendor `fast_float`.
- Portability: mmap/`unistd.h` make this POSIX-only; a Windows port swaps in
`MapViewOfFile`.