Testing a function in golang

Question

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?

It is slightly flaky to implement a function in such a way: now you rely on the caller to provide a large enough slice, and panic otherwise. — zerkms
– zerkms, Commented Mar 26, 2017 at 0:58

peterSO · Accepted Answer · 2017-03-26 13:58:39Z

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
$

One of my edits had a faster algorithm :P. Haha, sorry, just teasing. OP wasn't going for optimization anyway, so I removed the clutter from my answer.

RayfenWindspear · Accepted Answer · 2017-03-26 04:29:23Z

1

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

edited Mar 26, 2017 at 4:29

answered Mar 26, 2017 at 1:56

RayfenWindspear

6,3241 gold badge34 silver badges44 bronze badges

22 Comments

Paul Hankin Over a year ago

Faster, but isn't it incorrect? I think your append should go before the assignment of element to pre[index]. play.golang.org/p/ng7dX2rLKm

RayfenWindspear Over a year ago

You are right, it is still referencing the same elements of the slice. I fixed it now. A new one has to be allocated, which slows things down. Still, this trick is about twice as fast... unfortunate that it isn't as cool as I originally thought. play.golang.org/p/GywtiP3Lun

RayfenWindspear Over a year ago

@PaulHankin Ok, here, now it's super fast AND correct. play.golang.org/p/vdYQGXSZas

minecraftplayer1234 Over a year ago

And what if I cannot use append (have to make about every algorithm by myself). And btw I checked your version, its faster, but the graph looks like this (should be aproximately a straight line) gyazo.com/ff670cd918aa89bbec8add2169ccf431

minecraftplayer1234 Over a year ago

I mean the data you got is fine enough I guess (times get bigger x2, x1.5, x1.33, x1.25), but in my case its not. Did you change the tests somehow? @Edit, okay I tested it on Windows and it works really nice, I guess I will have to say goodbye to Linux on VM :(

|

Collectives™ on Stack Overflow

Testing a function in golang

2 Answers 2

1 Comment

22 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

22 Comments

Your Answer

Sign up or log in

Post as a guest

Related