Part 001: The first naive version

1. read_to_string loads the whole file into memory

read_to_string reads the entire 13.8 GB file into a single String before the loop starts. The 1B file is 13.8 GB and my machine has 16 GB of RAM. The program did finish, but only after macOS compressed and swapped most of that memory, and it took 2.5× as long as Jon's (see 1B over time). On a machine with less free RAM it would not finish at all. On the 1M and 100M files the same code works fine, which makes this easy to miss.

The general rule: never assume the input fits in memory. The usual way around it is streaming: read the file in small chunks and process it as you go. That's what Jon's version does with BufReader + .lines(). It reads one buffer at a time (8 KB by default), so memory use stays constant however big the file is:

let f = BufReader::new(File::open("input/1B_measurements.txt").unwrap());
for line in f.lines() { /* one line at a time */ }

How the two compare:

Two things in that table are easy to miss:

• Mine is not worse in every row. Because the whole file is already in one String, str::lines() hands out slices into it without allocating anything. Jon's BufRead::lines() has to copy every line out of the buffer into its own String, because the buffer gets overwritten by the next read. When I switch to BufReader, I'll gain constant memory but get an allocation per line that I don't have today.
• The difference on 100M isn't about reading. Reading the file is ~1 % of the run time (see Where the time goes in the code). Mine is slower there because of the Vec per line and the double map lookup. Only on the 1B file, where the String doesn't fit into RAM, does the way of reading decide the time.

Next step: switch my version to BufReader, like Jon's (see Next steps). Reading the file with mmap is on the TODO list for later.

2. split_once instead of split().collect::<Vec<_>>()

Mine collects the pieces into a Vec, which allocates on the heap for every line (1 billion allocations on the 1B file), just to read two items.

str::split_once returns Option<(&str, &str)>. It doesn't allocate, and pattern matching replaces the indexing:

let (station, temperature) = line.split_once(';').unwrap();

The two &str don't copy anything, they point into the original line. A &str is a wide pointer: the address of the first byte plus a length, 8 + 8 = 16 bytes on a 64-bit CPU. For the line Hamburg;12.0:

the line in memory:   H a m b u r g ; 1 2 . 0
                      ▲               ▲
station     = (pointer ┘, length 7)  "Hamburg"
temperature = (pointer ───────────┘, length 4)  "12.0"

So the whole result is 2 × 16 = 32 bytes, on the stack or straight in CPU registers. The Option around it costs nothing extra: a pointer is never null, so Rust uses null to mean None.

The time profile of the 100M run shows both costs (see Where the time goes in the code): ~9 % of the time goes to allocating and freeing memory, ~20 % to searching for the ;. split_once removes the allocation completely and makes the search shorter.

Next step: use split_once (see Next steps).

3. Looking up a station: contains_key + get_mut, entry, or just get_mut

Both versions look up the station in the map for every line, but each pays for something different.

Mine searches the map twice when the station is already there: once in contains_key and again in get_mut. It only allocates a String for the key in the else branch, i.e. for a new station:

if location_to_measurement.contains_key(location) {                 // lookup 1, with a &str
    let measurement_stats = location_to_measurement.get_mut(location).unwrap();   // lookup 2
    // update
} else {
    location_to_measurement.insert(location.to_string(), /* … */);   // String only here
}

Jon's uses the entry API, which needs only one lookup:

let stats = map
    .entry(station.to_string())
    .or_insert((f64::MAX, 0., 0, f64::MIN));
stats.0 = stats.0.min(temperature);
// …

But entry wants an owned key, so station.to_string() allocates a String for every line, even when the station is already in the map and the String is thrown away right after.

It also initializes a new entry twice: first with neutral values (f64::MAX for the minimum, f64::MIN for the maximum, 0 for the sum and the count), which the update right below immediately overwrites. That keeps a single code path for the first and every later measurement. It doesn't cost anything noticeable: it only happens when a new station is inserted, and the insert itself (allocating the String, adding it to the tree) costs far more than writing four numbers twice.

and_modify reads nicer, with no neutral values and no double initialization. Exactly one of the two branches runs:

map.entry(station.to_string())
    .and_modify(|s| {                        // only if the station is already there
        s.0 = s.0.min(temperature);
        s.1 += temperature;
        s.2 += 1;
        s.3 = s.3.max(temperature);
    })
    .or_insert((temperature, temperature, 1, temperature));   // only if it's new

(or_insert alone with the first measurement wouldn't work: it doesn't tell whether the entry was just inserted, so the update below it would count the first measurement twice.)

This is the version I'll switch to next (see Next steps): one lookup, no neutral values, and it reads well.

It still allocates a String for every line, though. The fastest option with the standard library is a single get_mut with a &str, and insert only for a new station:

if let Some(s) = map.get_mut(station) {      // one lookup, no allocation
    // update
} else {
    map.insert(station.to_string(), (temperature, temperature, 1, temperature));
}

For a station that's already in the map:

For a new station it's the other way round: get_mut fails and insert searches again, so entry is better there. Which case dominates depends on the data, and the 1BRC rules say implementations "must not rely on specifics of a given data set". What they do guarantee is that "there is a maximum of 10,000 unique station names" (1BRC rules). With a billion rows, at most 10,000 of them can insert a new station, and all others update an existing one. So get_mut + insert is the better choice for every valid input, not just my file with its 413 stations. The lesson: optimize for the specification, not for the sample data.

4. f64::min / f64::max instead of manual if comparisons

stats.0 = stats.0.min(temperature);
stats.3 = stats.3.max(temperature);

