Rust基准优化了

Question

我正在尝试从Rust哈希映射中获取密钥.我有以下基准:

#[bench]
fn rust_get(b: &mut Bencher) {
    let (hash, keys) =
        get_random_hash::<HashMap<String, usize>>(&HashMap::with_capacity, &rust_insert_fn);
    let mut keys = test::black_box(keys);
    b.iter(|| {
        for k in keys.drain(..) {
            hash.get(&k);
        }
    });
}

其中get_random_hash定义为:

fn get_random_hash<T>(
    new: &Fn(usize) -> T,
    insert: &Fn(&mut T, String, usize) -> (),
) -> (T, Vec<String>) {
    let mut keys = Vec::with_capacity(HASH_SIZE);
    let mut hash = new(HASH_CAPACITY);
    for i in 0..HASH_SIZE {
        let k: String = format!("{}", Uuid::new_v4());
        keys.push(k.clone());
        insert(&mut hash, k, i);
    }
    return (hash, keys);
}

并rust_insert_fn是:

fn rust_insert_fn(map: &mut HashMap<String, usize>, key: String, value: usize) {
    map.insert(key, value);
}

但是,当我运行基准测试时,它显然已经过优化:

test benchmarks::benchmarks::rust_get        ... bench:           1 ns/iter (+/- 0)

我认为test::black_box would solve the problem but it doesn't look like it does. I have even tried wrapping thehash.get(&k ) in the for loop withtest :: black_box`但仍然优化了代码.我应该如何正确地运行代码而不进行优化？

编辑 - 即使以下内容确实优化了get操作:

#[bench]
fn rust_get(b: &mut Bencher) {
  let (hash, keys) = get_random_hash::<HashMap<String, usize>>(&HashMap::with_capacity, &rust_insert_fn);
  let mut keys = test::black_box(keys);
  b.iter(|| {
    let mut n = 0;
    for k in keys.drain(..) {
      hash.get(&k);
      n += 1;
    };
    return n;
  });
}

有趣的是,以下基准测试工作:

#[bench]
fn rust_get_random(b: &mut Bencher) {
  let (hash, _) = get_random_hash::<HashMap<String, usize>>(&HashMap::with_capacity, &rust_insert_fn);
  b.iter(|| {
    for _ in 0..HASH_SIZE {
      hash.get(&format!("{}", Uuid::new_v4()));
    }
  });
}

#[bench]
fn rust_insert(b: &mut Bencher) {
  b.iter(|| {
    let mut hash = HashMap::with_capacity(HASH_CAPACITY);
    for i in 0..HASH_SIZE {
      let k: String = format!("{}", Uuid::new_v4());
      hash.insert(k, i);
    }
  });
}

但这也不是:

#[bench]
fn rust_del(b: &mut Bencher) {
  let (mut hash, keys) = get_random_hash::<HashMap<String, usize>>(&HashMap::with_capacity, &rust_insert_fn);
  let mut keys = test::black_box(keys);
  b.iter(|| {
    for k in keys.drain(..) {
      hash.remove(&k);
    };
  });
}

这是完整的要点.

Answer 1

编译器优化器如何工作？

优化器只不过是一个分析和转换的管道.每个单独的分析或转换都相对简单,应用它们的最佳顺序是未知的,通常由启发式确定.

这对我的基准测试有何影响？

基准测试很复杂,因为通常您希望测量优化的代码,但同时一些分析或转换可能会删除您感兴趣的代码,使基准测试无用.

因此,熟悉您正在使用的特定优化器的分析和转换过程非常重要,以便能够理解:

• 哪些是不受欢迎的,
• 如何陪衬他们.

如上所述,大多数通行证都相对简单,因此挫败它们也相对简单.困难在于它们中有一百个或更多,你必须知道哪一个正在踢它以便能够阻止它.

我与之相比有什么优化？

有一些特定的优化经常与基准测试一起发挥作用:

