slices: optimize Index and Compact for large types
Using `for i, v := range` loops causes extra copies.
Try to get rid of as much copies as possible.
│ old.txt~ │ new.txt~ │
│ sec/op │ sec/op vs base │
EqualFunc_Large-32 1.077m ± 1% 1.072m ± 1% ~ (p=0.631 n=10)
Index_Large-32 346.329µ ± 1% 6.510µ ± 24% -98.12% (p=0.000 n=10)
IndexFunc_Large-32 502.9µ ± 0% 381.2µ ± 1% -24.21% (p=0.000 n=10)
Compact_Large-32 409.5µ ± 1% 145.2µ ± 9% -64.54% (p=0.000 n=10)
CompactFunc_Large-32 693.5µ ± 1% 663.1µ ± 3% -4.39% (p=0.000 n=10)
geomean 556.3µ 191.3µ -65.61%
Change-Id: I187065ea32394b241951928bada7a698a9f45cd9
Reviewed-on: https://go-review.googlesource.com/c/exp/+/486735
Auto-Submit: Ian Lance Taylor <iant@google.com>
Reviewed-by: Dmitri Shuralyov <dmitshur@google.com>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Run-TryBot: Ian Lance Taylor <iant@google.com>
Reviewed-by: Ian Lance Taylor <iant@google.com>
diff --git a/slices/slices.go b/slices/slices.go
index cff0cd4..2540bd6 100644
--- a/slices/slices.go
+++ b/slices/slices.go
@@ -104,8 +104,8 @@
// Index returns the index of the first occurrence of v in s,
// or -1 if not present.
func Index[E comparable](s []E, v E) int {
- for i, vs := range s {
- if v == vs {
+ for i := range s {
+ if v == s[i] {
return i
}
}
@@ -115,8 +115,8 @@
// IndexFunc returns the first index i satisfying f(s[i]),
// or -1 if none do.
func IndexFunc[E any](s []E, f func(E) bool) int {
- for i, v := range s {
- if f(v) {
+ for i := range s {
+ if f(s[i]) {
return i
}
}
@@ -207,12 +207,12 @@
return s
}
i := 1
- last := s[0]
- for _, v := range s[1:] {
- if v != last {
- s[i] = v
+ for k := 1; k < len(s); k++ {
+ if s[k] != s[k-1] {
+ if i != k {
+ s[i] = s[k]
+ }
i++
- last = v
}
}
return s[:i]
@@ -224,12 +224,12 @@
return s
}
i := 1
- last := s[0]
- for _, v := range s[1:] {
- if !eq(v, last) {
- s[i] = v
+ for k := 1; k < len(s); k++ {
+ if !eq(s[k], s[k-1]) {
+ if i != k {
+ s[i] = s[k]
+ }
i++
- last = v
}
}
return s[:i]
diff --git a/slices/slices_test.go b/slices/slices_test.go
index 1d9ffd2..6ecd822 100644
--- a/slices/slices_test.go
+++ b/slices/slices_test.go
@@ -126,6 +126,16 @@
}
}
+func BenchmarkEqualFunc_Large(b *testing.B) {
+ type Large [4 * 1024]byte
+
+ xs := make([]Large, 1024)
+ ys := make([]Large, 1024)
+ for i := 0; i < b.N; i++ {
+ _ = EqualFunc(xs, ys, func(x, y Large) bool { return x == y })
+ }
+}
+
var compareIntTests = []struct {
s1, s2 []int
want int
@@ -334,6 +344,15 @@
}
}
+func BenchmarkIndex_Large(b *testing.B) {
+ type Large [4 * 1024]byte
+
+ ss := make([]Large, 1024)
+ for i := 0; i < b.N; i++ {
+ _ = Index(ss, Large{1})
+ }
+}
+
func TestIndexFunc(t *testing.T) {
for _, test := range indexTests {
if got := IndexFunc(test.s, equalToIndex(equal[int], test.v)); got != test.want {
@@ -350,6 +369,17 @@
}
}
+func BenchmarkIndexFunc_Large(b *testing.B) {
+ type Large [4 * 1024]byte
+
+ ss := make([]Large, 1024)
+ for i := 0; i < b.N; i++ {
+ _ = IndexFunc(ss, func(e Large) bool {
+ return e == Large{1}
+ })
+ }
+}
+
func TestContains(t *testing.T) {
for _, test := range indexTests {
if got := Contains(test.s, test.v); got != (test.want != -1) {
@@ -572,7 +602,15 @@
}
})
}
+}
+func BenchmarkCompact_Large(b *testing.B) {
+ type Large [4 * 1024]byte
+
+ ss := make([]Large, 1024)
+ for i := 0; i < b.N; i++ {
+ _ = Compact(ss)
+ }
}
func TestCompactFunc(t *testing.T) {
@@ -591,6 +629,15 @@
}
}
+func BenchmarkCompactFunc_Large(b *testing.B) {
+ type Large [4 * 1024]byte
+
+ ss := make([]Large, 1024)
+ for i := 0; i < b.N; i++ {
+ _ = CompactFunc(ss, func(a, b Large) bool { return a == b })
+ }
+}
+
func TestGrow(t *testing.T) {
s1 := []int{1, 2, 3}
