为什么我的Rust版本的"wc"慢于GNU coreutils的版本？

Question

考虑这个程序:

use std::io::BufRead;
use std::io;

fn main() {
    let mut n = 0;
    let stdin = io::stdin();
    for _ in stdin.lock().lines() {
        n += 1;
    }
    println!("{}", n);
}

为什么它比wc的GNU版本慢10倍？看看我如何测量它:

$ yes | dd count=1000000 | wc -l
256000000
1000000+0 records in
1000000+0 records out
512000000 bytes (512 MB, 488 MiB) copied, 1.16586 s, 439 MB/s
$ yes | dd count=1000000 | ./target/release/wc
1000000+0 records in
1000000+0 records out
512000000 bytes (512 MB, 488 MiB) copied, 41.685 s, 12.3 MB/s
256000000

Answer 1

您的代码比原始代码慢的原因有很多wc.你需要付出一些实际根本不需要的东西.通过删除它们,您已经可以获得相当大的速度提升.

堆分配

BufRead::lines()返回一个产生String元素的迭代器.由于这种设计,它(它必须!)为每一行分配内存.该lines()方法是一种方便编写代码的方法,但它不应该用于高性能情况.

为避免为每一行分配堆内存,可以BufRead::read_line()改为使用.代码有点冗长,但正如您所看到的,我们正在重用以下堆内存s:

let mut n = 0;
let mut s = String::new();
let stdin = io::stdin();
let mut lock = stdin.lock();
loop {
    s.clear();
    let res = lock.read_line(&mut s);
    if res.is_err() || res.unwrap() == 0 {
        break;
    }
    n += 1;
}
println!("{}", n);

在我的笔记本上,这导致:

$ yes | dd count=1000000 | wc -l
256000000
1000000+0 records in
1000000+0 records out
512000000 bytes (512 MB, 488 MiB) copied, 0,981827 s, 521 MB/s

$ yes | dd count=1000000 | ./wc 
1000000+0 records in
1000000+0 records out
512000000 bytes (512 MB, 488 MiB) copied, 6,87622 s, 74,5 MB/s
256000000

正如你所看到的,它改进了很多东西,但仍然不等同.

UTF-8验证

由于我们正在读取a String,我们正在验证stdin的原始输入是否是正确的UTF-8.这需要时间!但是我们只对原始字节感兴趣,因为我们只需要计算换行符(0xA).我们可以通过使用Vec<u8>和删除UTF-8检查BufRead::read_until():

let mut n = 0;
let mut v = Vec::new();
let stdin = io::stdin();
let mut lock = stdin.lock();
loop {
    v.clear();
    let res = lock.read_until(0xA, &mut v);
    if res.is_err() || res.unwrap() == 0 {
        break;
    }
    n += 1;
}
println!("{}", n);

这导致:

1000000+0 records in
1000000+0 records out
512000000 bytes (512 MB, 488 MiB) copied, 4,24162 s, 121 MB/s
256000000

这是一个60%的改善.但原版wc仍然快3.5倍!

进一步改进

现在我们用掉所有低悬的水果来提升性能.wc我认为,为了匹配速度,我们必须做一些严肃的分析.在我们当前的解决方案中,perf报告如下:

• 大约11%的时间花在memchr; 我不认为这可以改善
• 大约18%用于<StdinLock as std::io::BufRead>::fill_buf()和
• 约占6% <StdinLock as std::io::BufRead>::consume()

剩余时间的很大一部分main直接用于(由于内联).从它的外观来看,我们也为跨平台抽象付出了一些代价.Mutex方法和东西花了一些时间.

但在这一点上,我只是猜测,因为我没有时间进一步研究这个问题.对不起:<

但请注意,这wc是一个旧工具,并针对其运行的平台以及正在执行的任务进行了高度优化.我想有关Linux内部事物的知识会对性能有很大帮助.这是非常专业的,所以我不希望轻松匹配性能.

Answer 2

这是因为你的版本绝不等同于没有为字符串分配任何内存的GNU,而只是移动文件指针并递增不同的计数器.此外,它处理原始字节,而Rust String必须是有效的UTF-8.

GNU wc源码

Answer 3

这是我在＃rust-beginners IRC上从Arnavion获得的版本：

use std::io::Read;

fn main() {
    let mut buffer = [0u8; 1024];
    let stdin = ::std::io::stdin();
    let mut stdin = stdin.lock();
    let mut wc = 0usize;
    loop {
        match stdin.read(&mut buffer) {
            Ok(0) => {
                break;
            },
            Ok(len) => {
                wc += buffer[0..len].into_iter().filter(|&&b| b == b'\n').count();
            },
            Err(err) => {
                panic!("{}", err);
            },
        }
    };
    println!("{}", wc);
}

这使性能非常接近原始版本wc。