ベンチマーキングの悪い結果

Question

私はクイックソートアルゴリズムを並行処理で実装しました。今は時代を比較したいと思っていました。私はこれを書いた：

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

サンプルのベンチマーク機能は次のようになります。

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