sekineh / binary-heap-plus-rs

Enhancement over Rust's `std::collections::BinaryHeap`. Supports other than max heap.
MIT License
57 stars 18 forks source link

Avoid sift_down for unmutated PeekMut (rust#75974) #27

Closed cuviper closed 4 years ago

cuviper commented 4 years ago

This ports the change from rust-lang/rust#75974 -- PeekMut is now constructed with sift: false, and it is only set true by DerefMut. The same benchmarks are included this PR, and here are my results on this crate:

 name                      bench.master ns/iter  bench.75974 ns/iter  diff ns/iter   diff %  speedup
 bench_find_smallest_1000  358,162               240,945                  -117,217  -32.73%   x 1.49
 bench_from_vec            519,992               519,116                      -876   -0.17%   x 1.00
 bench_into_sorted_vec     336,279               309,787                   -26,492   -7.88%   x 1.09
 bench_peek_mut_deref_mut  457,992               1,117,506                 659,514  144.00%   x 0.41
 bench_pop                 364,764               360,842                    -3,922   -1.08%   x 1.01
 bench_push                487,726               483,631                    -4,095   -0.84%   x 1.01

So bench_find_smallest_1000 is much improved, while bench_peek_mut_deref_mut is much worse, just as they found in the standard library. The latter was justified as being "highly artificial" in https://github.com/rust-lang/rust/pull/75974#pullrequestreview-492011705.

cuviper commented 4 years ago

Hmm, CI failed 1.31.1 because of the new dev-dependency for the benchmarks, where rand only supports Rust 1.32. Let me know how you'd like to deal with that -- could use an older rand, or just forgo the benchmarks here.

sekineh commented 4 years ago

Thanks for the PR! I think we can bump the minimum supported rustc version to 1.32 or something. (In that case, I'll bump crate ver to 0.4.0)

Hmm, CI failed 1.31.1 because of the new dev-dependency for the benchmarks, where rand only supports Rust 1.32. Let me know how you'd like to deal with that -- could use an older rand, or just forgo the benchmarks here.

cuviper commented 4 years ago

OK, I've bumped to 1.32 and CI is happy. I'll leave it to you whether it would be beneficial to bump further for other features.

sekineh commented 4 years ago

LGTM, Thanks!