优化的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);
    };
  });
}

Here是完整的要点。

Answer 1

编译器优化器是如何工作的？

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

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

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

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

• 哪些是不受欢迎的，
• 如何挫败它们。

如前所述，大多数传球都是相对简单的，因此挫败它们也相对简单。困难之处在于，它们有上百个或更多，你必须知道哪一个正在发挥作用才能挫败它。

我遇到了哪些优化问题？

有几个特定的优化经常与基准测试一起发挥作用：

• Constant Propagation：允许在编译时评估部分代码，
• Loop Invariant Code Motion：允许在循环外提升某些代码的评估，
• Dead Code Elimination：删除无用的代码。

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

优化器在所谓的as-if规则下运行。这个基本规则允许优化器执行任何不改变程序输出的转换。也就是说，它通常不应该改变程序的可观察行为。

最重要的是，一些更改通常是明确允许的。最明显的是运行时预计会缩小，这反过来意味着线程交错可能会有所不同，一些语言甚至提供了更大的回旋余地。

我用的是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()：

• hash.get()是一个纯函数，表示没有side-effect.

，

1. 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进行基准测试，后者将是必要的，在这里它们是相等的。

因此，我们得到：

#[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，然后对一个空循环进行计时。