`wc -l` appears to be consistently slower than gnu implementation

[jnsgruk]

I was experimenting with wc -l against the 1 Billion Rows Challenge dataset today.

Running against the GNU implementation, it seems that uutils' implementation doesn't quite perform as well:

❯ hyperfine --warmup 3 "wc -l measurements.txt" "/usr/lib/cargo/bin/coreutils/wc -l measurements.txt"
Benchmark 1: wc -l measurements.txt
  Time (mean ± σ):      1.846 s ±  0.005 s    [User: 0.158 s, System: 1.685 s]
  Range (min … max):    1.836 s …  1.856 s    10 runs

Benchmark 2: /usr/lib/cargo/bin/coreutils/wc -l measurements.txt
  Time (mean ± σ):      2.128 s ±  0.008 s    [User: 0.520 s, System: 1.601 s]
  Range (min … max):    2.120 s …  2.147 s    10 runs

Summary
  wc -l measurements.txt ran
    1.15 ± 0.01 times faster than /usr/lib/cargo/bin/coreutils/wc -l measurements.txt

Where measurements.txt is just a very large text file with 1 billion short lines.

I was discussing with @sylvestre this morning, and he can also reproduce. I tried with both 0.0.24 and 0.0.30 on Ubuntu 24.04 LTS.

[sylvestre]

@drinkcat if you want a small challenge ;)

[drinkcat]

That does look fun, I'll take a look!

[drinkcat]

I can reproduce with some simple output of seq.

There is a lot of variability, so sometimes it's better to look at the minimum number in the range (the example below doesn't have this problem), and I sandwiched the rust version between coreutils runs to avoid thermal concerns:

seq 10000000000000 1 inf | head -n 100000000 > seq100M
cargo build -r -p uu_wc && taskset -c 0 hyperfine --warmup 10 -L wc wc,target/release/wc,wc "{wc} -l tmp/seq100M"
    Finished `release` profile [optimized] target(s) in 0.10s
Benchmark 1: wc -l tmp/seq100M
  Time (mean ± σ):     244.9 ms ±   5.9 ms    [User: 44.3 ms, System: 197.8 ms]
  Range (min … max):   239.5 ms … 262.3 ms    12 runs
 
Benchmark 2: target/release/wc -l tmp/seq100M
  Time (mean ± σ):     265.1 ms ±   5.2 ms    [User: 50.4 ms, System: 211.7 ms]
  Range (min … max):   256.9 ms … 278.2 ms    11 runs
 
Benchmark 3: wc -l tmp/seq100M
  Time (mean ± σ):     245.8 ms ±   5.7 ms    [User: 42.6 ms, System: 200.5 ms]
  Range (min … max):   242.2 ms … 261.7 ms    12 runs
  
Summary
  wc -l tmp/seq100M ran
    1.00 ± 0.03 times faster than wc -l tmp/seq100M
    1.08 ± 0.03 times faster than target/release/wc -l tmp/seq100M

[drinkcat]

Ok, 2 things:

First, super low hanging fruit, increasing read buffer size from 16kb to 128kb improves performance by about 4%. That's half the difference.

Second, the rest of the performance difference is probably in bytecount's AVX2 code. That library does something a bit complicated:

    while haystack.len() >= offset + 32 * 255 {
        let mut counts = _mm256_setzero_si256();
        for _ in 0..255 {
            counts = _mm256_sub_epi8(
                counts,
                _mm256_cmpeq_epi8(mm256_from_offset(haystack, offset), needles),
            );
            offset += 32;
        }
        count += sum(&counts);
    }

Basically accumulating counts into each byte of a 256-bit vector, then summing them up.

But GNU's wc does a much tighter loop (just looking at disassembly in samply):

vpcmpeqb ymm0, ymm1, ymmword [rdx] << compares, set all 1 in each byte if equal, 0 if not
vpmovmskb esi, ymm0 << Picks the MSb from each byte
popcnt esi, esi << counts the number of 1

I'll try to modify bytecount and run benchmarks (intuition would be that the simpler code is faster, but we'll need to check of course).

[drinkcat]

The second part was a red herring, it seems like both approaches are very similar in performance (once I managed to get Rust to actually emit popcnt).

But! Performance increases significantly if the buffer is aligned on a 32-byte boundary (#[repr(align(32))] in a wrapping structure).

We're on par with GNU with those 2 changes (larger, aligned buffer).

cargo build -r -p uu_wc && taskset -c 0 hyperfine --warmup 10 -L wc ./wc.main,target/release/wc,wc "{wc} -l tmp/seq100M"
    Finished `release` profile [optimized] target(s) in 0.12s
Benchmark 1: ./wc.main -l tmp/seq100M
  Time (mean ± σ):     265.9 ms ±   4.0 ms    [User: 50.0 ms, System: 212.9 ms]
  Range (min … max):   262.2 ms … 276.6 ms    11 runs
 
Benchmark 2: target/release/wc -l tmp/seq100M
  Time (mean ± σ):     244.0 ms ±   2.3 ms    [User: 38.5 ms, System: 203.6 ms]
  Range (min … max):   240.9 ms … 247.9 ms    12 runs
 
Benchmark 3: wc -l tmp/seq100M
  Time (mean ± σ):     243.6 ms ±   3.0 ms    [User: 44.8 ms, System: 197.0 ms]
  Range (min … max):   236.6 ms … 246.5 ms    12 runs
 
Summary
  wc -l tmp/seq100M ran
    1.00 ± 0.02 times faster than target/release/wc -l tmp/seq100M
    1.09 ± 0.02 times faster than ./wc.main -l tmp/seq100M

I'll clean up and push later. Nice thing here is that these changes are all contained within coreutils.

[jnsgruk]

Nice! Quick work!

[drinkcat]

@jnsgruk #7934. Might be nice to test on your machine, performance profile might be a bit different on different CPUs.

(I'm running this on the P core of a i7-1370P -- that's a laptop chip)