insert_to_slice_perf_test.go

insert_to_slice_perf_test.go

package main

import (
	"fmt"
	"math/rand"
	"time"

	"github.com/sajari/regression"
	"gonum.org/v1/plot"
	"gonum.org/v1/plot/plotter"
	"gonum.org/v1/plot/vg"
)

type TestInsertSlice struct{}

// Main function to test inserts
func insert(a []int, c int, i int) []int {
	return append(a[:i], append([]int{c}, a[i:]...)...)
}

// Duration measuring wrapper
func (t TestInsertSlice) benchmark(f func()) func() time.Duration {
	return func() time.Duration {
		now := time.Now() // before code execution
		f()
		return time.Since(now)
	}
}

// Use for generating sample array
func (t TestInsertSlice) generate(N int) []int {
	var a []int
	for i := 0; i < N; i++ {
		a = append(a, rand.Intn(100))
	}
	return a
}

// Use for generating random insert operations
type InsertOp struct {
	Index int
	Value int
}

// Taxonomy for average insert to slice, measure every operation execution time, sum atomic operations durations,
// and divide by number of operations
func (t TestInsertSlice) testSliceInserts(opsSize int, arraySize int) time.Duration {
	arr := t.generate(arraySize)
	ops := []InsertOp{}
	for i := 0; i < opsSize; i++ {
		// Index: as insert increases array size, we should account for this by increasing the base for
		// random insert index generation
		// Value: insert random integer in range [0, 100)
		ops = append(ops, InsertOp{Index: rand.Intn(arraySize) + i, Value: rand.Intn(100)})
	}
	var d time.Duration
	for _, op := range ops {
		d = d + t.benchmark(func() {
			arr = insert(arr, op.Value, op.Index)
		})()
	}
	var avg time.Duration = time.Duration(int64(float64(d) / float64(opsSize)))
	fmt.Printf("Test array size: %d, insert ops: %d, avg time spent inserting: %s\n",
		arraySize, opsSize, avg.String())
	return avg
}

// Taxonomy for average insert to slice v2.0, measure total execution time and divide by number of operations
func (t TestInsertSlice) testSliceInserts2(opsSize int, arraySize int) time.Duration {
	arr := t.generate(arraySize)
	ops := []InsertOp{}
	for i := 0; i < opsSize; i++ {
		// Index: as insert increases array size, we should account for this by increasing the base for
		// random insert index generation
		// Value: insert random integer in range [0, 100)
		ops = append(ops, InsertOp{Index: rand.Intn(arraySize) + i, Value: rand.Intn(100)})
	}
	d := t.benchmark(func() {
		for _, op := range ops {
			arr = insert(arr, op.Value, op.Index)
		}
	})()
	var avg time.Duration = time.Duration(int64(float64(d) / float64(opsSize)))
	fmt.Printf("Test array size: %d, insert ops: %d, avg time spent inserting: %s\n",
		arraySize, opsSize, avg.String())
	return avg
}

// Struct for storing expriments info
type DataPoint struct {
	Avg time.Duration
	N   int
}

// Generate observations, run regression test, plot observation on image & save it in current folder
func (t TestInsertSlice) buildModel() {

	ns := []int{10, 100, 200,
		300, 400, 500,
		600, 700, 800,
		1_000, 2_000, 3_000,
		5_000, 10_000, 20_000,
		30_000, 40_000, 50_000,
		100_000, 150_000, 200_000,
	}

	methodTitle := "method1"
	fmt.Println("\n\n\n=== " + methodTitle + " ===")
	fmt.Println("\n=== Observations generation ===")

	obs := []DataPoint{}
	for _, N := range ns {
		obs = append(obs, DataPoint{Avg: t.testSliceInserts(1000, N), N: N})
	}
	t.runRegression(obs)
	t.plotObs(obs, methodTitle)

	methodTitle = "method2"
	fmt.Println("\n\n\n=== " + methodTitle + " ===")
	obs = []DataPoint{}
	for _, N := range ns {
		obs = append(obs, DataPoint{Avg: t.testSliceInserts2(1000, N), N: N})
	}

	fmt.Println("\n=== Running regression ===")
	t.runRegression(obs)

	fmt.Println("\n=== Plotting observations ===")
	t.plotObs(obs, methodTitle)
}

func (t TestInsertSlice) runRegression(obs []DataPoint) {
	r := new(regression.Regression)
	r.SetObserved("Avg time spent inserting element in the array")
	r.SetVar(0, "N, size of array")
	dp := regression.DataPoints{}
	for _, o := range obs {
		dp = append(dp, regression.DataPoint(float64(o.Avg), []float64{float64(o.N)}))
	}
	r.Train(dp...)
	r.Run()

	fmt.Printf("Regression formula:\n%v\n", r.Formula)
	fmt.Printf("Regression:\n%s\n", r)
	c := r.GetCoeffs()
	fmt.Printf("Model coefficients %v", c)
}

func (t TestInsertSlice) plotObs(vs []DataPoint, title string) {
	p := plot.New()
	p.Title.Text = title + ":avg_nano_time_per_insert(arr_size)"

	points := plotter.XYs{}
	for _, v := range vs {
		points = append(points, plotter.XY{X: float64(v.N), Y: float64(v.Avg)})
	}

	scatter, err := plotter.NewScatter(points)

	if err != nil {
		panic(err)
	}
	p.Add(scatter)

	if err := p.Save(3*vg.Inch, 3*vg.Inch, "test_insert_slice_"+title+".png"); err != nil {
		panic(err)
	}
}

func main() {
	t := TestInsertSlice{}
	t.buildModel()
}