Make Stride use RandomAccessIterators

[rust-itertools]

Make Stride use RandomAccessIterators

[bluss]

Thanks, I see the same thing, also after adding some uses of test::black_box (didn't change bench results).

It mustn't be too surprising since the current Stride is unfortunately using two comparisons per iteration -- comparing begin to NULL and begin to end. A smart enough compiler should see that begin will never be NULL until it has first been equal to end.., but that doesn't happen.

I'm not sure about the best way to fix it. I'm using Stride from pointers, not from a slice or slice iterator, so I'd prefer an independent Stride iterator. Maybe element counting is simpler and faster.

[bluss]

Here is a diff that does in fact increase the performance of Stride, but it doesn't catch up fully.

diff --git a/src/stride.rs b/src/stride.rs
index dd4bd84..78afe39 100644
--- a/src/stride.rs
+++ b/src/stride.rs
@@ -195,19 +195,23 @@ macro_rules! stride_iterator {
             #[inline]
             fn next(&mut self) -> Option<$elem>
             {
-                if self.begin.is_null() {
-                    None
-                } else {
-                    unsafe {
-                        let elt: $elem = mem::transmute(self.begin);
-                        if self.begin == self.end {
+                if self.begin == self.end {
+                    if !self.begin.is_null() {
+                        unsafe {
+                            let elt: $elem = mem::transmute(self.begin);
                             self.begin = RawPtr::null();
-                        } else {
-                            self.begin = self.begin.offset(self.stride);
+                            self.end = RawPtr::null();
+                            return Some(elt);
                         }
-                        Some(elt)
+                    } else {
+                        return None;
                     }
                 }
+                unsafe {
+                    let elt: $elem = mem::transmute(self.begin);
+                    self.begin = self.begin.offset(self.stride);
+                    Some(elt)
+                }
             }

             fn size_hint(&self) -> (uint, Option<uint>)

[awelkie]

If the Stride struct uses a RandomAccessIterator, then we can just make a struct that iterates over pointers and implements RandomAccessIterator, and have the Stride iterate over that struct. That way, the RandomAccessIterator-based Stride struct will be able to work on raw pointers (like the current Stride struct does), as well as other types of iterators that don't operate on contiguous memory (like Counter) that the current Stride can't handle. And, since it's not incurring a performance penalty, it seems like a complete win.

[bluss]

The method sounds reasonable, but I'm sceptical of the RandomAccessIterator (RAI) trait; it is experimental. It also is not compatible with &mut A iterator elements, because that would make it trivial to duplicate mut pointers.

[bluss]

I've updated now Stride to use integers, similar to your impl, and it performs better (probably because the .next() method itself is much smaller / simipler now).

A strider over RAI could be a separate addition.

[bluss]

Please file a PR if a RAI solution is created.