• Constant Propagation:允许在编译时评估部分代码,
• Loop Invariant Code Motion:允许在循环外提升某些代码的评估,
• 死代码消除:删除无用的代码.

什么？优化器怎么敢破坏我的代码呢？

优化器在所谓的as-if规则下运行.此基本规则允许优化程序执行任何不会更改程序输出的转换.也就是说,它不应该改变程序的可观察行为.

最重要的是,通常明确允许一些更改.最明显的是运行时间预计会缩小,这反过来意味着线程交错可能会有所不同,而且某些语言会提供更多的摆动空间.

我用过black_box!

什么是black_box？它是一个函数,其定义对优化器特别不透明.这对允许编译器执行的优化有一些影响,因为它可能有副作用.这因此意味着:

• 转换后的代码必须执行black_box与原始代码完全相同的调用次数,
• 转换后的代码必须按照传入的参数以相同的顺序执行所述调用,
• 不能对返回的值做出假设black_box.

因此,手术使用black_box可以阻止某些优化.然而,盲目使用可能无法阻止正确的使用.

我与之相比有什么优化？

让我们从天真的代码开始:

#[bench]
fn rust_get(b: &mut Bencher) {
    let (hash, mut keys): (HashMap<String, usize>, _) =
        get_random_hash(&HashMap::with_capacity, &rust_insert_fn);

    b.iter(|| {
        for k in keys.drain(..) {
            hash.get(&k);
        }
    });
}

假设内部循环b.iter()将迭代所有键并hash.get()为每个键执行a :

1. 结果hash.get()未使用,
2. hash.get()是一个纯函数,意思是没有副作用.

因此,这个循环可以重写为:

b.iter(|| { for k in keys.drain(..) {} })

我们正在与Dead Code Elimination(或某些变体)发生冲突:代码没有用处,因此它被删除了.

甚至可能是编译器足够智能以实现for k in keys.drain(..) {}可以优化的drop(keys).

black_box然而,罐头的手术应用箔DCE:

b.iter(|| {
    for k in keys.drain(..) {
        black_box(hash.get(&k));
    }
});

根据上述效果black_box:

• 循环无法再优化,因为它会改变调用次数black_box,
• black_box必须使用期望的参数执行每次调用.

仍然存在一个可能的障碍:恒定传播.特别是如果编译器意识到所有键都产生相同的值,它可以优化hash.get(&k)并用所述值替换它.

这可以通过混淆密钥来实现:let mut keys = black_box(keys);如上所述,或地图.如果你要对空地图进行基准测试,那么后者是必要的,在这里它们是相同的.

我们得到:

#[bench]
fn rust_get(b: &mut Bencher) {
    let (hash, keys): (HashMap<String, usize>, _) =
        get_random_hash(&HashMap::with_capacity, &rust_insert_fn);
    let mut keys = test::black_box(keys);

    b.iter(|| {
        for k in keys.drain(..) {
            test::black_box(hash.get(&k));
        }
    });
}

最后一个提示.

基准测试非常复杂,您应该格外小心,只能对您希望进行基准测试的基准进行基准测试.

在这种特殊情况下,有两种方法调用:

• keys.drain(),
• hash.get().

因为基准名称对我来说,你的目的是衡量绩效get,我只能假设这keys.drain(..)是一个错误.

因此,基准应该是:

#[bench]
fn rust_get(b: &mut Bencher) {
    let (hash, keys): (HashMap<String, usize>, _) =
        get_random_hash(&HashMap::with_capacity, &rust_insert_fn);
    let keys = test::black_box(keys);

    b.iter(|| {
        for k in &keys {
            test::black_box(hash.get(k));
        }
    });
}

在这种情况下,这更为关键的是,传递到的闭包b.iter()预计会多次运行:如果你第一次排空键,那么之后剩下的是什么？空Vec......

......这实际上可能就是这里发生的一切; 因为b.iter()运行闭包直到它的时间稳定,它可能只是Vec在第一次运行中耗尽然后计时空循环.