// The One Billion Row Challenge: the lowest, mean and highest temperature
// of each weather station, from one reading per line.
//
// printf 'Hamburg;12.0\nBulawayo;8.9\nHamburg;-3.4\n' > measurements.txt
// nikaia run -- measurements.txt
// {Bulawayo=8.9/8.9/8.9, Hamburg=-3.4/4.3/12.0}
//
// To parse on every core, add `user-parallelism = "yes"` under `[build]` in
// nikaia.toml; for timing, also `opt-level = 3` under `[build.x86_64-linux]`.
// Name the project `brc`, not `1brc`: a package name cannot start with a digit.
//
// Shows: a `grammar` that describes the whole file, a parallel `par_fold`,
// names that are slices of a memory-mapped file rather than copies, and a
// format spec inside an f-string.
//
// To run it, copy this file to `src/main.nika` of a project (guide/getting-started.md).
use std::fs
use std::cli
use std::text
use std::collections
// ---------------------------------------------------------------------------
// 1. A grammar for the file
// ---------------------------------------------------------------------------
// A grammar for the whole file, not for one line: it is called once and walks
// the bytes itself. There is no tokenizer, so station names may contain blanks,
// dots and non-ASCII text.
grammar Measurements {
// An uppercase rule is *lexical*: nothing is skipped between its parts, so
// "Hamburg " with a trailing blank is a station of its own.
//
// The `String` is a slice of the input, never a copy.
//
// The scan stops at the `;` or at `frame_end`, the line end that
// MEASUREMENT below declares. A plain `until(";")` could run into the next
// line, and the compiler rejects it here.
rule NAME -> String = s:until(";" | frame_end) -> { s }
// Temperatures always carry exactly one decimal, so they are parsed as
// tenths and all the arithmetic stays in integers until printing.
// `digit{1,2}` is the width the format allows (-99.9 to 99.9), so
// "123.0" is a parse error. `dec[i32](…)` hands over the number those
// digits write rather than their text, so the action has nothing left to
// decode.
rule TENTHS -> i32 =
neg:"-"? whole:dec[i32](digit{1,2}) "." frac:digit
-> {
let value = whole * 10 + text::digit_value(frac)
if neg != null { -value } else { value }
}
// `=>` is a commit point: once the `;` is there, the line is a measurement,
// and a bad temperature after it is reported, not retried as something else.
//
// `@frame` says a measurement can be found from any offset by scanning to
// the next "\n", so the file can be cut into pieces and parsed in parallel.
// The compiler checks that no scan inside the frame can run past it (see NAME).
@frame(boundary: "\n")
rule MEASUREMENT -> Reading =
name:NAME ";" => temp:TENTHS frame_end
-> { Reading { name, temp } }
// `MEASUREMENT*` would collect a billion readings into memory. A fold
// instead passes each one to an accumulator, so the parse runs in
// constant space. `par_fold` also says how two partial results merge;
// with that and the frame, the compiler writes the splitting, one
// accumulator per core and the final merge. The merge is exact because
// everything is summed in integer tenths.
entry rule file -> Summary =
par_fold(MEASUREMENT, Summary, fn(acc, m) { acc.record(m) },
Summary::merge)
}
struct Reading {
name: String,
temp: i32,
}
// ---------------------------------------------------------------------------
// 2. Aggregation
// ---------------------------------------------------------------------------
struct Stats {
min: i32,
max: i32,
sum: i64,
count: i64,
}
impl Stats {
fn(first: i32) -> Stats {
return Stats { min: first, max: first, sum: first as i64, count: 1 }
}
fn add(ref mut self, temp: i32) {
if temp < self.min { self.min = temp }
if temp > self.max { self.max = temp }
self.sum += temp as i64
self.count += 1
}
fn merge(ref mut self, other: ref Stats) {
if other.min < self.min { self.min = other.min }
if other.max > self.max { self.max = other.max }
self.sum += other.sum
self.count += other.count
}
// The mean in tenths, rounded as the challenge rounds: a tie goes up,
// toward +infinity (`Math.round` in the official Java baseline). Exact
// integer arithmetic, no float: `div_euclid` divides rounding down, also
// when the sum is negative.
fn mean(ref self) -> i64 {
return (2 * self.sum + self.count).div_euclid(2 * self.count)
}
}
// The stations seen so far and their statistics. The keys are slices of the
// input too.
struct Summary {
stations: collections::HashMap[String, Stats],
}
impl Summary {
fn() -> Summary {
return Summary { stations: collections::HashMap() }
}
fn record(ref mut self, m: Reading) {
self.stations
.entry(m.name)
.and_modify fn (stats) { stats.add(m.temp) }
.or_insert_with fn { Stats(m.temp) }
}
fn merge(ref mut self, other: Summary) {
for (name, stats) in other.stations.drain() {
self.stations
.entry(name)
.and_modify fn (into) { into.merge(ref stats) }
.or_insert(stats)
}
}
}
// ---------------------------------------------------------------------------
// 3. Main: the I/O half
// ---------------------------------------------------------------------------
fn main() throws {
let path = cli::args().nth(1) ?? "measurements.txt"
// `fs::map` maps the file into memory instead of reading it, so a file of
// many gigabytes is never copied, and every station name points into it.
// No `async` or `await` is written: I/O does not block, and the code reads
// straight through. `catch` runs its block when the call fails, with the
// failure named `error`.
let data = fs::map(ref path, fs::Root::Anywhere) catch {
eprintln(f"cannot open {path}: {error}")
return
}
// The whole parse. With no `catch`, a bad line leaves `main` through
// `throws` and ends the program with an error that gives its line number
// in the whole file, even when the file was parsed in pieces.
let totals = Measurements::file(data)
let mut names = totals.stations.keys().collect()
names.sort()
let body = names
.map fn(name) {
// A map lookup gives a `Stats?` that may be absent. `??` supplies
// the other case; the key came from this map, so it cannot happen.
let s = totals.stations[name] ?? panic(f"{name} was a key a moment ago")
f"{name}={tenths(s.min as i64)}/{tenths(s.mean())}/{tenths(s.max as i64)}"
}
.join(", ")
// In an f-string, `{{` and `}}` are literal braces.
println(f"{{{body}}}")
}
// A value in tenths as the challenge prints it: one decimal, never `-0.0`.
fn tenths(t: i64) -> String {
if t < 0 {
let a = -t
return f"-{a / 10}.{a % 10}"
}
return f"{t / 10}.{t % 10}"
}The file itself · all the examples