So I've decided to write test for my function in golang. The function itself looks like this:
func Insert(slice []int, element int, index int) []int {
n := len(slice)
slice = slice[:(n + 1)]
for i := index; i < n; i++ {
slice[i+1] = slice[i]
}
slice[index] = element
return slice
}
So it takes a slice, extends its length by 1 and inserts an element at given index. Now before I call it I have to do 2 things:
size := somevalue
array := make([]int, size, size+1)
and then f.e array = Insert(array, 1, len(array)/2. Now I wrote insert_test.go:
package sdizo
import "testing"
func benchmarkInsert(size int, b *testing.B) {
b.ResetTimer()
for n := 0; n < b.N; n++ {
array := make([]int, size, size+1)
array = Insert(array, 1, len(array)/2)
}
}
func BenchmarkInsert10k(b *testing.B) { benchmarkInsert(10000, b) }
func BenchmarkInsert20k(b *testing.B) { benchmarkInsert(20000, b) }
func BenchmarkInsert30k(b *testing.B) { benchmarkInsert(30000, b) }
func BenchmarkInsert40k(b *testing.B) { benchmarkInsert(40000, b) }
func BenchmarkInsert50k(b *testing.B) { benchmarkInsert(50000, b) }
The thing is, there are 2 operations in testing loop. I cannot move the make() above the loop, cuz it has to make a new array everytime it tries to insert something to it (don't want to mess with capacity). It works, it gives me output, but I am curious if this make() doesn't mess up with time measurement, and I would like to ask you if I can somehow measure the time only for Insert()
P.S Is there a convenient way to write down the results of benchmark test to a file?
For example (from Go 1.7 forward), using your Insert algorithm,
package sdizo
import (
"strconv"
"testing"
)
func Insert(slice []int, element int, index int) []int {
n := len(slice)
slice = slice[:(n + 1)]
for i := index; i < n; i++ {
slice[i+1] = slice[i]
}
slice[index] = element
return slice
}
func BenchmarkInsert(b *testing.B) {
for size := 10000; size <= 50000; size += 10000 {
b.Run(strconv.Itoa(size/1000)+"k",
func(b *testing.B) {
a := make([]int, size, size+1)
b.ReportAllocs()
b.ResetTimer()
for i := 0; i < b.N; i++ {
a = a[:size]
a = Insert(a, 1, len(a)/2)
}
b.StopTimer()
},
)
}
}
Output:
$ go test -bench=.
goos: linux
goarch: amd64
pkg: sdizo
BenchmarkInsert/10k-4 50000 32502 ns/op 0 B/op 0 allocs/op
BenchmarkInsert/20k-4 20000 64364 ns/op 0 B/op 0 allocs/op
BenchmarkInsert/30k-4 20000 97310 ns/op 0 B/op 0 allocs/op
BenchmarkInsert/40k-4 10000 129196 ns/op 0 B/op 0 allocs/op
BenchmarkInsert/50k-4 10000 161427 ns/op 0 B/op 0 allocs/op
PASS
ok so/sdizo 9.778s
$
Now that we can benchmark your Insert algorithm, we can use that knowledge to improve the algorithm. For example,
package sdizo
import (
"strconv"
"testing"
)
func Insert(slice []int, element int, index int) []int {
slice = slice[:len(slice)+1]
copy(slice[index+1:], slice[index:])
slice[index] = element
return slice
}
func BenchmarkInsert(b *testing.B) {
for size := 10000; size <= 50000; size += 10000 {
b.Run(strconv.Itoa(size/1000)+"k",
func(b *testing.B) {
a := make([]int, size, size+1)
b.ReportAllocs()
b.ResetTimer()
for i := 0; i < b.N; i++ {
a = a[:size]
a = Insert(a, 1, len(a)/2)
}
b.StopTimer()
},
)
}
}
Output:
$ go test -bench=.
goos: linux
goarch: amd64
pkg: sdizo
BenchmarkInsert/10k-4 200000 7664 ns/op 0 B/op 0 allocs/op
BenchmarkInsert/20k-4 100000 15208 ns/op 0 B/op 0 allocs/op
BenchmarkInsert/30k-4 100000 22959 ns/op 0 B/op 0 allocs/op
BenchmarkInsert/40k-4 50000 35181 ns/op 0 B/op 0 allocs/op
BenchmarkInsert/50k-4 50000 39658 ns/op 0 B/op 0 allocs/op
PASS
ok so/sdizo 10.331s
$
EDIT: The real answer you seek. (Finally)
When you benchmark, actually benchmark what you want to benchmark. Your use case isn't going to be a make, then insert every time, so just make once, then test insert in the loop. The point is to test ONLY the chokepoint.
What you want to do here is just test Insert. You can do this by simply resizing the array each time, the cost of which is basically nothing (at least in comparison to make or Insert).
func benchmarkInsert(size int, b *testing.B) {
array := make([]int, size, size+1)
b.ResetTimer()
for n := 0; n < b.N; n++ {
array = Insert(array, 1, len(array)/2)
array = array[0:size]
}
}
To explain why it is minimal, you have to realize that deep down, a slice is essentially a struct that looks something like this:
type Slice struct {
contents []interface{}
length int
capacity int
}
Performing the operation to resize it using array = array[0:size] is analogous to setting the struct's length=size. See https://blog.golang.org/go-slices-usage-and-internals
As far as writing the results to file, that depends on your operating system. On any Unix system, simply running the benchmark command with > file.txt at the end will pipe the results to file.txt. Not sure about Windows.
EDIT: Adding more tests shows this scales linearly.
BenchmarkInsert10k-8 200000 7889 ns/op
BenchmarkInsert20k-8 100000 16131 ns/op
BenchmarkInsert30k-8 100000 24184 ns/op
BenchmarkInsert40k-8 50000 31767 ns/op
BenchmarkInsert50k-8 50000 39721 ns/op
BenchmarkInsert100k-8 20000 79711 ns/op
BenchmarkInsert200k-8 10000 159411 ns/op
BenchmarkInsert300k-8 5000 237188 ns/op
BenchmarkInsert400k-8 5000 316270 ns/op
BenchmarkInsert500k-8 3000 399146 ns/op
BenchmarkInsert1000k-8 2000 793845 ns/op
Using this code: https://play.golang.org/p/6fWHwpzUJE