Composed Iterators compile slowly

1

I'm playing around with iterators and wrote this code:

fn ident<T>(x:T) -> T {x}

fn mult(x:&u64, y:&u64) -> u64 { 
    x * y
}

fn add(x: &u64, y: &u64) -> u64 {
    x + y
}

pub fn hourglass() -> u64 {
    let cells = vec![2;64];
    let nodes64 = cells.iter().map(|x| ident(*x));
    let nodes32 = nodes64.take(32).zip(nodes64.skip(32)).map(
        |(x,y)| mult(&x, &y)
    );
    let nodes16 = nodes32.take(16).zip(nodes32.skip(16)).map(
        |(x,y)| add(&x, &y)
    );
    let nodes8 = nodes16.take(8).zip(nodes16.skip(8)).map(
        |(x,y)| mult(&x, &y)
    );
    let nodes4 = nodes8.take(4).zip(nodes8.skip(4)).map(
        |(x,y)| add(&x, &y)
    );
    let nodes2 = nodes4.take(2).zip(nodes4.skip(2)).map(
        |(x,y)| mult(&x, &y)
    );
    let chokepoint = nodes2.take(1).zip(nodes2.skip(1)).map(
        |(x,y)| add(&x, &y)
    );
    // chokepoint[0] // error: cannot index a value of type `[12 thousand characters]`

    match chokepoint.next() {
        None => 2, //impossible
        Some(a) => a
    }
}

fn main() {
    // hourglass() // error mismatched types, after checking all the above

    println!("result is: {}",hourglass());
}

It takes up to 40 minutes to compile before failing at the borrow checker. I've commented two errors that will show up in the type checker. The one in main should be a simple check, since hourglass is declared as returning a value, while main cannot. The previous error prints out a 12 thousand character type for chokepoint.

I'd love to actually run this to see if most of it compiles away and it runs fast, but I don't know enough to satisfy the borrow checker while taking so long between compile iterations.

Is this expected behavior?

2

If I get that right, chokepoint is not a Vec, nor an array. It is the Rust equivalent to a python generator, that is why you cannot index it.

The thousand character type is, because it is some kind of procedurally changed list of values, that is generated, element by element, when you call next(). To produce these elements it has to save what it has to do to get them. Which reflects in it's type.

However, I don't think that was the answer you were looking for, and I have zero understanding of the compilation itself.

I wish you good luck finding that out.

3

So I looked into this and seems like it's a combination of things:

  1. Hitting some poor performance behaviour in the type checker. Looks like the type inference engine has hit some polynomial-time operation and your code is producing a large number of type variables for it to chug through.
  2. Building error messages. The code doesn't compile, for a number of reasons, and the type in the error message is incredibly long, chances are it's spending quite a while just building error messages.

I understand that you are merely experimenting with iterators, but what you are trying to do here is not really a good use case for iterators. You'd be better off using a Vec and split_at (or split_at_mut and mutating one of the slices).

The working version of the code runs fast, even unoptimised, so it's just a compile-time thing.

4

@KyleHeadley I don't know how you formatted your post, but I suggest using triple backticks (```), then you will have proper syntax highlighting.

Edit: more detailed over there.

5