rust-lang / rust-clippy

A bunch of lints to catch common mistakes and improve your Rust code. Book: https://doc.rust-lang.org/clippy/
https://rust-lang.github.io/rust-clippy/
Other
11.52k stars 1.55k forks source link

Suggest faster `.contains()` instead of `.iter().any()` for `[u8]` and `[i8]` slices #13353

Open nyurik opened 3 months ago

nyurik commented 3 months ago

What it does

Suggest to replace values.iter().any(|&x| x == 10) with values.contains(&10) as shown in the example for x being u8 or an i8. Contains uses specialization, thus gains 8-10x in performance.

The generated assembly is significantly different too (see here).

Advantage

Drawbacks

Example

#[inline(never)]
pub fn has_any(values: &[u8]) -> bool {
    values.iter().any(|&x| x == 10)
}

Could be written as:

#[inline(never)]
pub fn ref_zero(values: &[u8]) -> bool {
    values.contains(&10)
}
nyurik commented 3 months ago

If anyone wants to try it, run this with cargo bench:

[dev-dependencies]
criterion = { version = "0.5", features = ["html_reports"] }

[[bench]]
name = "my_benchmark"
harness = false
// benches/my_benchmark.rs
use std::hint::black_box;
use criterion::{criterion_group, criterion_main, Criterion};

#[inline(never)]
pub fn contains(values: &[u8]) -> bool {
    values.contains(&10)
}

#[inline(never)]
pub fn has_any(values: &[u8]) -> bool {
    values.iter().any(|x| *x == 10)
}

fn criterion_benchmark(c: &mut Criterion) {
    let data = vec![20u8; 1000];
    let slice = &data[..];
    c.bench_function("ref_zero", |b| b.iter(|| contains(black_box(slice))));
    c.bench_function("has_any", |b| b.iter(|| has_any(black_box(slice))));
}

criterion_group!(benches, criterion_benchmark);
criterion_main!(benches);
Jarcho commented 3 months ago

This is from specialization for u8 and i8. See https://github.com/rust-lang/rust/blob/9c01301c52df5d2d7b6fe337707a74e011d68d6f/library/core/src/slice/cmp.rs#L232-L259

nyurik commented 3 months ago

@Jarcho ah, thx, i missed the specialization. Thus, it makes perfect sense to do this as a lint for u8 and i8