Benchmark for Generic go-immutable-radix

go.mod

module github.com/shoenig/iradix-bench

go 1.18

require (
	github.com/hashicorp/go-immutable-radix v1.3.1
	github.com/hashicorp/go-immutable-radix/v2 v2.0.0-20220715140122-1c6d3ab901ca
	github.com/hashicorp/go-uuid v1.0.3
	golang.org/x/exp v0.0.0-20220713135740-79cabaa25d75
)

require github.com/hashicorp/golang-lru v0.5.4 // indirect

iradix-bench.go

package main

import (
	"encoding/binary"
	"fmt"
	"io"
	"os"
	"runtime"
	"sort"
	"time"

	v1 "github.com/hashicorp/go-immutable-radix"
	v2 "github.com/hashicorp/go-immutable-radix/v2"
	"github.com/hashicorp/go-uuid"
	"golang.org/x/exp/constraints"
)

func main() {
	// interesting to tinker with, but most programs use defaults
	// runtime.GOMAXPROCS(1)
	// debug.SetGCPercent(-1)
	// runtime.LockOSThread()

	bench := create()

	for _, n := range []int{1e3, 1e4, 1e5, 1e6} {
		bench.run(n, "byte", insertions[byte](n, makeNumeric[byte](n)))
		bench.run(n, "int64", insertions[int64](n, makeNumeric[int64](n)))
		bench.run(n, "string", insertions[string](n, makeUUIDs(n)))
		bench.run(n, "employee", insertions[employee](n, makeEmployees(n)))

		bench.run(n, "byte", iterate[byte](n, makeNumeric[byte](n)))
		bench.run(n, "int64", iterate[int64](n, makeNumeric[int64](n)))
		bench.run(n, "string", iterate[string](n, makeUUIDs(n)))
		bench.run(n, "employee", iterate[employee](n, makeEmployees(n)))
	}

	bench.output(os.Stdout)
}

type result struct {
	v1 time.Duration
	v2 time.Duration
}

func (r result) String() string {
	delta := r.v2 - r.v1
	percent := 100 * float64(delta.Nanoseconds()) / float64(r.v1.Nanoseconds())
	s := fmt.Sprintf("%4.2f%%", percent)
	return fmt.Sprintf("%12s %12s %12s %8s", r.v1, r.v2, delta, s)
}

type test struct {
	size     int
	typ      string
	scenario string
}

func (t test) String() string {
	return fmt.Sprintf("%10s %-8s %7d", t.scenario, t.typ, t.size)
}

type benchmark map[test]result

func create() benchmark {
	return make(benchmark, 0)
}

func (b benchmark) run(size int, typ string, f func() (string, time.Duration, time.Duration)) {
	scenario, v1dur, v2dur := f()
	tc := test{size: size, typ: typ, scenario: scenario}
	b[tc] = result{
		v1: v1dur,
		v2: v2dur,
	}
	runtime.GC()
}

func (b benchmark) output(w io.Writer) {
	tests := make([]test, 0, len(b))

	for t := range b {
		tests = append(tests, t)
	}

	sort.Slice(tests, func(a, b int) bool {
		A := tests[a]
		B := tests[b]

		if A.scenario < B.scenario {
			return true
		} else if A.scenario > B.scenario {
			return false
		}

		if A.typ < B.typ {
			return true
		} else if A.typ > B.typ {
			return false
		}

		return A.size < B.size
	})

	header := fmt.Sprintf(
		"%-10s %-8s %7s %12s %12s %12s %8s\n",
		"Scenario", "Type", "Size", "V1", "V2", "Delta", "Pct",
	)
	_, _ = io.WriteString(w, header)
	for _, t := range tests {
		r := b[t]
		s := fmt.Sprintf("%s %s\n", t, r)
		_, _ = io.WriteString(w, s)
	}
}

func insertions[T any](n int, values []T) func() (string, time.Duration, time.Duration) {
	keys := makeKeys(n)

	return func() (string, time.Duration, time.Duration) {
		r1 := v1.New()
		r2 := v2.New[T]()

		r1start := time.Now()
		for i := 0; i < n; i++ {
			r1.Insert(keys[i], values[i])
		}
		r1stop := time.Now()

		r2start := time.Now()
		for i := 0; i < n; i++ {
			r2.Insert(keys[i], values[i])
		}
		r2stop := time.Now()

		return "insertion", r1stop.Sub(r1start), r2stop.Sub(r2start)
	}
}

func iterate[T any](n int, values []T) func() (string, time.Duration, time.Duration) {
	keys := makeKeys(n)

	return func() (string, time.Duration, time.Duration) {
		r1 := v1.New()
		r2 := v2.New[T]()

		tx1 := r1.Txn()
		tx2 := r2.Txn()

		for i := 0; i < n; i++ {
			_, _ = tx1.Insert(keys[i], values[i])
			_, _ = tx2.Insert(keys[i], values[i])
		}

		r1 = tx1.Commit()
		r2 = tx2.Commit()

		iter1 := r1.Root().Iterator()
		iter2 := r2.Root().Iterator()

		r1start := time.Now()
		for {
			_, _, more := iter1.Next()
			if !more {
				break
			}
		}
		r1stop := time.Now()

		r2start := time.Now()
		for {
			_, _, more := iter2.Next()
			if !more {
				break
			}
		}
		r2stop := time.Now()

		return "iterate", r1stop.Sub(r1start), r2stop.Sub(r2start)
	}
}

func makeKeys(n int) [][]byte {
	keys := make([][]byte, n, n)
	for i := 0; i < n; i++ {
		keys[i] = make([]byte, 8, 8)
		binary.LittleEndian.PutUint64(keys[i], uint64(i))
	}
	return keys
}

func makeNumeric[T constraints.Integer](n int) []T {
	values := make([]T, n, n)
	for i := 0; i < n; i++ {
		values[i] = T(i)
	}
	return values
}

func makeUUIDs(n int) []string {
	values := make([]string, n, n)
	for i := 0; i < n; i++ {
		id, err := uuid.GenerateUUID()
		if err != nil {
			panic(err)
		}
		values[i] = string(id)
	}
	return values
}

type employee struct {
	id    int
	name  string
	title string
}

func makeEmployees(n int) []employee {
	values := make([]employee, n, n)
	for i := 0; i < n; i++ {
		values[i] = employee{
			id:    i,
			name:  fmt.Sprintf("name %d", i),
			title: fmt.Sprintf("title %d", i),
		}
	}
	return values
}