rgoussu.dev
rgoussu@goussu: ~/library/java/exercises
❯ ~/library/java/exercises cat one-billion-row-challenge-subject.md

One Billion Row Challenge — subject

# The 1BRC spec restated — input and output formats, the billion-row generator, the same-machine measurement protocol, and the staged optimization ladder with the expected technique per stage.

Subjectsaved 2026-08-08source #exercise#java#jvm#performance#profiling#1brc#subject

Brief

One text file, one billion rows of temperature readings, one job: print min/mean/max per weather station, in Java, as fast as you can make it. The naive solution takes minutes; the leaderboard's best run in seconds on the same hardware. The gap is the exercise — closed one measured optimization at a time, never by guessing.

Instructions

The spec

  • Input — measurements.txt: one reading per line, <station>;<temperature>\n. Station name: UTF-8, 1–100 bytes, no ; or newline (a few hundred to ~10k distinct stations). Temperature: a decimal with exactly one fractional digit, -99.9 to 99.9 (e.g. Hamburg;12.0, Bulawayo;8.9, St. John's;-1.5).
  • Output — to stdout, stations sorted alphabetically, one run of <station>=<min>/<mean>/<max> each with one fractional digit, mean rounded half-up, in the format {Abha=-23.0/18.0/59.2, Abidjan=10.1/26.4/50.5, ...}.
  • Generator — produce the 1B-row file with the upstream repo's generator (create_measurements.sh), or write an equivalent one (station list + Gaussian per station). The file is ~13 GB; generate once, reuse for every run.

Measurement protocol

  • Same machine for every measurement, otherwise numbers don't compare. Note its specs (CPU, cores, RAM, disk) once.
  • Warm the file into page cache (or accept and note the cold-read cost consistently); time with hyperfine or repeated time runs — at least 3 runs per version, report the best or median, consistently.
  • Keep a running results table: version, change made, wall time, delta. Every ladder stage adds a row. A change without a row didn't happen.

The optimization ladder

Climb in order; at each stage, profile first (JFR or async-profiler), change the one thing the profile indicts, measure, and record.

  1. Baseline — BufferedReader.lines(), String.split(";"), HashMap<String, DoubleSummaryStatistics-ish>. Correct output, honest wall time: your denominator.
  2. Fix what the profiler shows — expected kills: split and substring allocation (parse the line by index yourself), autoboxed Doubles (primitive min/sum/max/count accumulators), repeated String hashing. Single-threaded still.
  3. Parallel chunks — split the file into N byte ranges aligned to newline boundaries, one worker per chunk, merge the per-station accumulators at the end. Try platform vs. virtual threads and record why the numbers barely differ (CPU-bound, no blocking to unmount).
  4. Memory-map + bytes — MappedByteBuffer or the FFM API's MemorySegment; parse raw bytes with no String creation until final output; temperatures as scaled integers (-1.5 → -15), custom byte-level number parse.
  5. Leaderboard tricks (optional but scored) — read top entries and port techniques one at a time: SWAR-style multi-byte scanning for ;/newline, branchless temperature parsing, a custom open-addressing hash keyed on raw name bytes. Keep only what your table shows earns its complexity.

Constraints

  • Java only, single JVM process, no external dependencies for the computation itself (the original challenge's rule); any JDK distribution you like — note which.
  • Correct output at every stage — a fast wrong answer is worthless. Diff each version's output against the baseline's before timing it.
  • No optimization lands without a profile pointing at it and a results-table row behind it.

Examples

Input fragment:

Hamburg;12.0
Bulawayo;8.9
Palembang;38.8
St. John's;15.2
Hamburg;34.2

Matching output fragment (alphabetical, min/mean/max):

{Bulawayo=8.9/8.9/8.9, Hamburg=12.0/23.1/34.2, Palembang=38.8/38.8/38.8, St. John's=15.2/15.2/15.2}

Acceptance

Mapped one-to-one onto the exercise's milestones:

  1. Baseline — the 1B-row file exists; the naive solution produces byte-correct output; its wall time is the results table's first row.
  2. Profile & fix the obvious — a profile artifact exists for the baseline; the single-threaded optimized version is measurably faster, with per-change rows showing which fix bought what.
  3. Go parallel — chunked parallel version merges correctly (output still byte-identical); scaling vs. core count recorded; the platform-vs-virtual-threads comparison has numbers and a one-line explanation.
  4. Memory-map it — no String allocated per line (verify by allocation profile); scaled-integer parsing; the table shows the drop.
  5. Steal like an engineer — at least one leaderboard technique ported, measured, and kept or reverted based on the numbers; the final table tells the whole story from baseline to best.

Related