These are shorter and say what they mean. Mine uses f32, which has the same methods (f32::min / f32::max).

Next step: use .min() / .max() instead of the if comparisons (see Next steps).

5. f32, f64 or integers?

I used f32 for the sum, Jon uses f64. Both give the same output on my files, but they behave very differently once you look at what a float can store.

How a float stores a number. A float is stored as 1.xxx… × 2^exponent. The bits after the point (the mantissa) carry the precision, and the leading 1. isn't stored, it's always 1:

f32:  [sign 1 bit][exponent  8 bits][mantissa 23 bits]  → 24 bits of precision
f64:  [sign 1 bit][exponent 11 bits][mantissa 52 bits]  → 53 bits of precision

So a float can only store a limited set of values, and the gap between two neighbouring values grows with the number: between 2^e and 2^(e+1) it is 2^(e − 23) for f32. Every result is rounded to the nearest value that can be stored:

f64 has the same pattern, only much later: it stores every integer exactly up to 2⁵³ ≈ 9 × 10¹⁵.

My file. With 413 stations, each station gets ~2.4 million measurements on the 1B file, so its sum grows to tens of millions. Past ~1 million, f32 already can't store tenths, and every addition gets rounded. I expected this to break the 1B results, but it didn't: the output is identical to Jon's f64 version on all 413 stations. The rounding errors are small and go both up and down, so they mostly cancel out.

The worst case the rules allow. But my file isn't the point: the 1BRC rules say any distribution must work, and every temperature is between −99.9 and 99.9. The worst valid input is all 10⁹ rows for one station, each with 99.9. The exact sum is 10⁹ × 99.9 = 99,900,000,000. I ran exactly that, a billion additions of 99.9:

• f32 gets stuck. From 2³¹ ≈ 2.15 × 10⁹ on, the gap between neighbouring values is 256. Adding 99.9 lands closer to the old sum than to the next value up (99.9 is less than half of 256), so it rounds back to the same sum. The sum stops growing after ~21 million rows, and the other ~979 million rows are lost.
• f64 survives. Its sum is off by ~1,164, but divided by a billion rows that's an error of ~0.000001 in the mean, far below the 0.05 that would change the printed tenth.

f64 still isn't exact. Values like 12.3 have no exact binary representation, and a mean that lies exactly halfway between two tenths can round either way. On an earlier 100K-row test file, two stations had such a mean (Gangtok 16.25, Monaco 15.55; the 1BRC rules round half up, so 16.3 and 15.6 are correct). Each version rounded one of them the wrong way:

Which way a tie rounds comes down to a tiny error in the sum. So Jon's output is a useful reference, but not a perfect oracle.

The robust fix: integers in tenths. Every temperature has exactly one decimal place, so it can be stored as a whole number of tenths: 12.3 becomes 123, -5.0 becomes -50. Integer sums are exact, and the mean is rounded once, at the end, from an exact value. Each value can use the smallest type that fits the worst case:

Together that's 16 bytes per station instead of the 32 bytes of Jon's (f64, f64, usize, f64), so more stations fit into the CPU caches.

I'm not doing this yet, Jon will almost certainly get there in the stream. It's on the TODO list, together with parsing the temperature straight into tenths.

6. Struct vs tuple

Jon uses a tuple (f64, f64, usize, f64) and accesses it as stats.0, stats.3, and so on. I use a named struct, MeasurementStats. Jon says himself that it should really be a struct; the tuple is just the quick way to start.

Performance is the same. A tuple and a struct with the same fields take the same memory ((f64, f64, usize, f64) and a struct with those four fields are both 32 bytes), and stats.0 and stats.min compile to the same instruction: a read at a fixed offset. My 16 bytes vs Jon's 32 come from the types (f32 and u32 vs f64 and usize), not from struct vs tuple.

The difference is in how you work with it:

The biggest win is methods: the update logic can live in the struct, for example a new that creates the stats from the first measurement and an add that updates them with the next one. The loop then just calls s.add(temperature) or MeasurementStats::new(temperature) and reads like a description of what happens. I'll write these methods in a later part.

Next step: give MeasurementStats the methods new and add (see Next steps).

7. Format string details

The two versions print the same line in two different ways.

Mine:

println!("{}={1:.1}/{2:.1}/{3:.1}", location, stats.min, stats.sum / stats.count as f32, stats.max);

Jon's:

println!("{station}={min:.1}/{:.1}/{max:.1}", sum / (count as f64));

There are three ways to refer to a value in a format string. After the colon comes the format: {:.1}, {1:.1} and {min:.1} all mean "round to one decimal place".

Compared:

Why doesn't Jon capture everything? Only a plain variable can be captured, not an expression like sum / count and not a field like stats.min. Jon unpacks the tuple into the variables station, min, sum, count and max in the while let, so he can capture those, and passes the mean, which is an expression, as an argument. Mine keeps the values in a struct (stats.min), so it can't capture them as they are.

None of these styles is faster: println! is a macro, and the format string is taken apart at compile time. What does cost something is how println! writes: in the System Trace of the 100M run, my version made 413 write system calls, one per line of output. A BufWriter would collect the lines and write them in a few big calls. That's on the TODO list.

Next step: rewrite my println! so the names are in the string (see Next steps).

8. Silent vs loud failure

Mine skips malformed lines without saying anything (if split.len() == 2). Jon's .unwrap() panics on them instead. For a benchmark with a known-good input, failing loudly is arguably better, because a skipped line would quietly produce a wrong result.

Next step: fail loudly like Jon's version (see Next steps).