基准测试的糟糕结果

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

Benchmarking bad results

问题

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

  1. func benchmarkConcurrentQuickSort(size int, b *testing.B) {
  2.     A := RandomArray(size)
  3.     var wg sync.WaitGroup
  4.     b.ResetTimer()
  5.     ConcurrentQuicksort(A, 0, len(A)-1, &wg)
  6.     wg.Wait()
  7. }
  9. func BenchmarkConcurrentQuickSort500(b *testing.B) {
  10.     benchmarkConcurrentQuickSort(500, b)
  11. }
  12. func BenchmarkConcurrentQuickSort1000(b *testing.B) {
  13.     benchmarkConcurrentQuickSort(1000, b)
  14. }
  15. func BenchmarkConcurrentQuickSort5000(b *testing.B) {
  16.     benchmarkConcurrentQuickSort(5000, b)
  17. }
  18. func BenchmarkConcurrentQuickSort10000(b *testing.B) {
  19.     benchmarkConcurrentQuickSort(10000, b)
  20. }
  21. func BenchmarkConcurrentQuickSort20000(b *testing.B) {
  22.     benchmarkConcurrentQuickSort(20000, b)
  23. }
  24. func BenchmarkConcurrentQuickSort1000000(b *testing.B) {
  25.     benchmarkConcurrentQuickSort(1000000, b)
  26. }

结果如下：

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

我可以相信最后一个结果，但我肯定认为对一个包含500个元素的数组进行排序所需的时间不可能只有1纳秒。我做错了什么？我非常确定RandomArray返回了所需大小的数组，正如我们在最后一个基准测试中看到的。为什么它打印出0.00纳秒？

  1. func RandomArray(n int) []int {
  2.     a := []int{}
  3.     for i := 0; i < n; i++ {
  4.         a = append(a, rand.Intn(500))
  5.     }
  6.     return a
  7. }
  9. // ConcurrentPartition - ConcurrentQuicksort function for partitioning the array (randomized choice of a pivot)
  10. func ConcurrentPartition(A []int, p int, r int) int {
  11.     index := rand.Intn(r-p) + p
  12.     pivot := A[index]
  13.     A[index] = A[r]
  14.     A[r] = pivot
  15.     x := A[r]
  16.     j := p - 1
  17.     i := p
  18.     for i < r {
  19.         if A[i] <= x {
  20.             j++
  21.             tmp := A[j]
  22.             A[j] = A[i]
  23.             A[i] = tmp
  24.         }
  25.         i++
  26.     }
  27.     temp := A[j+1]
  28.     A[j+1] = A[r]
  29.     A[r] = temp
  30.     return j + 1
  31. }
  33. // ConcurrentQuicksort - a concurrent version of a quicksort algorithm
  34. func ConcurrentQuicksort(A []int, p int, r int, wg *sync.WaitGroup) {
  35.     if p < r {
  36.         q := ConcurrentPartition(A, p, r)
  37.         wg.Add(2)
  38.         go func() {
  39.             ConcurrentQuicksort(A, p, q-1, wg)
  40.             wg.Done()
  41.         }()
  42.         go func() {
  43.             ConcurrentQuicksort(A, q+1, r, wg)
  44.             wg.Done()
  45.         }()
  46.     }
  47. }
英文:

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

  1. func benchmarkConcurrentQuickSort(size int, b *testing.B) {
  2. A := RandomArray(size)
  3. var wg sync.WaitGroup
  4. b.ResetTimer()
  5. ConcurrentQuicksort(A, 0, len(A)-1, &amp;wg)
  6. wg.Wait()
  7. }
  8. func BenchmarkConcurrentQuickSort500(b *testing.B) {
  9. benchmarkConcurrentQuickSort(500, b)
  10. }
  11. func BenchmarkConcurrentQuickSort1000(b *testing.B) {
  12. benchmarkConcurrentQuickSort(1000, b)
  13. }
  14. func BenchmarkConcurrentQuickSort5000(b *testing.B) {
  15. benchmarkConcurrentQuickSort(5000, b)
  16. }
  17. func BenchmarkConcurrentQuickSort10000(b *testing.B) {
  18. benchmarkConcurrentQuickSort(10000, b)
  19. }
  20. func BenchmarkConcurrentQuickSort20000(b *testing.B) {
  21. benchmarkConcurrentQuickSort(20000, b)
  22. }
  23. func BenchmarkConcurrentQuickSort1000000(b *testing.B) {
  24. benchmarkConcurrentQuickSort(1000000, b)
  25. }

The results are like this:

  1. C:\projects\go\src\github.com\frynio\mysort&gt;go test -bench=.
  2. BenchmarkConcurrentQuickSort500-4               2000000000               0.00 ns/op
  3. BenchmarkConcurrentQuickSort1000-4              2000000000               0.00 ns/op
  4. BenchmarkConcurrentQuickSort5000-4              2000000000               0.00 ns/op
  5. BenchmarkConcurrentQuickSort10000-4             2000000000               0.00 ns/op
  6. BenchmarkConcurrentQuickSort20000-4             2000000000               0.00 ns/op
  7. BenchmarkConcurrentQuickSort1000000-4                 30          49635266 ns/op
  8. PASS
  9. 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?

  1. func RandomArray(n int) []int {
  2. a := []int{}
  3. for i := 0; i &lt; n; i++ {
  4. a = append(a, rand.Intn(500))
  5. }
  6. return a
  7. }
  8. // ConcurrentPartition - ConcurrentQuicksort function for partitioning the array (randomized choice of a pivot)
  9. func ConcurrentPartition(A []int, p int, r int) int {
  10. index := rand.Intn(r-p) + p
  11. pivot := A[index]
  12. A[index] = A[r]
  13. A[r] = pivot
  14. x := A[r]
  15. j := p - 1
  16. i := p
  17. for i &lt; r {
  18. if A[i] &lt;= x {
  19. j++
  20. tmp := A[j]
  21. A[j] = A[i]
  22. A[i] = tmp
  23. }
  24. i++
  25. }
  26. temp := A[j+1]
  27. A[j+1] = A[r]
  28. A[r] = temp
  29. return j + 1
  30. }
  31. // ConcurrentQuicksort - a concurrent version of a quicksort algorithm
  32. func ConcurrentQuicksort(A []int, p int, r int, wg *sync.WaitGroup) {
  33. if p &lt; r {
  34. q := ConcurrentPartition(A, p, r)
  35. wg.Add(2)
  36. go func() {
  37. ConcurrentQuicksort(A, p, q-1, wg)
  38. wg.Done()
  39. }()
  40. go func() {
  41. ConcurrentQuicksort(A, q+1, r, wg)
  42. wg.Done()
  43. }()
  44. }
  45. }

答案1

得分: 2

【包测试】

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

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

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

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

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

输出结果：

  1. BenchmarkConcurrentQuickSort500-4       	   10000	    122291 ns/op
  2. BenchmarkConcurrentQuickSort1000-4      	    5000	    221154 ns/op
  3. BenchmarkConcurrentQuickSort5000-4      	    1000	   1225230 ns/op
  4. BenchmarkConcurrentQuickSort10000-4     	     500	   2568024 ns/op
  5. BenchmarkConcurrentQuickSort20000-4     	     300	   5808130 ns/op
  6. 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

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

Output:

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

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

发表评论

匿名网友

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

确定