ParallelIterator for Itertools Product

I'm looking to create the Cartesian product of two iterators. I found that itertools has a method to do exactly this: it1.iter().cartesian_product(it2.iter()). However, now I'd like a ParallelIterator of the result so that I can work on the resulting Cartesian product in parallel. Simply calling .par_iter() results in (some types removed for brevity):

error[E0599]: no method named `par_iter` found for type `itertools::Product<...>` in the current scope
   --> src/program.rs:966:90
    |
966 |                     it1.iter().cartesian_product(it2.iter()).par_iter();
    |                                                                                  ^^^^^^^^
    |
    = note: the method `par_iter` exists but the following trait bounds were not satisfied:
            `itertools::Product<...> : rayon::iter::IntoParallelRefIterator`

I'm assuming that I need to implement the trait IntoParallelRefIterator for the struct Product, but I'm struggling on how to do that. Also, I want to double-check that I'm correct in that I need to provide this implementation. I would have thought the generic version provide in the Rayon library (below) would work... why doesn't it?

impl<'data, I: 'data + ?Sized> IntoParallelRefIterator<'data> for I
where
    &'data I: IntoParallelIterator,
{
    type Iter = <&'data I as IntoParallelIterator>::Iter;
    type Item = <&'data I as IntoParallelIterator>::Item;

    fn par_iter(&'data self) -> Self::Iter {
        self.into_par_iter()
    }
}

You can't implement rayon::IntoParallelIterator for itertools::Product for a number of reasons:

  • The compiler won't let you, as it would this run afoul of the orphan impl rules.
  • The fields of Product are private.
  • Even if they were public, they're not ParallelIterators. They are serial Iterators.

You will need to write your own Product type that contains ParallelIterators and implements ParallelIterator. Maybe it could be added upstream to rayon so all can benefit.

Or more likely, you want to look at rayon::ParallelBridge as the simplest solution.


That impl requires &Product to implement IntoParallelIterator, which it doesn't. (neither itertools nor rayon depends on the other, so neither could write the impl).

1 Like

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