[Enhancement] Implement ParallelIterator trait for Windows

[rkshthrmsh]

Implementing the ParallelIterator trait for Windows might be quit helpful in accelerating usecases such as convolution and correlation over large ndarrays. Please let me know if you have considered this already and found some issues in implementing.

Here is an example:

    let a = arr
        .windows((3, 3))
        .into_par_iter()
        .map(|w| (&w * &kernel).sum())
        .collect::<Array1<f32>>();

[bluss]

Windows is a producer (NdProducer trait) so it can already be parallelized using Zip

[rkshthrmsh]

Hi @bluss, would this be the right way of doing it with Zip?

    let a = Array::from_vec(
        Zip::from(arr.windows((3, 3)))
            .into_par_iter()
            .map(|w| (&w.0 * &corner_kernel).sum()) // using tuple indexing to get the 3x3 ArrayView
            .collect::<Vec<f32>>(),
    );

Thank you!

[rkshthrmsh]

Destructuring in the closure definition to get the window seems more readable:

    let a = Array::from_vec(
        Zip::from(arr.windows((3, 3)))
            .into_par_iter()
            .map(|(w,)| (&w * &corner_kernel).sum()) // changed |w| to |(w,)|
            .collect::<Vec<f32>>(),
    );

[bluss]

Also possible I think:

let a = Zip::from(arr.windows((3, 3)))
  .par_map_collect(|(w, )| (&w * &corner_kernel).sum());

But par_map_collect makes an array the same size as the producer coming in. Maybe not what you want, but interesting to know about..

I'm a bit concerned about the into par iter collect since it does not have any guarantee about what order the elements end up.

But yes, is Zip enough or should it be a parallel iterator by itself? Try and see

[rkshthrmsh]

• into_par_iter did not change the ordering of elements. This is based on visual inspection, so take it with a pinch of salt.
• par_map_collect produced a 2-D array but of shape two lesser than the original along both axis. This seems logical because of the shape of the window. Moreover, I did not need to destructure w, so the code was more readable.
• In terms of performance, both were roughly the same.

[bluss]

Right, the ordering might be correct for some cases but it is not guaranteed and depends on memory order of the array, I think.

[bluss]

In general, thinking about the operation, it is flattening a 2D space to a 1D sequence without specifying an indexing order and that will always be fraught.

The Zip-related API at least avoids this but has no explicit flattening operation. This might be underdescribed in the docs but the assumption is that parallel iterators are allowed to execute in any order for efficency (memory locality). 1D producers like axis iter are indexed (IndexedParallelIterator) and do not have this quirk.

[nilgoyette]

@rkshthrmsh If you care about performance, you might want to rewrite

(&w * &corner_kernel).sum()

to avoid allocating. Using Zip::fold will work. It will be uglier but it won't allocate anything.