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

Question

我试图复制 this famous 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)

所以我们再次得到了我们期望的数字。所以问题是：

奇怪的运行ning次是什么原因？

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 = u8 LLVM 生成 SSE2 指令来进行向量运算，速度要快得多。理论上，LLVM 应该能够将 filter(...).fold(...) 优化为相同的代码，但在实践中它并不总是能消除抽象的开销。我希望当添加 MIR 时，Rust 不会依赖 LLVM 来进行特定于 Rust 的优化。

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

Trying famous branch-prediction example sometimes results in strange times

performance

optimization

rust

branch-prediction