Auto merge of #137122 - yotamofek:pr/std/iter-eq-exact-size, r=the8472

Specialize `Iterator::eq{_by}` for `TrustedLen` iterators

I'm sure I got some stuff wrong here, but opening this to get feedback and make sure it's a viable idea at all.

### Motivation
I had a piece of code that open-coded `Iterator::eq`, something like:
```rust
if current.len() != other.len()
    || current.iter().zip(other.iter()).any(|(a, b)| a != b) { ... }
```
... where both `current` and `other` are slices of the same type.
Changing the code to use `current.iter().eq(other)` made it a lot slower, since it wasn't checking the length of the two slices beforehand anymore, which in this instance made a big difference in perf. So I thought I'd see if I can improve `Iterator::eq`.

### Questions
1. I can't specialize for `ExactSizeIterator`, I think it's a limitation of `min_specialization` but not sure exactly why. Is specializing for `TrustedLen` good enough?
2. Should I make a codegen test for this? If so, then how? (I manually checked the assembly to make sure it works as expected)
3. Where should I put `SpecIterCompare`?
4. Can I get a perf run for this, please? I think the compiler uses this in a few places, so it might have an affect.

1 files changed, 48 insertions, 4 deletions

diff --git a/library/core/src/iter/traits/iterator.rs b/library/core/src/iter/traits/iterator.rs
index 7fb162a653f..695f8d1e195 100644
--- a/library/core/src/iter/traits/iterator.rs
+++ b/library/core/src/iter/traits/iterator.rs
@@ -4,6 +4,7 @@ use super::super::{
     Product, Rev, Scan, Skip, SkipWhile, StepBy, Sum, Take, TakeWhile, TrustedRandomAccessNoCoerce,
     Zip, try_process,
 };
+use super::TrustedLen;
 use crate::array;
 use crate::cmp::{self, Ordering};
 use crate::num::NonZero;
@@ -3816,10 +3817,7 @@ pub trait Iterator {
             }
         }
 
-        match iter_compare(self, other.into_iter(), compare(eq)) {
-            ControlFlow::Continue(ord) => ord == Ordering::Equal,
-            ControlFlow::Break(()) => false,
-        }
+        SpecIterEq::spec_iter_eq(self, other.into_iter(), compare(eq))
     }
 
     /// Determines if the elements of this [`Iterator`] are not equal to those of
@@ -4038,6 +4036,42 @@ pub trait Iterator {
     }
 }
 
+trait SpecIterEq<B: Iterator>: Iterator {
+    fn spec_iter_eq<F>(self, b: B, f: F) -> bool
+    where
+        F: FnMut(Self::Item, <B as Iterator>::Item) -> ControlFlow<()>;
+}
+
+impl<A: Iterator, B: Iterator> SpecIterEq<B> for A {
+    #[inline]
+    default fn spec_iter_eq<F>(self, b: B, f: F) -> bool
+    where
+        F: FnMut(Self::Item, <B as Iterator>::Item) -> ControlFlow<()>,
+    {
+        iter_eq(self, b, f)
+    }
+}
+
+impl<A: Iterator + TrustedLen, B: Iterator + TrustedLen> SpecIterEq<B> for A {
+    #[inline]
+    fn spec_iter_eq<F>(self, b: B, f: F) -> bool
+    where
+        F: FnMut(Self::Item, <B as Iterator>::Item) -> ControlFlow<()>,
+    {
+        // we *can't* short-circuit if:
+        match (self.size_hint(), b.size_hint()) {
+            // ... both iterators have the same length
+            ((_, Some(a)), (_, Some(b))) if a == b => {}
+            // ... or both of them are longer than `usize::MAX` (i.e. have an unknown length).
+            ((_, None), (_, None)) => {}
+            // otherwise, we can ascertain that they are unequal without actually comparing items
+            _ => return false,
+        }
+
+        iter_eq(self, b, f)
+    }
+}
+
 /// Compares two iterators element-wise using the given function.
 ///
 /// If `ControlFlow::Continue(())` is returned from the function, the comparison moves on to the next
@@ -4078,6 +4112,16 @@ where
     }
 }
 
+#[inline]
+fn iter_eq<A, B, F>(a: A, b: B, f: F) -> bool
+where
+    A: Iterator,
+    B: Iterator,
+    F: FnMut(A::Item, B::Item) -> ControlFlow<()>,
+{
+    iter_compare(a, b, f).continue_value().is_some_and(|ord| ord == Ordering::Equal)
+}
+
 /// Implements `Iterator` for mutable references to iterators, such as those produced by [`Iterator::by_ref`].
 ///
 /// This implementation passes all method calls on to the original iterator.