Snippet detailing the performance differences between Go stdlibs and the `insertion-queue` package

insertion_queue_perf.go

package main

import (
	"fmt"
	"math/rand"
	"os"
	"sort"
	"text/tabwriter"
	"time"

	iq "github.com/madz-lab/insertion-queue"
)

type stdLib []iq.Item

func (s stdLib) Len() int           { return len(s) }
func (s stdLib) Less(i, j int) bool { return s[i].Less(s[j]) }
func (s stdLib) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }

func (m *stdLib) Push(item iq.Item) {
	*m = append(*m, item)
	sort.Sort(m)
}

type queue interface {
	Push(iq.Item)
}

type number struct {
	value int
}

func (i number) Less(other iq.Item) bool {
	return i.value < other.(*number).value
}

// generateRandomItems generates a random item set
func generateRandomItems(count int) []*number {
	var (
		r     = rand.New(rand.NewSource(time.Now().UnixNano()))
		items = make([]*number, count)
	)

	for i := 0; i < count; i++ {
		items[i] = &number{
			value: r.Intn(100),
		}
	}

	return items
}

func measureCommon(
	q queue,
	items []*number,
	numIterations int,
) float64 {
	sumTime := float64(0)

	for i := 0; i < numIterations; i++ {
		start := time.Now()
		for _, item := range items {
			q.Push(item)
		}

		sumTime += time.Since(start).Seconds()
	}

	return sumTime / float64(numIterations)
}

func measureInsertionQueue(items []*number, numIterations int) float64 {
	q := iq.NewQueue()

	return measureCommon(&q, items, numIterations)
}

func measureStdLib(items []*number, numIterations int) float64 {
	q := make(stdLib, 0)

	return measureCommon(&q, items, numIterations)
}

func main() {
	const (
		numIterations = 100
		outputFormat  = "%s\t%.5f\n"
	)

	numItemsTable := []int{
		100,
		1000,
	}

	w := tabwriter.NewWriter(
		os.Stdout,
		10,
		10,
		2,
		' ',
		0,
	)

	for _, numItems := range numItemsTable {
		_, _ = fmt.Fprint(w, "\n==================\n")
		_, _ = fmt.Fprintf(w, "\nItems: %d\n", numItems)
		_, _ = fmt.Fprintf(w, "Iterations: %d\n", numIterations)
		_, _ = fmt.Fprint(w, "Name\tTime [s]\n")

		items := generateRandomItems(numItems)

		lib := measureInsertionQueue(items, numIterations)
		stdLib := measureStdLib(items, numIterations)

		_, _ = fmt.Fprintf(
			w,
			outputFormat,
			"insertion-queue",
			lib,
		)

		_, _ = fmt.Fprintf(
			w,
			outputFormat,
			"stdlib",
			stdLib,
		)

		_ = w.Flush()

		if lib < stdLib {
			fmt.Printf("\ninsertion-queue is faster by %.5fs\n", stdLib-lib)

			continue
		}

		fmt.Printf("\nstd-lib is faster by %.5fs\n", lib-stdLib)
	}
}

==================

Items: 100
Iterations: 100
Name             Time [s]
insertion-queue  0.00137
stdlib           0.00404

insertion-queue is faster by 0.00267s

==================

Items: 1000
Iterations: 100
Name             Time [s]
insertion-queue  0.13429
stdlib           0.41784

insertion-queue is faster by 0.28356s