Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
package main
import (
"math/rand"
std "sort"
"strconv"
"testing"
uno "github.com/peterrk/slices"
exp "golang.org/x/exp/slices"
)
func randomInts(list []int) {
size := len(list)
for i := 0; i < size; i++ {
list[i] = rand.Int()
}
}
func constantInts(list []int) {
size := len(list)
v := rand.Int()
for i := 0; i < size; i++ {
list[i] = v
}
}
func descentInts(list []int) {
size := len(list)
v := rand.Int()
for i := 0; i < size; i++ {
list[i] = v + size - i
}
}
func ascentInts(list []int) {
size := len(list)
v := rand.Int()
for i := 0; i < size; i++ {
list[i] = v + i
}
}
func smallInts(list []int) {
size := len(list)
limit := size / 100
for i := 0; i < size; i++ {
list[i] = rand.Intn(limit)
}
}
func mixedInts(list []int) {
size := len(list)
part := size / 5
limit := part / 100
for i := 0; i < part; i++ {
list[i] = rand.Intn(limit)
}
v := rand.Int()
for i := part; i < part*2; i++ {
list[i] = v + i
}
v = rand.Int()
for i := part * 2; i < part*3; i++ {
list[i] = v + size - i
}
for i := part * 3; i < part*4; i++ {
list[i] = rand.Int()
}
for i := part * 4; i < size; i++ {
list[i] = 0
}
}
type genFunc struct {
name string
fn func([]int)
}
var pattern = []genFunc{
genFunc{"Small", smallInts},
genFunc{"Random", randomInts},
genFunc{"Constant", constantInts},
genFunc{"Descent", descentInts},
genFunc{"Ascent", ascentInts},
genFunc{"Mixed", mixedInts},
}
type sizeClass struct {
name string
size int
}
var level = []sizeClass{
sizeClass{"1K", 1000},
sizeClass{"10K", 10_000},
sizeClass{"100K", 100_000},
sizeClass{"1M", 1000_000},
}
func benchmarkInt(b *testing.B, sort func([]int)) {
for _, gen := range pattern {
for _, sc := range level {
b.Run(gen.name+"-"+sc.name, func(b *testing.B) {
b.StopTimer()
rand.Seed(0)
list := make([]int, sc.size)
for i := 0; i < b.N; i++ {
gen.fn(list)
b.StartTimer()
sort(list)
b.StopTimer()
}
})
}
}
}
func BenchmarkIntUno(b *testing.B) {
benchmarkInt(b, uno.Sort[int])
}
func BenchmarkIntExp(b *testing.B) {
benchmarkInt(b, exp.Sort[int])
}
func BenchmarkIntStd(b *testing.B) {
benchmarkInt(b, std.Ints)
}
func benchmarkFloat(b *testing.B, sort func([]float64)) {
for _, sc := range level {
b.Run(sc.name, func(b *testing.B) {
b.StopTimer()
rand.Seed(0)
list := make([]float64, sc.size)
for i := 0; i < b.N; i++ {
for j := 0; j < sc.size; j++ {
list[j] = rand.Float64()
}
b.StartTimer()
sort(list)
b.StopTimer()
}
})
}
}
func BenchmarkFloatUno(b *testing.B) {
benchmarkFloat(b, uno.Sort[float64])
}
func BenchmarkFloatExp(b *testing.B) {
benchmarkFloat(b, exp.Sort[float64])
}
func BenchmarkFloatStd(b *testing.B) {
benchmarkFloat(b, std.Float64s)
}
func benchmarkString(b *testing.B, sort func([]string)) {
for _, sc := range level {
b.Run(sc.name, func(b *testing.B) {
b.StopTimer()
rand.Seed(0)
list := make([]string, sc.size)
for i := 0; i < b.N; i++ {
for j := 0; j < sc.size; j++ {
list[j] = strconv.Itoa(rand.Int())
}
b.StartTimer()
sort(list)
b.StopTimer()
}
})
}
}
func BenchmarkStrUno(b *testing.B) {
benchmarkString(b, uno.Sort[string])
}
func BenchmarkStrExp(b *testing.B) {
benchmarkString(b, exp.Sort[string])
}
func BenchmarkStrStd(b *testing.B) {
benchmarkString(b, std.Strings)
}
type object struct {
val int
pad [5]int
}
var order = uno.Order[object]{
Less: func(a, b object) bool {
return a.val < b.val
},
RefLess: func(a, b *object) bool {
return a.val < b.val
},
}
func benchmarkStruct(b *testing.B, sort func([]object)) {
for _, sc := range level {
b.Run(sc.name, func(b *testing.B) {
b.StopTimer()
rand.Seed(0)
list := make([]object, sc.size)
for i := 0; i < b.N; i++ {
for j := 0; j < sc.size; j++ {
list[j].val = rand.Int()
}
b.StartTimer()
sort(list)
b.StopTimer()
}
})
}
}
func BenchmarkStructUno(b *testing.B) {
benchmarkStruct(b, func(list []object) {
order.Sort(list)
})
}
func BenchmarkStructExp(b *testing.B) {
benchmarkStruct(b, func(list []object) {
exp.SortFunc(list, func(a, b object) bool {
return a.val < b.val
})
})
}
func BenchmarkStructStd(b *testing.B) {
benchmarkStruct(b, func(list []object) {
std.Slice(list, func(i, j int) bool {
return list[i].val < list[j].val
})
})
}
func BenchmarkStableUno(b *testing.B) {
benchmarkStruct(b, func(list []object) {
order.SortStable(list)
})
}
func BenchmarkStableExp(b *testing.B) {
benchmarkStruct(b, func(list []object) {
exp.SortStableFunc(list, func(a, b object) bool {
return a.val < b.val
})
})
}
func BenchmarkStableStd(b *testing.B) {
benchmarkStruct(b, func(list []object) {
std.SliceStable(list, func(i, j int) bool {
return list[i].val < list[j].val
})
})
}
func benchmarkPointer(b *testing.B, sort func([]*object)) {
for _, sc := range level {
b.Run(sc.name, func(b *testing.B) {
b.StopTimer()
rand.Seed(0)
list := make([]*object, sc.size)
for j := 0; j < sc.size; j++ {
list[j] = new(object)
}
for i := 0; i < b.N; i++ {
for j := 0; j < sc.size; j++ {
list[j].val = rand.Int()
}
b.StartTimer()
sort(list)
b.StopTimer()
}
})
}
}
func BenchmarkPointerUno(b *testing.B) {
benchmarkPointer(b, func(list []*object) {
uno.SortFunc(list, func(a, b *object) bool {
return a.val < b.val
})
})
}
func BenchmarkPointerExp(b *testing.B) {
benchmarkPointer(b, func(list []*object) {
exp.SortFunc(list, func(a, b *object) bool {
return a.val < b.val
})
})
}
func BenchmarkPointerStd(b *testing.B) {
benchmarkPointer(b, func(list []*object) {
std.Slice(list, func(i, j int) bool {
return list[i].val < list[j].val
})
})
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment