Benchmark heavy use of append vs. heavy use of slices.Insert

insert_test.go

package insert

import (
	"fmt"
	"testing"

	"golang.org/x/exp/slices"
)

func BenchmarkGrow(b *testing.B) {
	for _, M := range []int{
		10,
		1_000,
		100_000,
	} {
		{
			name := fmt.Sprintf("append_%d", M)
			b.Run(name, func(b *testing.B) {
				for i := 0; i < b.N; i++ {
					var a []int
					for j := 0; j < M; j++ {
						a = append(a, 0)
					}
					Sink = a
				}
			})
		}

		{
			name := fmt.Sprintf("insert_%d", M)
			b.Run(name, func(b *testing.B) {
				for i := 0; i < b.N; i++ {
					var a []int
					for j := 0; j < M; j++ {
						a = slices.Insert(a, 0, 0)
					}
					Sink = a
				}
			})
		}
	}
}

// Prevent optimizing things away
var Sink []int

slices.Insert needs to be O(N) because it is shifting up to N elements to the right. However, it could do much fewer allocations, by doubling (or 1.25x-ing) capacity when needed, like append does.