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

Question

I am making a program that brute forces a password by parallelization. At the moment the password to crack is already available as plain text, I'm just attempting to brute force it anyway.

I have a function called generate_char_array() which, based on an integer seed, converts base and returns a u8 slice of characters to try and check. This goes through the alphabet first for 1 character strings, then 2, etc.

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

With the found string index (or seed integer rather), I can generate the found string.

The problem is that the way Rayon parallelizes this for me is split the arbitrary large integer range into thread_count-large slices (e.g. for 4 threads, 0..2.5e11, 2.5e11..5e11 etc). This is not good, because the end of the range is for arbitrarily super large password lengths (10+, I don't know), whereas most passwords (including the fixed "zzzzz" I tend to try) are much shorter, and thus what I get is that the first thread does all the work, and the rest of the threads just waste time testing way too long passwords and synchronizing; getting actually slower than single thread performance as a result.

How could I instead split the arbitrary big range (doesn't have to have an end actually) into chunks of ranges and have each thread find within chunks? That would make the workers in different threads actually useful.

Answer 1

This goes through the alphabet first for 1 character strings, then 2

You wish to impose some sequencing on your data processing, but the whole point of Rayon is to go in parallel.

Instead, use regular iterators to sequentially go up in length and then use parallel iterators inside a specific length to quickly process all of the values of that length.

Since you haven't provided enough code for a runnable example, I've made this rough approximation to show the general shape of such a solution:

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

This can "waste" a little time at the end of each length as the parallel threads spin down one-by-one before spinning back up for the next length, but that seems unlikely to be a primary concern.