wc -l appears to be consistently slower than gnu implementation

@sylvestre

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.

@drinkcat

@drinkcat if you want a small challenge ;)

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

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

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).

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.

Nice! Quick work!

@jnsgruk

@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)

Navigation Menu

Repository navigation

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

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

wc -l appears to be consistently slower than gnu implementation #7929

Description

Activity

sylvestre commented on May 13, 2025

drinkcat commented on May 13, 2025

drinkcat commented on May 14, 2025

drinkcat commented on May 14, 2025

drinkcat commented on May 14, 2025

jnsgruk commented on May 14, 2025

drinkcat commented on May 15, 2025

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

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