Wie man parallelen Code vergleicht?

Question

Ich habe einige Code, den ich paralellisierte mit Rayon in der Hoffnung, seine Leistung zu verbessern, aber die Ergebnisse, gemessen durch die Bencher, waren ... am wenigsten beeindruckend. Ich vermutete, dass dies auf die Art und Weise zurückzuführen sein könnte, wie ich die Benchmarks durchführe (vielleicht sie werden parallel ausgeführt?), Also habe ich einen einfacheren Fall getestet.

Betrachten Sie den folgenden parallelisierten Code, basierend auf dem quick_sort crate:

#![feature(test)] 

extern crate rayon; 
extern crate test; 

use test::Bencher; 
use std::cmp::Ordering; 

pub fn sort<T>(arr: &mut [T]) 
    where T: Send + std::cmp::PartialEq + Ord 
{ 
    qsort(arr, find_pivot, &|a, b| a.cmp(b)) 
} 

pub fn sort_by<T, F>(arr: &mut [T], compare: &F) 
    where T: Send + std::cmp::PartialOrd, 
      F: Sync + Fn(&T, &T) -> Ordering 
{ 
    qsort(arr, find_pivot, compare); 
} 

fn qsort<T, F>(arr: &mut [T], pivot: fn(&[T], &F) -> usize, compare: &F) 
    where T: Send + std::cmp::PartialOrd, 
      F: Sync + Fn(&T, &T) -> Ordering 
{ 
    let len = arr.len(); 
    if len <= 1 { 
     return; 
    } 

    let p = pivot(arr, compare); 
    let p = partition(arr, p, compare); 
    let (l, r) = arr.split_at_mut(p + 1); 
    if p > len/2 { 
     rayon::join(
      || qsort(r, pivot, compare), 
      || qsort(l, pivot, compare) 
     ); 
    } else { 
     rayon::join(
      || qsort(l, pivot, compare), 
      || qsort(r, pivot, compare) 
     ); 
    } 
} 

fn find_pivot<T, F>(arr: &[T], compare: &F) -> usize 
    where T: Send + std::cmp::PartialOrd, 
      F: Sync + Fn(&T, &T) -> Ordering 
{ 
    let (l, r) = (0, arr.len() - 1); 
    let m = l + ((r - 1)/2); 
    let (left, middle, right) = (&arr[l], &arr[m], &arr[r]); 
    if (compare(middle, left) != Ordering::Less) && (compare(middle, right) != Ordering::Greater) { 
     m 
    } else if (compare(left, middle) != Ordering::Less) && 
       (compare(left, right) != Ordering::Greater) { 
     l 
    } else { 
     r 
    } 
} 


fn partition<T, F>(arr: &mut [T], p: usize, compare: &F) -> usize 
    where T: std::cmp::PartialOrd, 
      F: Sync + Fn(&T, &T) -> Ordering 
{ 
    if arr.len() <= 1 { 
     return p; 
    } 

    let last = arr.len() - 1; 
    let mut next_pivot = 0; 
    arr.swap(last, p); 
    for i in 0..last { 
     if compare(&arr[i], &arr[last]) == Ordering::Less { 
      arr.swap(i, next_pivot); 
      next_pivot += 1; 
     } 
    } 

    arr.swap(next_pivot, last); 
    next_pivot 
} 

#[bench] 
fn bench_qsort(b: &mut Bencher) { 
    let mut vec = vec![ 3, 97, 50, 56, 58, 80, 91, 71, 83, 65, 
         92, 35, 11, 26, 69, 44, 42, 75, 40, 43, 
         63, 5, 62, 56, 35, 3, 51, 97, 100, 73, 
         42, 41, 79, 86, 93, 58, 65, 96, 66, 36, 
         17, 97, 6, 16, 52, 30, 38, 14, 39, 7, 
         48, 83, 37, 97, 21, 58, 41, 59, 97, 37, 
         97, 9, 24, 78, 77, 7, 78, 80, 11, 79, 
         42, 30, 39, 27, 71, 61, 12, 8, 49, 62, 
         69, 48, 8, 56, 89, 27, 1, 80, 31, 62, 
         7, 15, 30, 90, 75, 78, 22, 99, 97, 89]; 

    b.iter(|| { sort(&mut vec); }); 
} 

Ergebnisse cargo bench:

running 1 test 
test bench_qsort ... bench:  10,374 ns/iter (+/- 296) // WHAT 

Während die Ergebnisse für den sequentiellen Code (extern crate quick_sort) sind:

running 1 test 
test bench_qsort ... bench:  1,070 ns/iter (+/- 65) 

Ich habe auch Benchmark versucht g mit längeren Vektoren, aber die Ergebnisse waren konsistent. Außerdem habe ich einige Tests mit GNU-Zeit durchgeführt und es sieht so aus, als ob der parallele Code wie erwartet mit größeren Vektoren schneller ist.

Was mache ich falsch? Kann ich Bencher verwenden, um parallelen Code zu vergleichen?

Answer 1

Das Array, das Sie im Test verwenden, ist so klein, dass in diesem Fall der parallele Code langsamer ist.

Es gibt einen gewissen Mehraufwand für das parallele Starten von Tasks, und der Speicherzugriff wird langsamer, wenn verschiedene Threads auf Speicher auf derselben Cachezeile zugreifen.

Für Iteratoren, um Overhead auf winzigen Arrays zu vermeiden, gibt es with_min_len, aber für join müssen Sie wahrscheinlich parallel/nicht-parallele Entscheidung selbst implementieren.

---

Mit 100-mal größer Array:

with rayon:   3,468,891 ns/iter (+/- 95,859) 
without rayon:   4,227,220 ns/iter (+/- 635,260) 
rayon if len > 1000: 3,166,570 ns/iter (+/- 66,329) 

Das relativ geringe Geschwindigkeit-up für diese Aufgabe zu erwarten ist, weil es speicher gebunden ist (es gibt keine komplexe Berechnung parallelisieren).