Почему параллельная обработка на районной основе занимает больше времени, чем последовательная обработка?

Question

Обучение Район , я хотел сравнить производительность параллельных вычислений и последовательных вычислений рядов Фибоначчи.Вот мой код:

use rayon;
use std::time::Instant;

fn main() {
    let nth = 30;
    let now = Instant::now();
    let fib = fibonacci_serial(nth);
    println!(
        "[s] The {}th number in the fibonacci sequence is {}, elapsed: {}",
        nth,
        fib,
        now.elapsed().as_micros()
    );

    let now = Instant::now();
    let fib = fibonacci_parallel(nth);
    println!(
        "[p] The {}th number in the fibonacci sequence is {}, elapsed: {}",
        nth,
        fib,
        now.elapsed().as_micros()
    );
}

fn fibonacci_parallel(n: u64) -> u64 {
    if n <= 1 {
        return n;
    }

    let (a, b) = rayon::join(|| fibonacci_parallel(n - 2), || fibonacci_parallel(n - 1));
    a + b
}

fn fibonacci_serial(n: u64) -> u64 {
    if n <= 1 {
        return n;
    }

    fibonacci_serial(n - 2) + fibonacci_serial(n - 1)
}

Запуск на Rust Playground

Я ожидал, что истекшее время параллельных вычислений будет меньше, чем истекшее время последовательной калькуляции, норезультат был противоположным:

# `s` stands for serial calculation and `p` for parallel
[s] The 30th number in the fibonacci sequence is 832040, elapsed: 12127
[p] The 30th number in the fibonacci sequence is 832040, elapsed: 990379

Моя реализация для последовательных / параллельных вычислений имела бы недостатки.Но если нет, то почему я вижу эти результаты?

Answer 1

Я думаю, что настоящая причина в том, что вы создаете n² темы, что нехорошо.При каждом вызове fibonacci_parallel вы создаете еще одну пару потоков для района, и поскольку вы снова вызываете fibonacci_parallel в замыкании, вы создаете еще одну пару потоков.
Это ужасно для ОС / района.

Подход для решения этой проблемы может быть следующим:

fn fibonacci_parallel(n: u64) -> u64 {
    fn inner(n: u64) -> u64 {
        if n <= 1 { 
            return n;
        }   

        inner(n - 2) + inner(n - 1)
    }   

    if n <= 1 {
        return n;
    }   

    let (a, b) = rayon::join(|| inner(n - 2), || inner(n - 1));
    a + b 
}

Вы создаете два потока, которые оба выполняют внутреннюю функцию.С этим дополнением я получаю

op@VBOX /t/t/foo> cargo run --release 40
    Finished release [optimized] target(s) in 0.03s
     Running `target/release/foo 40`
[s] The 40th number in the fibonacci sequence is 102334155, elapsed: 1373741
[p] The 40th number in the fibonacci sequence is 102334155, elapsed: 847343

Но, как уже говорилось, для малых чисел параллельное выполнение не стоит:

op@VBOX /t/t/foo> cargo run --release 20
    Finished release [optimized] target(s) in 0.02s
     Running `target/release/foo 20`
[s] The 10th number in the fibonacci sequence is 6765, elapsed: 82
[p] The 10th number in the fibonacci sequence is 6765, elapsed: 241