| Age | Commit message (Collapse) | Author | Lines |
|---|
|
It now doesn't fully rebuild the heap, but only the parts that are
necessary.
|
|
alloc: Added `as_slice` method to `BinaryHeap` collection
I initially asked about whether it is useful addition on https://internals.rust-lang.org/t/should-i-add-as-slice-method-to-binaryheap/13816, and it seems there were no objections, so went ahead with this PR.
> There is [`BinaryHeap::into_vec`](https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html#method.into_vec), but it consumes the value. I wonder if there is API design limitation that should be taken into account. Implementation-wise, the inner buffer is just a Vec, so it is trivial to expose as_slice from it.
Please, guide me through if I need to add tests or something else.
UPD: Tracking issue #83659
|
|
|
|
|
|
Improve sift_down performance in BinaryHeap
Replacing `child < end - 1` with `child <= end.saturating_sub(2)` in `BinaryHeap::sift_down_range` (surprisingly) results in a significant speedup of `BinaryHeap::into_sorted_vec`. The same substitution can be done for `BinaryHeap::sift_down_to_bottom`, which causes a slight but probably statistically insignificant speedup for `BinaryHeap::pop`. It's interesting that benchmarks aside from `bench_into_sorted_vec` are barely affected, even those that do use `sift_down_*` methods internally.
| Benchmark | Before (ns/iter) | After (ns/iter) | Speedup |
|--------------------------|------------------|-----------------|---------|
| bench_find_smallest_1000<sup>1</sup> | 392,617 | 385,200 | 1.02 |
| bench_from_vec<sup>1</sup> | 506,016 | 504,444 | 1.00 |
| bench_into_sorted_vec<sup>1</sup> | 476,869 | 384,458 | 1.24 |
| bench_peek_mut_deref_mut<sup>3</sup> | 518,753 | 519,792 | 1.00 |
| bench_pop<sup>2</sup> | 446,718 | 444,409 | 1.01 |
| bench_push<sup>3</sup> | 772,481 | 770,208 | 1.00 |
<sup>1</sup>: internally calls `sift_down_range`
<sup>2</sup>: internally calls `sift_down_to_bottom`
<sup>3</sup>: should not be affected
|
|
|
|
Because child > 0, the two statements are equivalent, but using
saturating_sub and <= yields in faster code. This is most notable in the
binary_heap::bench_into_sorted_vec benchmark, which shows a speedup of
1.26x, which uses sift_down_range internally. The speedup of pop (that
uses sift_down_to_bottom internally) is much less significant as the
sifting method is not called in a loop.
|
|
|
|
|
|
|
|
|
|
Clarify what the effects of a 'logic error' are
This clarifies what a 'logic error' is (which is a term used to describe what happens if you put things in a hash table or btree and then use something like a refcell to break the internal ordering). This tries to be as vague as possible, as we don't really want to promise what happens, except "bad things, but not UB". This was discussed in #80657
|
|
|
|
See #77433 for why the new heuristic was chosen.
Fixes #77433
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Avoid useless sift_down when std::collections::binary_heap::PeekMut is never mutably dereferenced
If `deref_mut` is never called then it's not possible for the element to be mutated without internal mutability, meaning there's no need to call `sift_down`.
This could be a little improvement in cases where you want to mutate the biggest element of the heap only if it satisfies a certain predicate that needs only read access to the element.
|
|
r=jyn514
Move to intra-doc links in library/alloc/src/collections/binary_heap.rs
Helps with #75080.
@rustbot modify labels: T-doc, A-intra-doc-links
|
|
|
|
|
|
|
|
Co-authored-by: Joshua Nelson <joshua@yottadb.com>
|
|
Co-authored-by: Joshua Nelson <joshua@yottadb.com>
|
|
Co-authored-by: Joshua Nelson <joshua@yottadb.com>
|
|
Co-authored-by: Joshua Nelson <joshua@yottadb.com>
|
|
|
|
|
|
|
|
|
|
|
|
private trait instead
|
|
|
|
|
|
|
|
|
|
|
