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

Question

我正在制作一个通过并行化暴力破解密码的程序。目前，要破解的密码已经以纯文本形式提供，无论如何我只是试图暴力破解它。

我有一个名为generate_char_array()的函数，它基于整数种子转换 base 并返回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

这首先通过字母表以获得 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);
}

这可能会在每个长度的末尾"浪费"一点时间，因为并行线程在旋转到下一个长度之前一个接一个地旋转，但这似乎不太可能是主要问题。

Answer 2

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

主循环是并行的，并且仅在每次尝试的第一个字节上。对于每个第一个字节，对余数执行完整的暴力搜索。

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 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 的数量(人造丝使用的线程数(，在您的情况下：

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

请注意，此方法的性能高度依赖于 Rayon 在并行线程上执行序列拆分的方式。验证它是否与您在问题中报告的那样工作。