Rust - using Rayon for permutations - vector memory allocation error

Question

Aim: generate several billion permutations and run code on each one in parallel.

Attempt: use Itertools to assign all permutations to a resulting vector and then use rayon to process each one.

Minimum reproducible code:

use rayon::iter::ParallelIterator;
use rayon::iter::IntoParallelIterator;
use itertools::Itertools;

fn main() {
    let data: Vec<u128> = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19].to_vec();
    let k = 8;
    let vector: Vec<Vec<u128>>

    //Following code should return 29.6 billion permutations
    let _vector = data.into_iter().permutations(k).map_into::<Vec<u128>> 
    ().collect_vec();

    //Following code then processes each permutation using rayon crate
    (vector).into_par_iter().for_each(move |x| further_processing(x));
}

When the data input vector is 16 elements or less the code runs. For 24 elements the following error returns: memory allocation of 121898649600 bytes failed error: process didn't exit successfully: target\debug\threads.exe (exit code: 0xc0000409, STATUS_STACK_BUFFER_OVERRUN)

Not using the rayon crate works with 24 elements, but is very slow - this code replaces the last two lines with: data.into_iter().permutations(k).for_each(move |x| further_processing(x));

So the problem appears to be memory allocation for a very large, growing permutations vector that rayon can then access.

Is there a way to either successfully generate this very large permutation set for rayon to access, a smarter way to use rayon directly on the input data, or a more suitable parallel-computing approach to this problem?

Answer 1

I can't seem to find any parallel permutation implementations, so your best bet is probably to use ParallelBridge to convert the iterator into a parallel one. Note that, unless your processing is intensive, you shouldn't use this and just use regular iterator methods instead because there's an added synchronization cost.

use rayon::iter::ParallelIterator;
use rayon::iter::ParallelBridge;
use itertools::Itertools;

fn main() {
    let data: Vec<u128> = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19].to_vec();
    let k = 8;

    let data_iter = data.into_iter().permutations(k);

    data_iter.par_bridge().for_each(move |x| further_processing(x));
}