I/O: `.lines()` iterator is slower than a manual loop over `.read_line()` due to allocations

[Shnatsel]

BufRead::lines() is a convenient way to read line-by-line. But since it implements the Iterator trait which allows .collect()ing the elements, it allocates every line on the heap separately.

A manual loop over BufRead::read_line() is significantly faster because you can reuse a single buffer for all lines, although it is more verbose.

Code using .lines():

    for line in reader.lines() {
        // TODO: process the line
    }

Manual read_line loop reusing the same buffer:

    let mut line = String::new();
    while reader.read_line(&mut line)? != 0 { // 0 bytes read is how the OS indicates that we reached end of file
        // TODO: process the line
        line.clear(); // clear the buffer after each line, or we'll end up with the whole file in memory!
    }

Benchmark results on this public domain book in plain text format repeated 50 times:

Benchmark 1: target/release/lines ~/repeated_book
  Time (mean ± σ):     132.0 ms ±  10.8 ms    [User: 122.9 ms, System: 9.0 ms]
  Range (min … max):   118.6 ms … 161.0 ms    100 runs
 
Benchmark 2: target/release/read_line ~/repeated_book
  Time (mean ± σ):      97.2 ms ±  10.4 ms    [User: 87.9 ms, System: 9.2 ms]
  Range (min … max):    90.5 ms … 131.8 ms    100 runs
 
Summary
  'target/release/read_line ~/repeated_book' ran
    1.36 ± 0.18 times faster than 'target/release/lines ~/repeated_book'

Exact code used for benchmarks:
https://github.com/Shnatsel/fast-io-cookbook/blob/82ae9bd106002c4d7ffeb6f263b9ae8c05ffe95e/src/bin/lines.rs
https://github.com/Shnatsel/fast-io-cookbook/blob/82ae9bd106002c4d7ffeb6f263b9ae8c05ffe95e/src/bin/read_line.rs

[Shnatsel]

There is still a little bit of performance left on the table. read_line copies the data from the BufRead buffer to the output buffer; you can avoid that copy and save a tiny bit of time using the for_byte_line method from bstr crate. Paired with simdutf8 for UTF-8 validation it ekes out another 8% on my machine:

use bstr::io::BufReadExt; // external crate `bstr`
use simdutf8; // external crate for faster UTF-8 validation

// ... 

reader.for_byte_line(|byte_line| {
    let line = simdutf8::basic::from_utf8(line);
    // TODO: process the line
    Ok(true)
})?;

Benchmarks:

$ hyperfine --warmup 20 -m 300 --parameter-list FILE 'repeated_book' 'target/release/lines {FILE}' 'target/release/read_line {FILE}'  'target/release/bstr_for_byte_line_simdutf8 {FILE}'
Benchmark 1: target/release/lines repeated_book
  Time (mean ± σ):     131.0 ms ±   8.7 ms    [User: 119.7 ms, System: 11.2 ms]
  Range (min … max):   120.9 ms … 168.4 ms    300 runs
 
Benchmark 2: target/release/read_line repeated_book
  Time (mean ± σ):      95.9 ms ±   7.4 ms    [User: 85.9 ms, System: 10.1 ms]
  Range (min … max):    90.9 ms … 123.2 ms    300 runs
 
Benchmark 3: target/release/bstr_for_byte_line_simdutf8 repeated_book
  Time (mean ± σ):      88.5 ms ±   7.7 ms    [User: 77.8 ms, System: 10.6 ms]
  Range (min … max):    84.5 ms … 122.2 ms    300 runs
 
Summary
  'target/release/bstr_for_byte_line_simdutf8 repeated_book' ran
    1.08 ± 0.13 times faster than 'target/release/read_line repeated_book'
    1.48 ± 0.16 times faster than 'target/release/lines repeated_book'

Full code used: https://github.com/Shnatsel/fast-io-cookbook/blob/82ae9bd106002c4d7ffeb6f263b9ae8c05ffe95e/src/bin/bstr_for_byte_line_simdutf8.rs

[nnethercote]

Interesting! I tried this out on my counts utility, but it turns out I need a separate string per line anyway because (a) sometimes it makes modifications to the line, and (b) it puts the line into a hash map, which requires a String.

I see you have https://github.com/Shnatsel/fast-io-cookbook/, can you tell me about that?

[Shnatsel]

I was thinking of another article and repository about fast I/O, similar to what I did for bounds checks (article, repo).

But I don't know if I will ever complete it because I'm not sure I have enough material, writing an article is a lot of work, and I have other priorities right now.

My findings for reading lines are already laid out above. I also have interesting results about reading the whole file.

std::fs::read that loads the whole file in memory is much slower than making a 32k buffer and reading into it in 32k chunks, then processing each chunk. This is because when reading the whole file you write the entire thing into RAM and read it back when processing it, while the small buffer stays in CPU cache. This makes more than 2x difference on my machine.

I've also tried mmap, and it's a complex beast. When the whole file is already cached in memory, it can give a 10% to 15% speedup compared to manual reads. But if the file is on disk and has not been read over and over to get fully cached in RAM (like you would do in a benchmarking loop), there is no difference (you can verify this by dropping FS caches before each measurement). I was going to advise against using mmap because it is impossible to use safely without copying the data or turning it into &[Cell<u8>] instead of [&u8], which negates all performance benefits.

You can also find the code for all of these in the cookbook repo.

[Shnatsel]

Also, the performance of Read::bytes() is atrocious, even over a BufReader. It's 10x slower than reading the whole file into memory up front and 20x slower than manually reading into a smallish buffer over and over.

That is by far the worst pitfall I've seen yet.

[nnethercote]

Interesting! I tried this out on my counts utility, but it turns out I need a separate string per line anyway because (a) sometimes it makes modifications to the line, and (b) it puts the line into a hash map, which requires a String.

After thinking some more I worked out a way to avoid the need for String in a lot of cases. On my Mac laptop this doubled the speed for some inputs! See nnethercote/counts@7d39bbb.

Now that I have a nice example, I will add this to the perf-book, probably next week.