This is an automated email from the ASF dual-hosted git repository.
zeroshade pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/iceberg-go.git
The following commit(s) were added to refs/heads/main by this push:
new 982042f92 perf(internal): reduce string difference allocations (#2243)
982042f92 is described below
commit 982042f92fe11c621addfad84d94ff25742c4833
Author: Minh Vu <[email protected]>
AuthorDate: Wed Oct 21 22:44:31 2026 +0200
perf(internal): reduce string difference allocations (#2243)
* perf(internal): avoid map overhead in string differences
Signed-off-by: Minh Vu <[email protected]>
* perf(internal): pre-size difference result from input lengths
---------
Signed-off-by: Minh Vu <[email protected]>
---
internal/difference_perf_test.go | 69 ++++++++++++++++++++++++++++++++++++++++
internal/utils.go | 28 +++++++++++++---
2 files changed, 92 insertions(+), 5 deletions(-)
diff --git a/internal/difference_perf_test.go b/internal/difference_perf_test.go
new file mode 100644
index 000000000..2dfd20be1
--- /dev/null
+++ b/internal/difference_perf_test.go
@@ -0,0 +1,69 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package internal_test
+
+import (
+ "fmt"
+ "reflect"
+ "testing"
+
+ "github.com/apache/iceberg-go/internal"
+)
+
+func TestDifferenceFastPaths(t *testing.T) {
+ for _, tc := range []struct {
+ name string
+ a, b []string
+ want []string
+ }{
+ {name: "nil", want: []string{}},
+ {name: "empty input", b: []string{"a", "b", "c"}, want:
[]string{}},
+ {name: "no exclusions", a: []string{"b", "a", "a"}, want:
[]string{"b", "a", "a"}},
+ {name: "one exclusion", a: []string{"a", "b", "a", "c"}, b:
[]string{"a"}, want: []string{"b", "c"}},
+ {name: "two exclusions", a: []string{"a", "b", "c", "b", "d"},
b: []string{"b", "d"}, want: []string{"a", "c"}},
+ {name: "many exclusions", a: []string{"a", "b", "c", "d", "e",
"d"}, b: []string{"b", "d", "x", "d"}, want: []string{"a", "c", "e"}},
+ {name: "all excluded", a: []string{"a", "a"}, b: []string{"a"},
want: []string{}},
+ } {
+ t.Run(tc.name, func(t *testing.T) {
+ if got := internal.Difference(tc.a, tc.b);
!reflect.DeepEqual(got, tc.want) {
+ t.Fatalf("Difference(%v, %v) = %v, want %v",
tc.a, tc.b, got, tc.want)
+ }
+ })
+ }
+}
+
+var differenceBenchSink []string
+
+func BenchmarkDifference(b *testing.B) {
+ for _, size := range []int{1_024, 8_192} {
+ paths := make([]string, size)
+ for i := range paths {
+ paths[i] =
fmt.Sprintf("data/partition=%06d/file-%06d.parquet", i, i)
+ }
+ for _, excluded := range []int{0, 1, size / 2, size} {
+ b.Run(fmt.Sprintf("entries=%d/exclusions=%d", size,
excluded), func(b *testing.B) {
+ removed := paths[:excluded]
+ b.ReportAllocs()
+ b.ResetTimer()
+ for range b.N {
+ differenceBenchSink =
internal.Difference(paths, removed)
+ }
+ })
+ }
+ }
+}
diff --git a/internal/utils.go b/internal/utils.go
index ca9108f8b..c5de79771 100644
--- a/internal/utils.go
+++ b/internal/utils.go
@@ -84,14 +84,32 @@ func FloorDiv[T constraints.Integer](a, b T) T {
// Helper function to find the difference between two slices (a - b).
func Difference(a, b []string) []string {
- m := make(map[string]bool)
- for _, item := range b {
- m[item] = true
+ if len(a) == 0 {
+ return []string{}
+ }
+ if len(b) == 0 {
+ return append(make([]string, 0, len(a)), a...)
+ }
+ if len(b) <= 2 {
+ diff := make([]string, 0, len(a))
+ for _, item := range a {
+ if !slices.Contains(b, item) {
+ diff = append(diff, item)
+ }
+ }
+
+ return diff
}
- diff := make([]string, 0)
+ m := make(map[string]struct{}, len(b))
+ for _, item := range b {
+ m[item] = struct{}{}
+ }
+ // Leave room for the likely survivors without reserving for every
input.
+ // Append still handles duplicate entries and exclusions outside a.
+ diff := make([]string, 0, max(0, len(a)-len(b)))
for _, item := range a {
- if !m[item] {
+ if _, excluded := m[item]; !excluded {
diff = append(diff, item)
}
}
