병렬 코드를 벤치마킹하는 방법은 무엇입니까?

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) 

비교적 작은 속도 증가는,이 작업 예상 (병렬화 할 복잡한 계산이 없다).