基准测试的糟糕结果

huangapple go评论79阅读模式
英文:

Benchmarking bad results

问题

所以我已经实现了带有并发的快速排序算法(也有不带并发的版本)。现在我想要比较它们的时间。我写了以下代码:

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个元素的数组进行排序所需的时间不可能只有1纳秒。我做错了什么?我非常确定RandomArray返回了所需大小的数组,正如我们在最后一个基准测试中看到的。为什么它打印出0.00纳秒?

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()
        }()
    }
}
英文:

so I have the Quicksort algorithm implemented with concurrency (the one without as well). Now I wanted to compare the times. I wrote this:

func benchmarkConcurrentQuickSort(size int, b *testing.B) {
A := RandomArray(size)
var wg sync.WaitGroup
b.ResetTimer()
ConcurrentQuicksort(A, 0, len(A)-1, &amp;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)
}

The results are like this:

C:\projects\go\src\github.com\frynio\mysort&gt;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

I can believe the last one, but I definitely think that sorting 500-element array takes longer than 1ns. What am i doing wrong? I am pretty sure that RandomArray returns array of wanted size, as we can see in the last benchmark. Why does it print out the 0.00 ns?

func RandomArray(n int) []int {
a := []int{}
for i := 0; i &lt; 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 &lt; r {
if A[i] &lt;= 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 &lt; 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()
}()
}
}

答案1

得分: 2

【包测试】

一个示例基准函数如下所示:

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

基准函数必须运行目标代码 b.N 次。在基准执行期间,b.N 会进行调整,直到基准函数持续足够长,以便可靠地计时。

我在你的代码中没有看到基准循环。尝试使用以下代码:

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
英文:

> 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.

I don't see a benchmark loop in your code. Try

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

Output:

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

huangapple
  • 本文由 发表于 2017年6月25日 08:25:17
  • 转载请务必保留本文链接:https://go.coder-hub.com/44742110.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定