7

Github Improve sift_down performance in BinaryHeap by hanmertens · Pull Request...

 3 years ago
source link: https://github.com/rust-lang/rust/pull/81127
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Copy link

Contributor

hanmertens commented on Jan 17

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_10001 392,617 385,200 1.02 bench_from_vec1 506,016 504,444 1.00 bench_into_sorted_vec1 476,869 384,458 1.24 bench_peek_mut_deref_mut3 518,753 519,792 1.00 bench_pop2 446,718 444,409 1.01 bench_push3 772,481 770,208 1.00

1: internally calls sift_down_range
2: internally calls sift_down_to_bottom
3: should not be affected


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK