diff options
author | Ian Lance Taylor <iant@golang.org> | 2023-04-12 13:57:21 -0700 |
---|---|---|
committer | Gopher Robot <gobot@golang.org> | 2023-04-13 17:55:12 +0000 |
commit | 3de5b4da26b0062c9fd1b84849a0d4b7e78aaf5a (patch) | |
tree | 2f7bdd373b436e1b1c72d3cb881c6fba15f47ad7 /src/slices | |
parent | 74c296b69ffe07322b4bb42d7d2afe5f76ccf6ad (diff) | |
download | go-3de5b4da26b0062c9fd1b84849a0d4b7e78aaf5a.tar.gz go-3de5b4da26b0062c9fd1b84849a0d4b7e78aaf5a.zip |
slices: amortize allocations in Insert
Fixes #54948
Change-Id: I467afb940b539b100dcce687b05914a9da7b9ed2
Reviewed-on: https://go-review.googlesource.com/c/go/+/484159
Run-TryBot: Ian Lance Taylor <iant@google.com>
Reviewed-by: Bryan Mills <bcmills@google.com>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Auto-Submit: Ian Lance Taylor <iant@google.com>
Reviewed-by: Ian Lance Taylor <iant@google.com>
Reviewed-by: Valentin Deleplace <deleplace@google.com>
Diffstat (limited to 'src/slices')
-rw-r--r-- | src/slices/slices.go | 6 | ||||
-rw-r--r-- | src/slices/slices_test.go | 14 |
2 files changed, 19 insertions, 1 deletions
diff --git a/src/slices/slices.go b/src/slices/slices.go index ea1dea573c..4a35ec5c23 100644 --- a/src/slices/slices.go +++ b/src/slices/slices.go @@ -88,7 +88,11 @@ func Insert[S ~[]E, E any](s S, i int, v ...E) S { copy(s2[i:], v) return s2 } - s2 := make(S, tot) + // Use append rather than make so that we bump the size of + // the slice up to the next storage class. + // This is what Grow does but we don't call Grow because + // that might copy the values twice. + s2 := append(S(nil), make(S, tot)...) copy(s2, s[:i]) copy(s2[i:], v) copy(s2[i+len(v):], s[i:]) diff --git a/src/slices/slices_test.go b/src/slices/slices_test.go index 720e731ddf..0f3df43e06 100644 --- a/src/slices/slices_test.go +++ b/src/slices/slices_test.go @@ -256,6 +256,20 @@ func TestInsert(t *testing.T) { t.Errorf("Insert(%v, %d, %v...) = %v, want %v", test.s, test.i, test.add, got, test.want) } } + + if !testenv.OptimizationOff() && !race.Enabled { + // Allocations should be amortized. + const count = 50 + n := testing.AllocsPerRun(10, func() { + s := []int{1, 2, 3} + for i := 0; i < count; i++ { + s = Insert(s, 0, 1) + } + }) + if n > count/2 { + t.Errorf("too many allocations inserting %d elements: got %v, want less than %d", count, n, count/2) + } + } } var deleteTests = []struct { |