hashmap - 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：删除无用的代码。
什么？优化器怎么敢这样破坏我的代码？
优化器在所谓的“仿佛”规则下运行。这个基本规则允许优化器执行任何不改变程序输出的转换。也就是说，它一般不应该改变程序的可观察行为。
除此之外，通常还明确允许进行一些更改。最明显的是，运行时预计会缩减，这反过来意味着线程交错可能会有所不同，有些语言甚至会有更大的回旋余地。
我用过！
什么是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);
        }
    });
}

假设black_box中的循环将迭代所有键，并为每个键执行b.iter()：
hash.get()的结果未使用，
hash.get()是一个纯功能，意味着它没有副作用。
因此，此循环可以重写为：

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

我们正在与死代码消除（或某些变体）发生冲突：代码没有作用，因此被消除。
它甚至可能是编译器足够聪明，能够意识到hash.get()可以优化为for k in keys.drain(..) {}。
然而，drop(keys)的外科应用可以挫伤DCE：

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

根据上述black_box的影响：
无法再优化循环，因为它会将调用数更改为black_box，
对black_box的每个调用都必须使用预期的参数执行。
仍然有一个可能的障碍：持续的传播。特别是，如果编译器意识到所有键都产生相同的值，它可以优化出black_box并用所述值替换它。
这可以通过混淆键：hash.get(&k)来实现，正如您在上面所做的，或者映射。如果要对空映射进行基准测试，则必须使用后者，在这里它们是相等的。
因此我们得到：

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

最后的提示。
基准测试非常复杂，您应该格外小心，只对希望基准测试的内容进行基准测试。
在这种特殊情况下，有两个方法调用：
let mut keys = black_box(keys);，
keys.drain()。
因为基准名称对我来说意味着，您的目标是测量hash.get()的性能，所以我只能假设对get的调用是一个错误。
因此，基准实际上应该是：

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

在本例中，更为关键的是传递给keys.drain(..)的闭包需要运行多次：如果第一次耗尽密钥，那么之后还剩下什么？空的。。。
... 这可能就是这里真正发生的一切；因为b.iter()运行闭包直到其时间稳定，它可能只是在第一次运行时排出Vec，然后计时一个空循环。