Iterator speed about bitvec HOT 2 CLOSED

I am reluctant, but not unwilling, to add a nightly feature gate, but it would receive less maintenance than the stable items.

A double-pointer iterator is something I've been vaguely contemplating since seeing its use in the [T] iterators. It can be represented as follows:

#[repr(C)]
struct Iter<O: BitOrder, T: BitStore> {
  //  address of the base element
  front: *const T,
  //  address of the element containing the tail marker
  back: *const T,
  //  semantic count of the first live bit
  head: BitIdx<T::Mem>,
  //  semantic count of the first dead bit
  tail: BitTail<T::Mem>,
}

This is easy to construct from a BitPtr<T>:

impl<T: BitStore> BitPtr<T> {
  fn to_iter(self) -> Iter<T> {
    let (base, head, bits) = self.raw_parts();
    let (elts, tail) = head.span(bits);
    Iter {
      front: base,
      back: base.offset(elts),
      head,
      tail,
    }
  }
}

I'll need to come up with a good way to test whether the (*const T, BitIdx<T::Mem>) bit pointer has reached the (*const T, BitTail<T::Mem> tail marker in order to handle termination, but access to memory is just BitAccess::get(&*(front as *const T::Access), head) or construction of a BitMut<T> from (front, head, 1). Pretty straightforward.

from bitvec.

Version 0.18 uses double-pointer iteration, and demonstrates non-trivial acceleration. Thank you for the suggestion, and your work earlier this year! It's really helped me improve the library.

from bitvec.