並列コードのベンチマーク方法は？

Question

私はRayonを使用してパラレル化したコードをいくつか用意していますが、その結果は、Bencherで測定されていますが、最も印象的でした。ベンチマークを実行している（おそらく彼らはが並行して実行されていますか？）ので、私はそれがより簡単なケースをテストしたために発生している可能性があります。シーケンシャルコード（extern crate quick_sort）の結果であるが

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

：cargo benchの

#![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); }); 
} 

結果：

はquick_sort crateに基づいて、次の並列コードを検討

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

私もベンチマークを試みましたgはより長いベクトルであるが、結果は一貫していた。さらに、私はGNU時間を使っていくつかのテストを行いました。期待されるように、より大きなベクトルでは並列コードが速くなるようです。

私は間違っていますか？並列コードのベンチマークにBencherを使用できますか？

Answer 1

テストで使用する配列が非常に小さいため、実際にはパラレルコードはになります。

タスクを並行して起動するにはオーバーヘッドがあり、異なるスレッドが同じキャッシュライン上のメモリにアクセスするとメモリアクセスが遅くなります。

小さな配列のオーバーヘッドを避けるためには、with_min_lenがありますが、joinの場合は、おそらく並列/非並列の決定を自分で実装する必要があります。

---

で100倍の配列：それはメモリ結合（並列化する複雑な計算はありません）ですので、

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) 

は比較的小さなスピードアップは、このタスクのために期待されています。