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 is a version of what I suggested in my comment.

The main loop is parallel and is only over the first byte of each attempt. For each first byte, do the full brute force search for the remainder.

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

Also, even for a brute force method, this is probably highly inefficient still!

Answer 2

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.

Answer 3

If Rayon splits the slices as you described, then apply simple math to balance the password lengths:

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

The span value depends on the number of CPUs (the number of threads used by Rayon), in your case:

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

Note the performance of this approach is highly dependent on how Rayon performs the split of the sequence on parallel threads. Verify that it works as you reported in the question.