如何基准并行代码？

Question

我有一些代码，我使用Rayon希望提高其性能，但是由Bencher测量的结果是......最不起眼的。我怀疑它可能是由我执行基准测试的方式引起的（也许它们是并行运行的？），所以我测试了一个更简单的案例。

考虑以下基于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); } );
}

cargo bench的结果：

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

而顺序代码（extern crate quick_sort）的结果是：

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

我也尝试使用较长的向量进行基准测试，但结果是一致的。此外，我使用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)

预计此任务的加速时间相对较小，因为它受内存限制（没有复杂的并行计算）。