我如何使用 Rayon 将大范围拆分为多个范围块，并让每个线程在一个块中找到？

Question

我正在制作一个通过并行化强制密码的程序。目前破解密码已经可以明文获取，我只是尝试暴力破解而已。

我有一个名为 generate_char_array() 的函数，它基于整数种子将基数和 returns 转换为 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"）要短得多，因此我得到的是第一个线程完成所有工作，其余线程只是浪费时间测试太长的密码和同步；结果实际上比单线程性能慢。

我怎么能而不是拆分任意大范围（不必实际上有一个结束）到范围的块 并且让每个线程在块中找到？这将使不同线程中的工作人员真正有用。

Answer 1

这是我在评论中建议的版本。

主循环是并行的，并且只在每次尝试的第一个字节上。对于每个第一个字节，对其余字节进行完整的蛮力搜索。

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

此外，即使对于暴力方法，这可能仍然非常低效！

Answer 2

This goes through the alphabet first for 1 character strings, then 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);
}

这可以 "waste" 在每个长度的末尾花费一点时间，因为并行线程在旋转回升到下一个长度之前一个接一个地向下旋转，但这似乎不太可能成为主要问题.

Answer 3

如果 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值取决于CPU数量（Rayon使用的线程数），在你的情况下：

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

注意这种方法的性能在很大程度上取决于 Rayon 如何在并行线程上执行序列拆分。验证它是否像您在问题中报告的那样工作。

我如何使用 Rayon 将大范围拆分为多个范围块，并让每个线程在一个块中找到？

How can I use Rayon to split a big range into chunks of ranges and have each thread find within a chunk?

multithreading

rust

rayon