CODEWITHSUNDEEP
rustrayon
Daniel Giger
Daniel Giger

Reputation: 2533

Why does filter() have different type requirements on parallel iterators?

I'm trying to understand why Rayon's filter() function won't work without needing to specify the right type, whereas filter() will work correctly if I'm not using a parallel iterator. Here's my code:

use rayon::prelude::*;

fn is_even(n: i64) -> bool {
    n % 2 == 0
}

fn main() {
    let v: Vec<_> = (1..300_000_000)
        .into_par_iter()  //  works correctly without this line, but not parallel
        .filter(|&x| is_even(x))
        .collect();
}

And here are the error messages:

error[E0271]: type mismatch resolving `<rayon::range::Iter<i32> as rayon::iter::ParallelIterator>::Item == i64`
  --> src/main.rs:11:10
   |
11 |         .filter(|&x| is_even(x))
   |          ^^^^^^ expected `i32`, found `i64`

error[E0271]: type mismatch resolving `<rayon::range::Iter<i32> as rayon::iter::ParallelIterator>::Item == i64`
  --> src/main.rs:12:10
   |
12 |         .collect();
   |          ^^^^^^^ expected `i32`, found `i64`
   |
   = note: required because of the requirements on the impl of `rayon::iter::ParallelIterator` for `rayon::iter::Filter<rayon::range::Iter<i32>, [closure@src/main.rs:11:17: 11:32]>`

Why does filter() only work without specifying the kind of integer if I'm not using into_par_iter()? (I know I can fix it by labeling the range as i64, but not why it would be necessary)

Upvotes: 3

Views: 549

Answers (1)

kmdreko
kmdreko

Reputation: 59882

Update: This type inference issue has been fixed in rayon 1.5.1

Why indeed... Digging into it, this is due to the way rayon determines if a Range implements IntoParallelIterator.

impl<T> IntoParallelIterator for Range<T> where Iter<T>: ParallelIterator { ... }

struct Iter<T> {
    range: Range<T>,
}

impl ParallelIterator for Iter<u8> { type Item = u8; }
impl ParallelIterator for Iter<u16> { type Item = u16; }
impl ParallelIterator for Iter<u32> { type Item = u32; }
impl ParallelIterator for Iter<u64> { type Item = u64; }
impl ParallelIterator for Iter<i8> { type Item = i8; }
impl ParallelIterator for Iter<i16> { type Item = i16; }
impl ParallelIterator for Iter<i32> { type Item = i32; }
impl ParallelIterator for Iter<i64> { type Item = i64; }
// etc

The compiler is trying to see if (1..300_000_000).into_par_iter() is even legal and because ParallelIterator is implemented for the Iter<T> types separately, its forced to deduce now what T is before it proceeds.

See the non-working reconstruction on the playground.

If instead they did something like:

impl<T> ParallelIterator for Iter<T> where T: SomeIntegerType + Send {
    type Item = T;
}

trait SomeIntegerType {}
impl SomeIntegerType for u8 {}
impl SomeIntegerType for u16 {}
impl SomeIntegerType for u32 {}
impl SomeIntegerType for u64 {}
impl SomeIntegerType for i8 {}
impl SomeIntegerType for i16 {}
impl SomeIntegerType for i32 {}
impl SomeIntegerType for i64 {}
// etc

The compiler can see that Iter does implement ParallelIterator as long as T implements SomeIntegerType, but it doesn't have to deduce the type now, it can wait until later.

See my working reconstruction on the playground.

Upvotes: 4

Related Questions