Use internal iteration in `Iterator` comparison methods #100845

timvermeulen · 2022-08-21T13:41:58Z

Updates the Iterator methods cmp_by, partial_cmp_by, and eq_by to use internal iteration on self. I've also extracted their shared logic into a private helper function iter_compare, which will either short-circuit once the comparison result is known or return the comparison of the lengths of the iterators.

This change also indirectly benefits calls to cmp, partial_cmp, eq, lt, le, gt, and ge.

Unsurprising benchmark results: iterators that benefit from internal iteration (like Chain) see a speedup, while other iterators are unaffected.

 name                           before ns/iter  after ns/iter  diff ns/iter   diff %  speedup 
 iter::bench_chain_partial_cmp  208,301         54,978             -153,323  -73.61%   x 3.79 
 iter::bench_partial_cmp        55,527          55,702                  175    0.32%   x 1.00 
 iter::bench_lt                 55,502          55,322                 -180   -0.32%   x 1.00

rustbot · 2022-08-21T13:42:01Z

Hey! It looks like you've submitted a new PR for the library teams!

If this PR contains changes to any rust-lang/rust public library APIs then please comment with @rustbot label +T-libs-api -T-libs to tag it appropriately. If this PR contains changes to any unstable APIs please edit the PR description to add a link to the relevant API Change Proposal or create one if you haven't already. If you're unsure where your change falls no worries, just leave it as is and the reviewer will take a look and make a decision to forward on if necessary.

Examples of T-libs-api changes:

Stabilizing library features
Introducing insta-stable changes such as new implementations of existing stable traits on existing stable types
Introducing new or changing existing unstable library APIs (excluding permanently unstable features / features without a tracking issue)
Changing public documentation in ways that create new stability guarantees
Changing observable runtime behavior of library APIs

rust-highfive · 2022-08-21T13:42:01Z

r? @thomcc

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

thomcc · 2022-08-22T05:02:19Z

@bors try @rust-timer queue

rust-timer · 2022-08-22T05:02:21Z

Awaiting bors try build completion.

@rustbot label: +S-waiting-on-perf

bors · 2022-08-22T05:02:28Z

⌛ Trying commit db2b4a3 with merge db6da14ee4410b3d56c50bb6a28be04047a08c91...

bors · 2022-08-22T06:27:50Z

☀️ Try build successful - checks-actions
Build commit: db6da14ee4410b3d56c50bb6a28be04047a08c91 (db6da14ee4410b3d56c50bb6a28be04047a08c91)

rust-timer · 2022-08-22T06:27:52Z

Queued db6da14ee4410b3d56c50bb6a28be04047a08c91 with parent 3ce46b7, future comparison URL.

rust-timer · 2022-08-22T08:40:02Z

Finished benchmarking commit (db6da14ee4410b3d56c50bb6a28be04047a08c91): comparison url.

Instruction count

Primary benchmarks: ❌ relevant regression found
Secondary benchmarks: no relevant changes found

	mean¹	max	count²
Regressions ❌ (primary)	1.2%	1.2%	1
Regressions ❌ (secondary)	-	-	0
Improvements ✅ (primary)	-	-	0
Improvements ✅ (secondary)	-	-	0
All ❌✅ (primary)	1.2%	1.2%	1

Max RSS (memory usage)

Results

Primary benchmarks: ❌ relevant regressions found
Secondary benchmarks: mixed results

	mean¹	max	count²
Regressions ❌ (primary)	3.1%	4.1%	3
Regressions ❌ (secondary)	1.8%	2.2%	5
Improvements ✅ (primary)	-	-	0
Improvements ✅ (secondary)	-3.4%	-3.4%	1
All ❌✅ (primary)	3.1%	4.1%	3

Cycles

Results

Primary benchmarks: no relevant changes found
Secondary benchmarks: ❌ relevant regression found

	mean¹	max	count²
Regressions ❌ (primary)	-	-	0
Regressions ❌ (secondary)	2.9%	2.9%	1
Improvements ✅ (primary)	-	-	0
Improvements ✅ (secondary)	-	-	0
All ❌✅ (primary)	-	-	0

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

Benchmarking this pull request likely means that it is perf-sensitive, so we're automatically marking it as not fit for rolling up. While you can manually mark this PR as fit for rollup, we strongly recommend not doing so since this PR may lead to changes in compiler perf.

