I've written a small Sudoku solver using backtracking. Now I want to benchmark the speed of this function. Here is my current code:
type Board struct {
Cells [9][9]int
}
func BenchmarkBacktrack(b *testing.B) {
for i := 0; i < b.N; i++ {
b.StopTimer()
// prevent the modification of the orignal board
copy := &Board{
Cells: exampleBoard.Cells,
}
b.StartTimer()
copy.Backtrack()
}
}
Since &Board
is pointer I would solve the Sudoku in the first iteration and in the next one I would backtrack a solved board. Therefore, I reset the board at the beginning of each iteration. exampleBoard
is filled with sample values.
Is their a better way to benchmark the function without stopping and restarting the timer over and over?
And wouldn't cost the function calls a small amount of time that impacts the benchmark?
And wouldn't cost the function calls a small amount of time that that impacts the benchmark?
Of course they would. So does the for
loop, which is included in the benchmark. Plus overhead of calling copy.Backtrack
function. But the thing is, this should be all irrelevant, unless you're benchmarking a single operation taking nanoseconds (in which case you shouldn't). Creation of an empty board is probably a trivial operation, so I wouldn't touch the timers at all. If it's not trivial, then you're doing it right – call StopTimer
. This is exactly why it was invented:
StopTimer stops timing a test. This can be used to pause the timer while performing complex initialization that you don't want to measure.
You could try providing a func NewBoard([9][9]int) *Board
method, which just initializes a board from the example data. Then write a benchmark for Backtrack()
on a new board and a separate benchmark for NewBoard()
.
Subtracting the two numbers should give you an idea of the speed of your Backtrack method alone.
type Board struct {
Cells [9][9]int
}
var scratch *Board
func NewBoard(cells [9][9]int) *Board {
return &Board{Cells: cells}
}
func BenchmarkBacktrack(b *testing.B) {
for i := 0; i < b.N; i++ {
scratch = NewBoard(exampleBoard.Cells)
scratch.Backtrack()
}
func BenchmarkNewBoard(b *testing.B) {
for i := 0; i < b.N; i++ {
scratch = NewBoard(exampleBoard.Cells)
}
Also note the use of scratch
variable. Trying to create a loop local variable inside the benchmark loop could lead the compiler to optimise away the call to NewBoard()
depending on presence/absence of side-effects. For parity, you need to use the scratch
variable in both benchmarks.