Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

x/exp/slices: amortize allocations in Insert #54948

Open
Deleplace opened this issue Sep 8, 2022 · 1 comment
Open

x/exp/slices: amortize allocations in Insert #54948

Deleplace opened this issue Sep 8, 2022 · 1 comment
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone

Comments

@Deleplace
Copy link

Deleplace commented Sep 8, 2022

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.
@gopherbot gopherbot added this to the Unreleased milestone Sep 8, 2022
@mknyszek
Copy link
Contributor

mknyszek commented Sep 8, 2022

CC @ianlancetaylor

@mknyszek mknyszek added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Sep 8, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
None yet
Development

No branches or pull requests

3 participants