Rust - использование Rayon для перестановок - ошибка выделения векторной памяти

Цель: сгенерировать несколько миллиардов перестановок и запустить код для каждой из них параллельно.

Попытка: используйте Itertools, чтобы назначить все перестановки результирующему вектору, а затем используйте rayon для обработки каждой из них.

Минимальный воспроизводимый код:

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));
}

Когда входной вектор data содержит 16 элементов или меньше, код запускается. Для 24 элементов возвращается следующая ошибка: memory allocation of 121898649600 bytes failed error: process didn't exit successfully: target\debug\threads.exe (exit code: 0xc0000409, STATUS_STACK_BUFFER_OVERRUN)

Без использования ящика вискозы работает с 24 элементами, но очень медленно — этот код заменяет последние две строки на: data.into_iter().permutations(k).for_each(move |x| further_processing(x));

Таким образом, проблема заключается в выделении памяти для очень большого растущего вектора перестановок, к которому затем может получить доступ rayon.

Есть ли способ либо успешно сгенерировать этот очень большой набор перестановок для доступа к rayon, либо более разумный способ использовать rayon непосредственно во входных данных, либо более подходящий подход параллельных вычислений к этой проблеме?


memory rust large-data permutation rayon
person Isambard_FA    schedule 10.03.2021    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Кажется, я не могу найти никаких параллельных реализаций перестановок, поэтому лучше всего использовать ParallelBridge, чтобы преобразовать итератор в параллельный. Обратите внимание, что если ваша обработка не является интенсивной, вы не должны использовать это, а вместо этого просто используйте обычные методы итератора, потому что есть дополнительные затраты на синхронизацию.

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));
}
person Aplet123    schedule 10.03.2021
comment
Спасибо за это понимание @Aplet123 высоко ценится. - person Isambard_FA; 10.03.2021