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

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

1 голос
/ 09 мая 2020 
#![feature(map_first_last)]
use num_cpus;

use std::collections::BTreeMap;
use ordered_float::OrderedFloat;

use std::sync::{Arc, Mutex};
use std::thread;


use std::time::Instant;

const MONO_FREQ: [f64; 26] = [
    8.55, 1.60, 3.16, 3.87, 12.1, 2.18, 2.09, 4.96, 7.33, 0.22, 0.81, 4.21, 2.53, 7.17, 7.47, 2.07,
    0.10, 6.33, 6.73, 8.94, 2.68, 1.06, 1.83, 0.19, 1.72, 0.11,
];

fn main() {
    let ciphertext : String = "helloworldthisisatest".to_string();
    concurrent( &ciphertext);
    parallel( &ciphertext);

}

fn concurrent(ciphertext : &String) {
    let start = Instant::now();

    for _ in 0..50000 {

        let mut best_fit : f64 = chi_squared(&ciphertext);
        let mut best_key : u8 = 0;

        for i in 1..26 {
            let test_fit = chi_squared(&decrypt(&ciphertext, i));
            if test_fit < best_fit {
                best_key = i;
                best_fit = test_fit;
            }
        }
    }

    let elapsed = start.elapsed();
    println!("Concurrent : {} ms", elapsed.as_millis());
}

fn parallel(ciphertext : &String) {
    let cpus = num_cpus::get() as u8;
    let start = Instant::now();

    for _ in 0..50000 {

        let mut best_result : f64 = chi_squared(&ciphertext);

        for i in (0..26).step_by(cpus.into()) {
            let results = Arc::new(Mutex::new(BTreeMap::new()));
            let mut threads = vec![];

            for ii in i..i+cpus {
                threads.push(thread::spawn({
                    let clone = Arc::clone(&results);
                    let test = OrderedFloat(chi_squared(&decrypt(&ciphertext, ii)));
                    move || {
                        let mut v = clone.lock().unwrap();
                        v.insert(test, ii);
                    }
                }));
            }
            for t in threads {
                t.join().unwrap();
            }
            let lock = Arc::try_unwrap(results).expect("Lock still has multiple owners");
            let hold = lock.into_inner().expect("Mutex cannot be locked");
            if hold.last_key_value().unwrap().0.into_inner() > best_result {
                best_result = hold.last_key_value().unwrap().0.into_inner();
            }
        }

    }
    let elapsed = start.elapsed();
    println!("Parallel : {} ms", elapsed.as_millis());
}

fn decrypt(ciphertext : &String, shift : u8) -> String {
    ciphertext.chars().map(|x| ((x as u8 + shift - 97) % 26 + 97) as char).collect()
}

pub fn chi_squared(text: &str) -> f64 {     
    let mut result: f64 = 0.0;
    for (pos, i) in get_letter_counts(text).iter().enumerate() {
        let expected = MONO_FREQ[pos] * text.len() as f64 / 100.0;
        result += (*i as f64 - expected).powf(2.0) / expected;
    }
    return result;
}

fn get_letter_counts(text: &str) -> [u64; 26] {
    let mut results: [u64; 26] = [0; 26];
    for i in text.chars() {
        results[((i as u64) - 97) as usize] += 1;
    }
    return results;
}

Извините, что сбрасываю так много кода, но я понятия не имею, в чем проблема, независимо от того, что я пробую, параллельный код кажется примерно в 100 раз медленнее.

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

Я пробовал ar c mutex, rayon и messaging и все такое замедлите его, когда он должен его ускорить. Что я могу сделать, чтобы это ускорить?

1 Ответ

0 голосов
/ 09 мая 2020

Ваш код вычисляет chi_squared функцию в основном потоке, вот правильная версия. 

  for ii in i..i + cpus {
        let cp = ciphertext.clone();
        let clone = Arc::clone(&results);
        threads.push(thread::spawn(move || {
            let test = OrderedFloat(chi_squared(&decrypt(&cp, ii)));
            let mut v = clone.lock().unwrap();
            v.insert(test, ii);
        }));
}

Обратите внимание, что не имеет значения, вычисляется он параллельно или нет, потому что порождение 50000 * 26 потоков и накладные расходы на синхронизацию между потоками - вот что в первую очередь составляет 100-кратную разницу. Использование реализации threadpool снизит накладные расходы, но результат все равно будет намного медленнее, чем однопоточная версия. Единственное, что вы можете сделать, это назначить работу во внешнем l oop (0..50000), однако я предполагаю, что вы пытаетесь распараллелить внутри основного l oop.

...