Как я могу использовать Rayon, чтобы разбить большой диапазон на куски диапазонов, и чтобы каждый поток находился внутри него? - PullRequest
Новая
       25

Как я могу использовать Rayon, чтобы разбить большой диапазон на куски диапазонов, и чтобы каждый поток находился внутри него?

0 голосов
/ 10 мая 2018

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

У меня есть функция с именем generate_char_array(), которая на основе целочисленного начального числа преобразует основную ивозвращает u8 кусок символов, чтобы попробовать и проверить.Сначала идет алфавит для 1 строки символов, затем 2 и т. Д. 

let found_string_index = (0..1e12 as u64).into_par_iter().find_any(|i| {
    let mut array = [0u8; 20];
    let bytes = generate_char_array(*i, &mut array);
    return &password_bytes == &bytes;
});

С помощью индекса найденной строки (или, скорее, целого числа) я могу сгенерировать найденную строку.

Проблема в том, что способ, которым Rayon распараллеливает это для меня, разбивает произвольный большой целочисленный диапазон на thread_count -большие срезы (например, для 4 потоков, 0..2.5e11, 2.5e11..5e11 и т. Д.).Это нехорошо, потому что конец диапазона предназначен для произвольно сверхбольших паролей (10+, я не знаю), тогда как большинство паролей (включая фиксированный "zzzzz", который я стараюсь) намного короче, и поэтомучто я получаю, так это то, что первый поток выполняет всю работу, а остальные потоки просто тратят время на проверку слишком длинных паролей и синхронизации;в результате получается производительность на самом деле ниже, чем у одного потока.

Как я мог вместо разделить произвольный большой диапазон (не долженна самом деле есть конец) на куски диапазонов и каждый поток находится внутри кусков?Это сделало бы рабочих из разных потоков действительно полезными.

Ответы [ 3 ]

0 голосов
/ 10 мая 2018

Сначала идет алфавит для 1 строки символов, затем 2

Вы хотите наложить некоторую последовательность на обработку ваших данных, но весь смысл Rayon - идти параллельно.

Вместо этого используйте регулярные итераторы для последовательного увеличения длины, а затем используйте параллельные итераторы внутри определенной длины для быстрой обработки всех значений этой длины.

Поскольку вы не предоставили достаточно кода для работающего примера, я сделал это приблизительное приближение, чтобы показать общую форму такого решения: 

extern crate rayon;

use rayon::iter::{IntoParallelRefIterator, ParallelIterator};
use std::ops::RangeInclusive;

type Seed = u8;

const LENGTHS: RangeInclusive<usize> = 1..=3;
const SEEDS: RangeInclusive<Seed> = 0..=std::u8::MAX;

fn find<F>(test_password: F) -> Option<(usize, Seed)>
where
    F: Fn(usize, Seed) -> bool + Sync,
{
    // Rayon doesn't support RangeInclusive yet
    let seeds: Vec<_> = SEEDS.collect();

    // Step 1-by-1 through the lengths, sequentially
    LENGTHS.flat_map(|length| {
        // In parallel, investigate every value in this length
        // This doesn't do that, but it shows how the parallelization
        // would be introduced
        seeds
            .par_iter()
            .find_any(|&&seed| test_password(length, seed))
            .map(|&seed| (length, seed))
    }).next()
}

fn main() {
    let pass = find(|l, s| {
        println!("{}, {}", l, s);
        // Actually generate and check the password based on the search criteria
        l == 3 && s == 250
    });

    println!("Found password length and seed: {:?}", pass);
}

Это может «тратить» немного времени в конце каждой длины, поскольку параллельные нити вращаются один за другим, а затем снова вращаются вверх для следующей длины, но это вряд ли является основной проблемой.

0 голосов
/ 11 мая 2018

Если Rayon разбивает ломтики, как вы описали, тогда примените простую математику, чтобы сбалансировать длину пароля: 

let found_string_index = (0..max_val as u64).into_par_iter().find_any(|i| {
    let mut array = [0u8; 20];
    let v = i/span + (i%span) * num_cpu;

    let bytes = generate_char_array(*v, &mut array);
    return &password_bytes == &bytes;
});

Значение span зависит от количества процессоров (количество потоков, используемых Rayon), в вашем случае: 

let num_cpu = 4;
let span = 2.5e11 as u64;
let max_val = span * num_cpu;

Примечание производительность этого подхода сильно зависит от того, как Rayon выполняет разбиение последовательности на параллельные потоки. Убедитесь, что это работает, как вы сообщили в вопросе.

0 голосов
/ 10 мая 2018

Это версия того, что я предложил в своем комментарии.

Основной цикл является параллельным и занимает только первый байт каждой попытки.Для каждого первого байта выполните поиск полной грубой силы для остатка. 

let matched_bytes = (0 .. 0xFFu8).into_par_iter().filter_map(|n| {
    let mut array = [0u8; 8];
    // the first digit is always the same in this run
    array[0] = n;
    // The highest byte is 0 because it's provided from the outer loop
    (0 ..= 0x0FFFFFFFFFFFFFFF as u64).into_iter().filter_map(|i| {
        // pass a slice so that the first byte is not affected
        generate_char_array(i, &mut array[1 .. 8]);
        if &password_bytes[..] == &array[0 .. password_bytes.len()] {
            Some(array.clone())
        } else {
            None
        }
    }).next()
}).find_any(|_| true);

println!("found = {:?}", matched_bytes);

Кроме того, даже для метода грубой силы это, вероятно, все еще крайне неэффективно!

...