about summary refs log tree commit diff
diff options
context:
space:
mode:
authorBjörn Steinbrink <bsteinbr@gmail.com>2015-02-03 16:54:06 +0100
committerBjörn Steinbrink <bsteinbr@gmail.com>2015-02-03 16:54:06 +0100
commit9a17f62947d0c079f1c877de4fe1dab5b2c500d9 (patch)
treec173d432fbc6cd1158f504cf69794ba45e545930
parent3d072a193bfcb76206aab576049e696d6d8db25d (diff)
Optimize rposition
The extra check caused by the expect() call can, in general, not be
optimized away, because the length of the iterator is unknown at compile
time, causing a noticable slow-down. Since the check only triggers if
the element isn't actually found in the iterator, i.e. it isn't
guaranteed to trigger for ill-behaved ExactSizeIterators, it seems
reasonable to switch to an implementation that doesn't need the check
and just always returns None if the value isn't found.

Benchmark:
````rust
let v: Vec<u8> = (0..1024*65).map(|_| 0).collect();
b.iter(|| {
    v.as_slice().iter().rposition(|&c| c == 1)
});
````

Before:
````
test rposition  ... bench:     49939 ns/iter (+/- 23)
````

After:
````
test rposition  ... bench:     33306 ns/iter (+/- 68)
````
-rw-r--r--src/libcore/iter.rs7
1 files changed, 4 insertions, 3 deletions
diff --git a/src/libcore/iter.rs b/src/libcore/iter.rs
index d0734f9c039..417bcab5140 100644
--- a/src/libcore/iter.rs
+++ b/src/libcore/iter.rs
@@ -723,11 +723,12 @@ pub trait IteratorExt: Iterator + Sized {
         P: FnMut(Self::Item) -> bool,
         Self: ExactSizeIterator + DoubleEndedIterator
     {
-        let len = self.len();
-        for i in (0..len).rev() {
-            if predicate(self.next_back().expect("rposition: incorrect ExactSizeIterator")) {
+        let mut i = self.len() - 1;
+        while let Some(v) = self.next_back() {
+            if predicate(v) {
                 return Some(i);
             }
+            i -= 1;
         }
         None
     }