hashmap - Rust基准测试优化

Question

我正在尝试对从Rust哈希映射中获取 key 进行基准测试。我有以下基准:

#[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 the hash.get(＆k ) in the for loop with test::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);
    };
  });
}

Here是要点。

Answer 1

How does a compiler optimizer work?

优化器不过是analyses and transformations的管道。每个单独的分析或转换都相对简单，并且应用它们的最佳顺序是未知的，并且通常由启发式方法确定。

How does this affect my benchmark?

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

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

哪些不受欢迎，

如何挫败他们。

如前所述，大多数 channel 比较简单，因此挫败它们也相对简单。困难在于这样的事实:它们有一百多个或更多，并且您必须知道哪个人在踢，才能挫败它。

What optimizations am I running afoul of?

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

Constant Propagation:允许在编译时评估部分代码

Loop Invariant Code Motion:允许在循环之外提升对某些代码段

的评估

Dead Code Elimination:删除无用的代码。

What? How dare the optimizer mangle my code so?

优化器在所谓的假设规则下运行。该基本规则允许优化器执行任何不改变程序输出的转换。也就是说，它一般不应更改程序的可观察行为。

最重要的是，通常明确允许进行一些更改。最明显的是预计运行时间会减少，这反过来意味着线程交织可能会有所不同，并且某些语言会提供更多的回旋余地。

I used black_box!

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

转换后的代码必须执行与原始代码

相同数量的black_box调用

转换后的代码必须按照传入参数

的相同顺序执行所述调用

不能假设black_box返回的值。

因此，black_box的外科手术使用可以挫败某些优化。但是，盲目使用可能无法阻止正确的使用。

What optimizations am I running afoul of?

让我们从朴素的代码开始:

#[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():

hash.get()的结果未使用，

hash.get()是一个纯函数，表示没有副作用。

因此，此循环可以重写为:

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

我们违反了死代码消除(或某些变体):代码没有任何作用，因此被消除了。

甚至可能是编译器足够聪明，以至于可以将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);或上面的 map 来实现。如果要对空 map 进行基准测试，则后者是必要的，在这里它们是相等的。

因此，我们得到:

#[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));
        }
    });
}

A final tip.

基准测试非常复杂，您应该格外小心，仅对您希望基准测试的东西进行基准测试。

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

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，然后为空循环计时。