slices: amortize allocations in Insert

[Deleplace]

What version of Go are you using (go version)?

$ go version
go version go1.19 darwin/amd64

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

go env Output

$ go env
GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOCACHE="/Users/deleplace/Library/Caches/go-build"
GOENV="/Users/deleplace/Library/Application Support/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="darwin"
GOINSECURE=""
GOMODCACHE="/Users/deleplace/go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="darwin"
GOPATH="/Users/deleplace/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/usr/local/go"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/usr/local/go/pkg/tool/darwin_amd64"
GOVCS=""
GOVERSION="go1.19"
GCCGO="gccgo"
GOAMD64="v1"
AR="ar"
CC="clang"
CXX="clang++"
CGO_ENABLED="1"
GOMOD="/Users/deleplace/Documents/2022/09/08/insert/go.mod"
GOWORK=""
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -arch x86_64 -m64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/p4/g7fnpss96g5708_mmv3cxzgh0000gn/T/go-build3158111282=/tmp/go-build -gno-record-gcc-switches -fno-common"

What did you do?

I benchmarked calling slices.Insert at index 0 in a loop: https://gist.github.com/Deleplace/0544f0681912348666ee48e2d55bc58d

What did you expect to see?

I expected slices.Insert to have a total cost O(N^2) to insert N element one by one (because it needs to shift all elements to the right each time), and to perform only O(log N) memory allocation operations, like append.

What did you see instead?

slices.Insert is O(N^2) but its cost is dominated by memory allocation. It does O(N) allocs.

The current strategy when inserting 1 element is to grow the slice capacity by only 1, as corroborated by the current implementation, this comment and this tweet.

I suggest we implement an allocation strategy similar to append's strategy that implements a dynamic array, for 2 reasons:

• It is more efficient. We do expect to be using slices.Insert to insert many elements, but we can't expect them all to be available all at once, or to be all inserted at the same index.
• The performance characteristics of its behaviour would be less surprising for the developers who know that slices are dynamic array, and have append in mind.

[mknyszek]

CC @ianlancetaylor

[gopherbot]

Change https://go.dev/cl/484159 mentions this issue: slices: amortize allocations in Insert