Copy link

Contributor

rust-highfive commented on Aug 24

r? @Mark-Simulacrum

(rust-highfive has picked a reviewer for you, use r? to override)

This comment has been hidden.

This comment has been hidden.

This comment has been hidden.

This comment has been hidden.

This comment has been hidden.

the8472 commented on Aug 24

BinaryHeap doesn't have many benchmarks, maybe some could be added to show an improvement.

SkiFire13 commented on Aug 24

I'm not sure if this is something for this PR, but I just noticed that the current specialization is on I rather than I::IntoIter. This means that only BinaryHeap<T> and Vec<T> benefit from these specializations, while std::vec::IntoIter and std::collections::binary_heap::IntoIter do not.

For comparison this is how it's implemented for Vec:

I believe we should copy Vec's code and specialize SpecExtend for std::vec::IntoIter and std::collections::binary_heap::IntoIter instead.

Mark-Simulacrum commented on Aug 24

Can you please inline the relevant pieces of discussion / why this is a win in general, etc. from the internals thread? This both avoids having to re-read that for context and ensures it's preserved for any future visitor (into git commit history).

Neutron3529 commented on Aug 25 •

Can you please inline the relevant pieces of discussion / why this is a win in general, etc. from the internals thread? This both avoids having to re-read that for context and ensures it's preserved for any future visitor (into git commit history).

I edited the first post:

as scottmcm mentioned:

BinaryHeap::append already has heuristics for how to extend BinaryHeap<T> with Vec<T>; updating extend to do the same seems perfectly reasonable.

is it enough? @Mark-Simulacrum

JohnCSimon commented on Sep 12

Triage: setting this to waiting on review

Mark-Simulacrum commented on Sep 15 •

It looks like this PR is doing two separate things:

• Adding a specialization for extending with a Vec<T>
• Modifying the non-specialized extend algorithm

This first of these makes sense, seems fine, but the second I don't see a description of the goal in this PR. It also seems like these two changes are orthogonal and should belong in separate PRs?

FWIW, saying "discussion is here" and pointing into the middle of an internals thread is not ideal; the PR description should ideally be self-contained or at least only point to documents or summary comments, not just discussion threads. This will speed up review and make the flow easier for everyone.

@rustbot author

(Please adjust the label with @rustbot ready when you're ready for another review).

This comment has been hidden.

rustbot commented on Sep 15

@Neutron3529

JohnCSimon commented 22 days ago

Ping from triage:

@Neutron3529 - can you please address the merge conflicts and
adjust the label with @rustbot ready when you're ready for another review

Neutron3529 commented 14 days ago

@rustbot ready
I deleted the improvement that could speed up the default extend method which may end up with a double panic.
then, there is no conflict.

It might be meanful that mark fn rebuild_tail as pub unsafe, or add some new function like extend_batch to gain benefit from the fast rebuild_tail algorithm

Please update the PR description to reflect the current state of this PR. Otherwise, this PR looks good to me, r=me with the description updated and commits squashed.

Neutron3529 commented 10 days ago

@rustbot ready
done~

bors commented 8 days ago

Commit 2feee36 has been approved by Mark-Simulacrum

bors commented 8 days ago

Testing commit 2feee36 with merge ad44239...

bors commented 8 days ago

Test successful - checks-actions
Approved by: Mark-Simulacrum
Pushing ad44239 to master...

rust-timer commented 8 days ago

Finished benchmarking commit (ad44239): comparison url.

Summary: This change led to moderate relevant mixed results in compiler performance.

• Moderate improvement in instruction counts (up to -0.3% on incr-unchanged builds of ripgrep)
• Small regression in instruction counts (up to 0.4% on incr-unchanged builds of regression-31157)

If you disagree with this performance assessment, please file an issue in rust-lang/rustc-perf.

Next Steps: If you can justify the regressions found in this perf run, please indicate this with @rustbot label: +perf-regression-triaged along with sufficient written justification. If you cannot justify the regressions please open an issue or create a new PR that fixes the regressions, add a comment linking to the newly created issue or PR, and then add the perf-regression-triaged label to this PR.

@rustbot label: +perf-regression