7

我有许多 4KiB 缓冲区，它们有 50% 的机会只包含零值。非零缓冲区通常在缓冲区的早期有一个非零字节。

fn is_zero(buf: &Vec<u8>) -> bool {
    for byte in buf.into_iter() {
        if *byte != 0 {
            return false;
        }
    }
    return true;
}

这是检查 Rust 的一种高效方式--release吗？（我正在处理许多 GB 的数据。）

（在 C 版本中，我unsigned long long在检查之前将缓冲区转换为。考虑到 SSE 等，这可能不是我能做的最好的事情。）

4

4 回答 4

7

您align_to可以将切片 ofu8转换为 切片u128，从而使比较更有效：

fn is_zero(buf: &[u8]) -> bool {
    let (prefix, aligned, suffix) = unsafe { buf.align_to::<u128>() };

    prefix.iter().all(|&x| x == 0)
        && suffix.iter().all(|&x| x == 0)
        && aligned.iter().all(|&x| x == 0)
}

在我的机器上运行一个简单的基准测试显示了 16 倍的性能提升！

#![feature(test)]
extern crate test;

fn v() -> Vec<u8> {
    std::iter::repeat(0).take(1000000).collect()
}

fn is_zero(buf: &[u8]) -> bool {
    buf.into_iter().all(|&b| b == 0)
}

fn is_zero_aligned(buf: &[u8]) -> bool {
    let (prefix, aligned, suffix) = unsafe { buf.align_to::<u128>() };

    prefix.iter().all(|&x| x == 0)
        && suffix.iter().all(|&x| x == 0)
        && aligned.iter().all(|&x| x == 0)
}

#[bench]
fn bench_is_zero(b: &mut test::Bencher) {
    let v = test::black_box(v());
    b.iter(|| is_zero(&v[..]))
}

#[bench]
fn bench_is_zero_aligned(b: &mut test::Bencher) {
    let v = test::black_box(v());
    b.iter(|| is_zero_aligned(&v[..]))
}

running 2 tests
test tests::bench_is_zero         ... bench:     455,975 ns/iter (+/- 414)
test tests::bench_is_zero_aligned ... bench:      28,615 ns/iter (+/- 116)

根据您的机器，不同的整数类型 ( u64) 可能会产生更好的性能。

感谢 Rust discord 服务器上的@Globi 提供的想法

于 2020-12-20T01:22:02.937 回答
4

byteorder通过一次阅读，在我的笔记本电脑上发现了 4 倍的加速u64，在本机字节序中。

库文件

extern crate byteorder;

use byteorder::{NativeEndian, ReadBytesExt};
use std::io::Cursor;

pub fn one(buf: &[u8]) -> bool {
    buf.into_iter().all(|&byte| byte == 0)
}

pub fn two(buf: &[u8]) -> bool {
    let mut cur = Cursor::new(buf);
    while let Ok(val) = cur.read_u64::<NativeEndian>() {
        if val != 0 {
            return false;
        }
    }
    while let Ok(val) = cur.read_u8() {
        if val != 0 {
            return false;
        }
    }
    true
}

长凳/benches.rs

#![feature(test)]

extern crate test;
extern crate zero_slice_8;

use zero_slice_8::{one, two};

fn v() -> Vec<u8> {
    let mut result = vec![];
    for _ in 0..100000 {
        result.push(0);
    }
    result
}

#[bench]
fn bench_one(b: &mut test::Bencher) {
    let v = v();
    b.iter(|| one(&v[..]))
}

#[bench]
fn bench_two(b: &mut test::Bencher) {
    let v = v();
    b.iter(|| two(&v[..]))
}
于 2020-12-19T11:51:29.790 回答
1

以下函数是纯保存Rust：

fn is_zero ( slice : &[u8] ) -> bool {
    for i in (0..slice.len()).step_by(16) {
        if slice.len() - i >= 16 {
            let arr : [u8; 16] = slice[i..i+16].try_into().expect("this should always succeed");
            if u128::from_be_bytes(arr) != 0 {
                return false;
            }
        } else {
            for i in i..slice.len() {
                if slice[i] != 0 {
                    return false;
                }
            }
        }
    }
    return true;
}

具体来说，它使用u128::from_be_bytes函数将[u8; 16]数组转换u128为非操作的 a，并使用TryIntotrait 将[u8]适当长度的 a 转换为 a [u8; 16]—— 其余部分相当简单。可以手动展开内部循环以对其进行转换，但我怀疑这将是一个重要的性能瓶颈，u8即构成列表尾部的不是干净的 16 字节的 s 会起作用。

根据处理器的不同，使用u64甚至u32可能更快，必须自己分析。

于 2020-12-19T14:19:05.740 回答
1

您可以使用rayon，这是一个似乎非常适合您的用例的数据并行库。使用非常简单：只需更改buf.iter()为buf.par_iter()，其余的由 Rayon 完成：

use rayon::prelude::*;

fn is_zero_par(buf: &[u8]) -> bool {
    buf.par_iter().all(|&b| b == 0)
}

对于 2000 万个元素的向量，人造丝的性能提高了 7 倍：

#![feature(test)]
use rayon::prelude::*;
extern crate test;

fn v() -> Vec<u8> {
    std::iter::repeat(0).take(20000000).collect()
}

fn is_zero(buf: &[u8]) -> bool {
    buf.into_iter().all(|&b| b == 0)
}

fn is_zero_par(buf: &[u8]) -> bool {
    buf.par_iter().all(|&b| b == 0)
}

#[bench]
fn bench_is_zero(b: &mut test::Bencher) {
    let v = test::black_box(v());
    b.iter(|| is_zero(&v[..]))
}

#[bench]
fn bench_is_zero_par(b: &mut test::Bencher) {
    let v = test::black_box(v());
    b.iter(|| is_zero_par(&v[..]))
}

running 2 tests
test tests::bench_is_zero     ... bench:   7,217,686 ns/iter (+/- 478,845)
test tests::bench_is_zero_par ... bench:   1,080,959 ns/iter (+/- 111,692)

请注意，多线程的性能影响取决于工作负载（元素数量），较小的工作负载可能会受到负面影响。

于 2020-12-19T23:33:43.557 回答