Go中切片排序的意外基准结果

Question

I just started learning golang and decided to implement some basic sorting algorithms (bubble sort, selection sort, and insertion sort) to try working with packages, slices, and testing infrastructure.

Here's the implementation:

package child_sort

func SortBubble(xs []int) {
    for i := range xs {
        swapped := false
        for j := 1; j < len(xs)-i; j++ {
            if xs[j-1] > xs[j] {
                xs[j-1], xs[j] = xs[j], xs[j-1]
                swapped = true
            }
        }
        if !swapped {
            break
        }
    }
}

func SortSelection(xs []int) {
    for i := range xs {
        min_i := i
        for j := i + 1; j < len(xs); j++ {
            if xs[j] < xs[min_i] {
                min_i = j
            }
        }
        if min_i != i {
            xs[i], xs[min_i] = xs[min_i], xs[i]
        }
    }
}

func SortInsertion(xs []int) {
    for i := 1; i < len(xs); i++ {
        for j := i; j > 0; j-- {
            if xs[j] < xs[j-1] {
                xs[j], xs[j-1] = xs[j-1], xs[j]
            }
        }
    }
}

Unit tests seem to work fine, but when I created benchmarks for these, I got weird results, like these:

go test --bench . --benchmem 
PASS
BenchmarkBubble        1    2258469081 ns/op      241664 B/op          1 allocs/op
BenchmarkSelection  1000000000           0.60 ns/op        0 B/op          0 allocs/op
BenchmarkInsertion         1    1180026827 ns/op      241664 B/op          1 allocs/op
ok      .../go/src/child_sort   12.976s

What bugs me is that selection sort runs almost instantly and produces zero allocations. Same thing happens to other sorting algos if I decrease the size of the arrays. And the opposite is true, i.e. if I increase the size, selection sort starts to behave sanely.

Here's the tests file:

package child_sort

import (
    "math/rand"
    "testing"
    "time"
)

func generate(size int, min, max int) []int {
    rand.Seed(time.Now().UTC().UnixNano())
    var xs = make([]int, size, size)
    for i := range xs {
        xs[i] = min + rand.Intn(max-min)
    }
    return xs
}

func TestSortBubble(t *testing.T) {
    xs := []int{9, 8, 7, 6, 5}
    ys := []int{5, 6, 7, 8, 9}
    SortBubble(xs)
    for i, v := range xs {
        if v != ys[i] {
            t.Errorf("fail")
        }
    }
}

func TestSortSelection(t *testing.T) {
    xs := []int{1, 2, 9, 6, 2}
    ys := []int{1, 2, 2, 6, 9}
    SortSelection(xs)
    for i, v := range xs {
        if v != ys[i] {
            t.Errorf("fail")
        }
    }
}

func TestSortInsertion(t *testing.T) {
    xs := []int{1, 2, 9, 6, 2}
    ys := []int{1, 2, 2, 6, 9}
    SortInsertion(xs)
    for i, v := range xs {
        if v != ys[i] {
            t.Errorf("fail")
        }
    }
}

func BenchmarkBubble(b *testing.B) {
    xs := generate(10000, -100, 100)
    /* b.ResetTimer() */
    SortBubble(xs)
}

func BenchmarkSelection(b *testing.B) {
    xs := generate(10000, -100, 100)
    /* b.ResetTimer() */
    SortSelection(xs)
}

func BenchmarkInsertion(b *testing.B) {
    xs := generate(10000, -100, 100)
    /* b.ResetTimer() */
    SortInsertion(xs)
}

Answer 1

The observed effects have nothing to do with your sorting code, slices or whatever. You are simply not using b testing.B properly: You are supposed to execute your code b.N times.

Have a look at how the standard sorting package does its benchmarks: http://golang.org/src/pkg/sort/sort_test.go