Fixed-size lazy iterators?

1

Once we have Const Generics is it useful to add an Iterator method like this?

fn take_ct<const n: usize>(self) -> TakeCT<Self, n>

(CT = compile-time). TakeCT is meant to be a fixed-size lazy iterator, like a lazy version of [Self; N]. Fixed-size iterators could lead to optimizations similar to the ones allowed by fixed-size arrays (like loop unrolling, removal the equivalent of bound tests, etc).

If you have a function that returns lazily the binary digits of a number of type T you can return something like:

impl SizedIterator<Item=bool, size_of::<T>() * 8>

1 Like
2

If we want to use the standard traits Iterator and IntoIterator, only the latter can be of a compile time constant size. Because it is in the trait of an Iterator that it can change the number of remaining elements in its sequence with the next method.

If the iterator itself should have a compile time constant size, what does its trait look like? Just intended as an open question, below is a doodle that is not complete:

trait CgIterator<const n: usize> {
    type Item;
    type Next: CgIterator<n - 1, Item = Self::Item>;   // ← not sure how this terminates at zero
    fn next(self) -> Option<(Self::Item, Self::Next)>;
}
3

Regarding termination, how about this?

trait CSIterator<const N: usize> {
    type Item;
    type Next: CSIterator<N.saturating_sub(1), Item = Self::Item>;
    fn next(self) -> Option<(Self::Item, Self::Next)>;
}
4

I did some more thinking and came up with the following:

// Machinery for type level if->0-then-else
// It is a bit unfortunate that we need all this boilerplate.
struct Nat<const N: usize>(PhantomData<[(); N]>);
trait IfSuccFn<S, Z> { type Out; }
// If Succ(N) => S
impl<const N: usize, S, Z> IfSuccFn<S, Z> for Nat<{N + 1}> { type Out = S; }
// If 0 => Z
impl<S, Z> IfSuccFn<S, Z> for Nat<{0}> { type Out = Z; }
// if N > 0 then S, else Z.
type IfSucc<const N: usize, S, Z> = <Nat<N> as IfSucc<S, Z>>::Out;

trait CSIterator<const N: usize> {
    type Item;
    type Next: CSIterator<{ N.saturating_sub(1) }, Item = Self::Item>;
    fn next(self) -> (IfSucc<N, Self::Item, ()>, Self::Next);
}

fn foreach<Iter: CSIterator<N>, F: FnMut(Iter::Item), const N>(iter: Iter, fun: F) {
    if N > 0 {
        let (item, next) = iter.next();
        fun(item);
        foreach(next);
    }
}

The main benefit of this encoding (assuming it actually type checks) is that we are not involving Option at all.

EDIT: Improving readability of the encoding a bit:

// Machinery for type level if-then-else
struct Test<const B: bool>(PhantomData<[(); B as usize]>);
trait IfFn<S, Z> { type Out; }
impl<S, Z> IfFn<S, Z> for Test<{true }> { type Out = S; }
impl<S, Z> IfFn<S, Z> for Test<{false}> { type Out = Z; }

// if B then S, else Z.
type If<const B: bool, S, Z> = <Test<B> as IfFn<S, Z>>::Out;

trait CSIterator<const N: usize> {
    type Item;
    type Next: CSIterator<{ N.saturating_sub(1) }, Item = Self::Item>;
    fn next(self) -> (If<{N == 0}, (), Self::Item>, Self::Next);
}

Ideally, you would really want to write:

trait CSIterator<const N: usize> {
    type Item;
    type Next: CSIterator<{ N.saturating_sub(1) }, Item = Self::Item>;
    fn next(self) -> (if N == 0 { () } else { Self::Item }, Self::Next);
}

and that’s it.

5

That’s neat. I wonder if we can regain an interface that is at least similar to how a regular iterator is using adaptors and is called. I guess the consume/loop part will always be different, because the next method has to consume the iterator value.

1 Like
6

Isn’t this just forced loop unrolling and be counterproductive to performance for large n?

@leonardo: Could you help me understand what’s preventing those optimizations from happening on a regular .take(8)? Presumably it would be inlined already and make the compiler time constant visible to the compiler?

7

For me the beauty is not the perf but the added correctness constraints; Ideally, there would be some way to avoid monomorphization when you want to, but that is tricky.

8

Could you elaborate on what additional checks this helps you provide that you’re not otherwise getting? This is replacing already easy-to-understand type-safe code that works with both variables and constants. Is the only additional constraint that were enforcing the use of compile-time constants?

@leonardo primarily mentioned optimizations as the benefit, which is why I asked for some insights as to why they wouldn’t already happen.

9

Unlike things like TrustedLen, this enforces the length of each iterator statically (and .next() can't lie and must return an element until there are no more elements left), and so you can for example ensure statically that Chain<A, B> has length = length(A) + length(B) or that Map<I> does not alter the length and returns just as many elements as I does.

That said, I'm not sure this traits belongs in libstd; and should fully bake before we consider adding it there -- I suspect we are a long way from that.

10

FWIW, I proposed a const for the size of an IntoIterator, but it wasn't desired at this time:

11

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.