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

Results on my workstation:

goos: darwin
goarch: amd64
pkg: insert
cpu: VirtualApple @ 2.50GHz
BenchmarkGrow/append_10-10         	 9669075	       127.1 ns/op
BenchmarkGrow/insert_10-10         	 3839758	       287.6 ns/op
BenchmarkGrow/append_1000-10       	  299048	      4041 ns/op
BenchmarkGrow/insert_1000-10       	    1543	    754534 ns/op
BenchmarkGrow/append_100000-10     	    1974	    552244 ns/op
BenchmarkGrow/insert_100000-10     	       1	5446765125 ns/op

When inserting a single element in each call, slices.Insert has O(N) cost per inserted element, and append has O(1) amortized cost per inserted element.

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.