尝试着名的分支预测示例有时会导致奇怪的时间

Question

我试图在这个着名的问题中复制这个例子.我的代码看起来像这样:

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

use test::Bencher;
use rand::{thread_rng, Rng};

type ItemType = u8;
type SumType = u64;
const TEST_SIZE: usize = 32_768;

#[bench]
fn bench_train(b: &mut Bencher) {
    let numbers = get_random_vec();
    b.iter(|| calc_sum(&numbers));
}

#[bench]
fn bench_train_sort(b: &mut Bencher) {
    let mut numbers = get_random_vec();
    numbers.sort();     // <-- the magic difference
    b.iter(|| calc_sum(&numbers));
}

fn get_random_vec() -> Vec<ItemType> {
    thread_rng().gen_iter().take(TEST_SIZE).collect()
}

fn calc_sum(numbers: &Vec<ItemType>) -> SumType {
    let mut sum = 0;
    for &num in numbers {
        if num < ItemType::max_value() / 2 {
            sum += num.into();
        }
    }

    sum
}

如果我对上面的确切代码进行基准测试,我会得到合理的结果(比如在链接的问题中):

test bench_train      ... bench:     148,611 ns/iter (+/- 8,445)
test bench_train_sort ... bench:      21,064 ns/iter (+/- 1,980)

但是,如果我更改SumType为u8两个版本,则运行速度相同且速度更快:

test bench_train      ... bench:       1,272 ns/iter (+/- 64)
test bench_train_sort ... bench:       1,280 ns/iter (+/- 170)

第一个:当然,sum会一直溢出,但在释放模式下,Rust的溢出检查被禁用,所以我们只计算错误的结果而不会感到恐慌.这可能是出乎意料地短暂时间的原因吗？

更奇怪的是:当我将实现更改为calc_sum更惯用的东西时,结果会再次发生变化.我的第二个实施:

fn calc_sum(numbers: &Vec<ItemType>) -> SumType {
    numbers.iter()
        .filter(|&&num| num < ItemType::max_value() / 2)
        .fold(0, |acc, &num| acc + (num as SumType))
}

通过这种实现,SumType无所谓了.随着u8以及与u64我得到这些结果:

test bench_train      ... bench:     144,411 ns/iter (+/- 12,533)
test bench_train_sort ... bench:      16,966 ns/iter (+/- 1,100)

所以我们再次得到我们期待的数字.所以问题是:

奇怪的运行时间是什么原因？

---

PS:我cargo bench在发布模式下测试了哪些编译.

PPS:我刚注意到在calc_sum我into()用于投射的第一个实现中,而我as在第二个例子中使用.当as在第一个例子中使用时,我得到更多奇怪的数字.用SumType = u64:

test bench_train      ... bench:      39,850 ns/iter (+/- 2,355)
test bench_train_sort ... bench:      39,344 ns/iter (+/- 2,581)

用SumType = u8:

test bench_train      ... bench:       1,184 ns/iter (+/- 339)
test bench_train_sort ... bench:       1,239 ns/iter (+/- 85)

Answer 1

我快速查看了汇编程序代码,看来如果你使用SumType = u8LLVM会生成SSE2指令来执行向量操作,这要快得多.理论上,LLVM应该能够优化filter(...).fold(...)到相同的代码,但实际上它不能总是消除抽象的开销.我希望在添加MIR时,Rust不会依赖LLVM来执行特定于Rust的优化.