go - 基准不良结果

Question

所以我实现了并发的 Quicksort 算法(也没有)。现在我想比较一下时间。我写了这个:

func benchmarkConcurrentQuickSort(size int, b *testing.B) {
    A := RandomArray(size)
    var wg sync.WaitGroup
    b.ResetTimer()
    ConcurrentQuicksort(A, 0, len(A)-1, &wg)
    wg.Wait()
}

func BenchmarkConcurrentQuickSort500(b *testing.B) {
    benchmarkConcurrentQuickSort(500, b)
}
func BenchmarkConcurrentQuickSort1000(b *testing.B) {
    benchmarkConcurrentQuickSort(1000, b)
}
func BenchmarkConcurrentQuickSort5000(b *testing.B) {
    benchmarkConcurrentQuickSort(5000, b)
}
func BenchmarkConcurrentQuickSort10000(b *testing.B) {
    benchmarkConcurrentQuickSort(10000, b)
}
func BenchmarkConcurrentQuickSort20000(b *testing.B) {
    benchmarkConcurrentQuickSort(20000, b)
}
func BenchmarkConcurrentQuickSort1000000(b *testing.B) {
    benchmarkConcurrentQuickSort(1000000, b)
}

结果是这样的:

C:\projects\go\src\github.com\frynio\mysort>go test -bench=.
BenchmarkConcurrentQuickSort500-4               2000000000               0.00 ns/op
BenchmarkConcurrentQuickSort1000-4              2000000000               0.00 ns/op
BenchmarkConcurrentQuickSort5000-4              2000000000               0.00 ns/op
BenchmarkConcurrentQuickSort10000-4             2000000000               0.00 ns/op
BenchmarkConcurrentQuickSort20000-4             2000000000               0.00 ns/op
BenchmarkConcurrentQuickSort1000000-4                 30          49635266 ns/op
PASS
ok      github.com/frynio/mysort        8.342s

我可以相信最后一个，但我绝对认为对 500 个元素的数组进行排序需要的时间超过 1ns。我究竟做错了什么？我很确定 RandomArray 会返回所需大小的数组，正如我们在上一个基准测试中看到的那样。为什么打印出 0.00 ns？

func RandomArray(n int) []int {
    a := []int{}
    for i := 0; i < n; i++ {
        a = append(a, rand.Intn(500))
    }
    return a
}

// ConcurrentPartition - ConcurrentQuicksort function for partitioning the array (randomized choice of a pivot)
func ConcurrentPartition(A []int, p int, r int) int {
    index := rand.Intn(r-p) + p
    pivot := A[index]
    A[index] = A[r]
    A[r] = pivot
    x := A[r]
    j := p - 1
    i := p
    for i < r {
        if A[i] <= x {
            j++
            tmp := A[j]
            A[j] = A[i]
            A[i] = tmp
        }
        i++
    }
    temp := A[j+1]
    A[j+1] = A[r]
    A[r] = temp
    return j + 1
}

// ConcurrentQuicksort - a concurrent version of a quicksort algorithm
func ConcurrentQuicksort(A []int, p int, r int, wg *sync.WaitGroup) {
    if p < r {
        q := ConcurrentPartition(A, p, r)
        wg.Add(2)
        go func() {
            ConcurrentQuicksort(A, p, q-1, wg)
            wg.Done()
        }()
        go func() {
            ConcurrentQuicksort(A, q+1, r, wg)
            wg.Done()
        }()
    }
}

Answer 1

Package testing

A sample benchmark function looks like this:

func BenchmarkHello(b *testing.B) {
    for i := 0; i < b.N; i++ {
        fmt.Sprintf("hello")
    }
}

The benchmark function must run the target code b.N times. During benchmark execution, b.N is adjusted until the benchmark function lasts long enough to be timed reliably.

我在您的代码中没有看到基准循环。尝试

func benchmarkConcurrentQuickSort(size int, b *testing.B) {
    A := RandomArray(size)
    var wg sync.WaitGroup
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        ConcurrentQuicksort(A, 0, len(A)-1, &wg)
        wg.Wait()
    }
}

输出:

BenchmarkConcurrentQuickSort500-4              10000        122291 ns/op
BenchmarkConcurrentQuickSort1000-4              5000        221154 ns/op
BenchmarkConcurrentQuickSort5000-4              1000       1225230 ns/op
BenchmarkConcurrentQuickSort10000-4              500       2568024 ns/op
BenchmarkConcurrentQuickSort20000-4              300       5808130 ns/op
BenchmarkConcurrentQuickSort1000000-4              1    1371751710 ns/op