u8::reverse_bits is too slow

[gnzlbg]

While upgrading the bitintr crate I re-ran its benchmarks and found out that the stable implementation there is much faster than the stabilized u8::reverse_bits intrinsic available on nightly.

I'm comparing this implementation of u8::reverse_bits:

fn rbit_u8(x: u8) -> u8 {
    (((((x as u64) * 0x80200802_u64) & 0x0884422110_u64) * 0x0101010101_u64)
        >> 32) as u8
}

vs u8::reverse_bits.

My benchmark there isn't super tight, each iteration calls reverse_bits on all [0, 255] integers :

fn u8_runner<F: Fn(u8) -> u8>(bench: &mut Bencher, f: F) {
    bench.iter(|| {
        for v in 0..=u8::max_value() {
            bencher::black_box(f(bencher::black_box(v)));
        }
    })
}

#[bench]
fn rbit_u8_std(bench: &mut Bencher) {
    u8_runner(bench, |x| x.reverse_bits()))
}

#[bench]
fn rbit_u8_self(bench: &mut Bencher) {
    u8_runner(bench, |x| rbit_u8(x)))
}

On my laptop (x86_64 1.8Ghz i5), I'm getting 343 ns/iter for rbit_u8, while for u8::reverse_bits I'm getting 619 ns/iter. Dividing by 256 that's 1.34 (mine) vs 2.42 (libstd) ns / bitreverse.

All of this somehow rings a bell; the bitintr crate had a benchmark specifically for this operation, and it was previously comparing its own implementations against core::intrinsic::bitreverse, and it had a workaround for using its own implementation even when the user was on nightly and explicitly enabled using core::intrinsics via an unstable cargo feature. I guess I should have written a comment back then.

[gnzlbg]

cc @Amanieu

[Amanieu]

This should be fixed in LLVM, as a better lowering of the bitreverse intrinsic.

[gnzlbg]

Ok, I knew I almost had a dejavu: https://bugs.llvm.org/show_bug.cgi?id=31810

This is blocked on that LLVM issue being resolved.

[nagisa]

This is x86-specific. Most of the other supported architectures have a dedicated instruction for this.

[nikic]

It would help if the LLVM issue was clarified wrt which expansion actually needs to be implemented. The current issue reads rather confused with a lot of contradictory benchmark results.

[gnzlbg]

@nikic it appears that for different users on different micr-architectures different implementations might be better. So while the current implementation is good for some users, it is bad for others. To make progress, one would probably need to benchmark the different implementations on the different micro-architectures that LLVM supports, and see if that fits with the reported benchmarks by the different users there.

[nagisa]

It is not strictly necessary to benchmark all the approaches – the instruction cost model should be able to fairly accurately deduce the cost of the operation on all sorts of targets. Not sure if it is possible, but a reasonable implementation may be one which selects a specific lowering from many based on such a model.

[steveklabnik]

Triage: I tried to create a reproduction, but am getting overflow: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=95c284b261fd57733f807001e25a48fe

[Amanieu]

Use wrapping_mul.