Next Steps: If you can justify the regressions found in this try perf run, please indicate this with @rustbot label: +perf-regression-triaged along with sufficient written justification. If you cannot justify the regressions please fix the regressions and do another perf run. If the next run shows neutral or positive results, the label will be automatically removed.

@bors rollup=never
@rustbot label: +S-waiting-on-review -S-waiting-on-perf +perf-regression

the arithmetic mean of the percent change ↩ ↩² ↩³
number of relevant changes ↩ ↩² ↩³

thomcc · 2022-08-22T10:18:33Z

Hm, unsure about how much those regressions matter... I think in the past we've had perf issues with actually using internal iteration, even though it helps a lot for the iterator types it's important.

I think I might punt the review to @scottmcm if they don't mind, since IIRC they have a lot more experience with iterators and iteration perf in particular.

r? @scottmcm

(Feel free to punt back if you don't have the time to review this -- I just know it's an area you've worked on a lot, and might be better suited than I)

library/core/src/iter/traits/iterator.rs

scottmcm · 2022-09-24T03:53:19Z

library/core/src/iter/traits/iterator.rs

@@ -3613,29 +3595,26 @@ pub trait Iterator {
    /// assert!(xs.iter().eq_by(&ys, |&x, &y| x * x == y));
    /// ```
    #[unstable(feature = "iter_order_by", issue = "64295")]
-    fn eq_by<I, F>(mut self, other: I, mut eq: F) -> bool
+    fn eq_by<I, F>(self, other: I, eq: F) -> bool


Probably not this PR, but it might be interesting to experiment with a size_hint check for this one.

Something like

pub fn definitely_not_equal(a: &impl Iterator, b: &impl Iterator) -> bool { match (a.size_hint(), b.size_hint()) { ((a_lo, _), (_, Some(b_hi))) => b_hi < a_lo, ((_, Some(a_hi)), (b_lo, _)) => a_hi < b_lo, _ => false, } }

Since that could instantly catch a bunch of cases where things have good size_hints in practice, while also optimizing away completely for things that always return (0, None) since that'd obviously always be false overall.

For sure! I almost included that in this PR, in fact. It's a behavior change, but hopefully one we feel like we're permitted to make.

scottmcm · 2022-09-24T03:56:20Z

Thanks for this! It's a bit of a shame that it's asymmetric (which side has the chain matters), but I don't think there's any obvious solution for that. And we'll see what the after-merge perf run says, but I'm not too worried about 1 regression, when the instructions and cycles disagree anyway. Hopefully the new analysis that perf runs now will say that things are fine.

@bors r+ rollup=never

bors · 2022-09-24T03:56:22Z

📌 Commit db2b4a3 has been approved by scottmcm

It is now in the queue for this repository.

bors · 2022-09-24T04:04:49Z

⌛ Testing commit db2b4a3 with merge 0696895...

bors · 2022-09-24T06:55:26Z

☀️ Test successful - checks-actions
Approved by: scottmcm
Pushing 0696895 to master...

rust-timer · 2022-09-24T08:13:40Z

Finished benchmarking commit (0696895): comparison URL.

Overall result: ✅ improvements - no action needed

@rustbot label: -perf-regression

Instruction count

This is a highly reliable metric that was used to determine the overall result at the top of this comment.

	mean¹	range	count²
Regressions ❌ (primary)	-	-	0
Regressions ❌ (secondary)	-	-	0
Improvements ✅ (primary)	-1.1%	[-1.1%, -1.1%]	1
Improvements ✅ (secondary)	-	-	0
All ❌✅ (primary)	-1.1%	[-1.1%, -1.1%]	1

Max RSS (memory usage)

This benchmark run did not return any relevant results for this metric.

Cycles

Results

This is a less reliable metric that may be of interest but was not used to determine the overall result at the top of this comment.

	mean¹	range	count²
Regressions ❌ (primary)	-	-	0
Regressions ❌ (secondary)	4.7%	[4.7%, 4.7%]	1
Improvements ✅ (primary)	-2.3%	[-2.3%, -2.3%]	1
Improvements ✅ (secondary)	-	-	0
All ❌✅ (primary)	-2.3%	[-2.3%, -2.3%]	1

the arithmetic mean of the percent change ↩ ↩²
number of relevant changes ↩ ↩²

klensy · 2022-09-24T11:17:28Z

https://perf.rust-lang.org/compare.html?start=e1c28e0c857280ce829beab16ef6082cd518db98&end=06968954f7e11454d49377629bb57d13253384b9&stat=size%3Alinked_artifact

linked_artifact bigger by 48kb (no greens), but not object file.

Use internal iteration in Iterator::{cmp_by, partial_cmp_by, eq_by}

db2b4a3

rustbot added the T-libs Relevant to the library team, which will review and decide on the PR/issue. label Aug 21, 2022

rust-highfive assigned thomcc Aug 21, 2022

rust-highfive added the S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. label Aug 21, 2022

rustbot added the S-waiting-on-perf Status: Waiting on a perf run to be completed. label Aug 22, 2022

rustbot added perf-regression Performance regression. and removed S-waiting-on-perf Status: Waiting on a perf run to be completed. labels Aug 22, 2022

rust-highfive assigned scottmcm and unassigned thomcc Aug 22, 2022

scottmcm reviewed Aug 23, 2022

View reviewed changes

library/core/src/iter/traits/iterator.rs Show resolved Hide resolved

scottmcm reviewed Aug 23, 2022

View reviewed changes

library/core/src/iter/traits/iterator.rs Show resolved Hide resolved

scottmcm reviewed Aug 23, 2022

View reviewed changes

library/core/src/iter/traits/iterator.rs Show resolved Hide resolved

scottmcm reviewed Sep 24, 2022

View reviewed changes

bors removed the S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. label Sep 24, 2022

bors added the S-waiting-on-bors Status: Waiting on bors to run and complete tests. Bors will change the label on completion. label Sep 24, 2022

bors added the merged-by-bors This PR was explicitly merged by bors. label Sep 24, 2022

bors merged commit 0696895 into rust-lang:master Sep 24, 2022

rustbot added this to the 1.66.0 milestone Sep 24, 2022

rustbot removed the perf-regression Performance regression. label Sep 24, 2022

anatawa12 mentioned this pull request Feb 2, 2025

Tracking issue for iter_order_by #64295

Open

2 tasks

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Use internal iteration in `Iterator` comparison methods #100845

Use internal iteration in `Iterator` comparison methods #100845

timvermeulen commented Aug 21, 2022

rustbot commented Aug 21, 2022

rust-highfive commented Aug 21, 2022

thomcc commented Aug 22, 2022

rust-timer commented Aug 22, 2022

bors commented Aug 22, 2022

bors commented Aug 22, 2022

rust-timer commented Aug 22, 2022

rust-timer commented Aug 22, 2022

thomcc commented Aug 22, 2022

scottmcm Sep 24, 2022

timvermeulen Sep 24, 2022

scottmcm commented Sep 24, 2022 •

edited

Loading

bors commented Sep 24, 2022

bors commented Sep 24, 2022

bors commented Sep 24, 2022

rust-timer commented Sep 24, 2022

klensy commented Sep 24, 2022

Use internal iteration in Iterator comparison methods #100845

Use internal iteration in Iterator comparison methods #100845

Conversation

timvermeulen commented Aug 21, 2022

rustbot commented Aug 21, 2022

rust-highfive commented Aug 21, 2022

thomcc commented Aug 22, 2022

rust-timer commented Aug 22, 2022

bors commented Aug 22, 2022

bors commented Aug 22, 2022

rust-timer commented Aug 22, 2022

rust-timer commented Aug 22, 2022

Footnotes

thomcc commented Aug 22, 2022

Choose a reason for hiding this comment

Choose a reason for hiding this comment

scottmcm commented Sep 24, 2022 • edited Loading

bors commented Sep 24, 2022

bors commented Sep 24, 2022

bors commented Sep 24, 2022

rust-timer commented Sep 24, 2022

Overall result: ✅ improvements - no action needed

Footnotes

klensy commented Sep 24, 2022

Use internal iteration in `Iterator` comparison methods #100845

Use internal iteration in `Iterator` comparison methods #100845

scottmcm commented Sep 24, 2022 •

edited

Loading