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/arrow-go.git
The following commit(s) were added to refs/heads/main by this push:
new ff7bd5a1 perf(arrow/array): avoid temporary slices in Diff comparisons
(#1239)
ff7bd5a1 is described below
commit ff7bd5a11263f840fe42cc268f02e7c2aaefe215
Author: Minh Vu <[email protected]>
AuthorDate: Fri Aug 28 16:55:11 2026 +0200
perf(arrow/array): avoid temporary slices in Diff comparisons (#1239)
### Rationale for this change
`array.Diff` compares each matching pair by calling `SliceEqual` on two
one-element slices. This creates temporary Arrow arrays for every
non-null comparison.
### What changes are included in this PR?
- Resolve a value comparator once when the Myers diff is created.
- Compare booleans, integers, temporal values, strings, and binary
values directly.
- Keep floating-point, decimal, interval, and nested values on the
existing `SliceEqual` fallback.
- Preserve the existing null handling.
- Add offset and null coverage for the direct comparison paths.
- Add benchmarks for equal arrays and a change at the end of the input.
Apple M1 Pro results with `GOMAXPROCS=1` and 65,536 values:
| Case | Before | After |
| --- | ---: | ---: |
| Int64 equal | 18.4 ms | 0.65 ms |
| Int64 changed last | 18.5 ms | 0.60 ms |
| String equal | 20.3 ms | 0.74 ms |
| String changed last | 20.5 ms | 0.73 ms |
| Binary equal | 21.8 ms | 0.82 ms |
| Binary changed last | 22.6 ms | 0.84 ms |
The equal cases go from 262,147 allocations to 4 allocations per
operation.
### Are these changes tested?
- `go test ./...`
- `go test -race ./arrow/array`
- `go vet -composites=false ./arrow/array`
### Are there any user-facing changes?
No.
---
arrow/array/diff.go | 78 +++++++++++++++
arrow/array/diff_benchmark_test.go | 165 ++++++++++++++++++++++++++++++++
arrow/array/diff_direct_compare_test.go | 159 ++++++++++++++++++++++++++++++
3 files changed, 402 insertions(+)
diff --git a/arrow/array/diff.go b/arrow/array/diff.go
index d7b26062..7de43514 100644
--- a/arrow/array/diff.go
+++ b/arrow/array/diff.go
@@ -17,6 +17,7 @@
package array
import (
+ "bytes"
"fmt"
"strings"
@@ -140,6 +141,7 @@ type editPoint struct {
type quadraticSpaceMyersDiff struct {
base arrow.Array
target arrow.Array
+ valueEqual func(baseIndex, targetIndex int) bool
finishIndex int
editCount int
endpointBase []int
@@ -154,6 +156,7 @@ func newQuadraticSpaceMyersDiff(base, target arrow.Array)
*quadraticSpaceMyersDi
d := &quadraticSpaceMyersDiff{
base: base,
target: target,
+ valueEqual: newDiffValueEqual(base, target),
finishIndex: -1,
editCount: 0,
endpointBase: []int{},
@@ -177,9 +180,84 @@ func (d *quadraticSpaceMyersDiff) valuesEqual(baseIndex,
targetIndex int) bool {
if baseNull || targetNull {
return baseNull && targetNull
}
+ if d.valueEqual != nil {
+ return d.valueEqual(baseIndex, targetIndex)
+ }
return SliceEqual(d.base, int64(baseIndex), int64(baseIndex+1),
d.target, int64(targetIndex), int64(targetIndex+1))
}
+func newDiffValueEqual(base, target arrow.Array) func(baseIndex, targetIndex
int) bool {
+ switch base.DataType().ID() {
+ case arrow.BOOL:
+ return makeDiffValueEqual[bool](base, target)
+ case arrow.INT8:
+ return makeDiffValueEqual[int8](base, target)
+ case arrow.INT16:
+ return makeDiffValueEqual[int16](base, target)
+ case arrow.INT32:
+ return makeDiffValueEqual[int32](base, target)
+ case arrow.INT64:
+ return makeDiffValueEqual[int64](base, target)
+ case arrow.UINT8:
+ return makeDiffValueEqual[uint8](base, target)
+ case arrow.UINT16:
+ return makeDiffValueEqual[uint16](base, target)
+ case arrow.UINT32:
+ return makeDiffValueEqual[uint32](base, target)
+ case arrow.UINT64:
+ return makeDiffValueEqual[uint64](base, target)
+ case arrow.DATE32:
+ return makeDiffValueEqual[arrow.Date32](base, target)
+ case arrow.DATE64:
+ return makeDiffValueEqual[arrow.Date64](base, target)
+ case arrow.TIME32:
+ return makeDiffValueEqual[arrow.Time32](base, target)
+ case arrow.TIME64:
+ return makeDiffValueEqual[arrow.Time64](base, target)
+ case arrow.TIMESTAMP:
+ return makeDiffValueEqual[arrow.Timestamp](base, target)
+ case arrow.DURATION:
+ return makeDiffValueEqual[arrow.Duration](base, target)
+ case arrow.STRING, arrow.LARGE_STRING:
+ return makeDiffValueEqual[string](base, target)
+ case arrow.BINARY, arrow.LARGE_BINARY, arrow.FIXED_SIZE_BINARY:
+ return makeDiffBytesEqual(base, target)
+ default:
+ return nil
+ }
+}
+
+func makeDiffValueEqual[T interface {
+ arrow.ValueType
+ comparable
+}](base, target arrow.Array) func(int, int) bool {
+ left, ok := base.(arrow.TypedArray[T])
+ if !ok {
+ return nil
+ }
+ right, ok := target.(arrow.TypedArray[T])
+ if !ok {
+ return nil
+ }
+ return func(baseIndex, targetIndex int) bool {
+ return left.Value(baseIndex) == right.Value(targetIndex)
+ }
+}
+
+func makeDiffBytesEqual(base, target arrow.Array) func(int, int) bool {
+ left, ok := base.(arrow.TypedArray[[]byte])
+ if !ok {
+ return nil
+ }
+ right, ok := target.(arrow.TypedArray[[]byte])
+ if !ok {
+ return nil
+ }
+ return func(baseIndex, targetIndex int) bool {
+ return bytes.Equal(left.Value(baseIndex),
right.Value(targetIndex))
+ }
+}
+
// increment the position within base and target (the elements skipped in this
way were
// present in both sequences)
func (d *quadraticSpaceMyersDiff) extendFrom(p editPoint) editPoint {
diff --git a/arrow/array/diff_benchmark_test.go
b/arrow/array/diff_benchmark_test.go
new file mode 100644
index 00000000..8d93a909
--- /dev/null
+++ b/arrow/array/diff_benchmark_test.go
@@ -0,0 +1,165 @@
+// 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 array_test
+
+import (
+ "testing"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/array"
+ "github.com/apache/arrow-go/v18/arrow/memory"
+)
+
+var diffBenchmarkEdits array.Edits
+
+func benchmarkInt64Arrays(n int, changed bool) (base, target *array.Int64) {
+ values := make([]int64, n)
+ for i := range values {
+ values[i] = int64(i)
+ }
+ targetValues := append([]int64(nil), values...)
+ if changed {
+ targetValues[n-1]++
+ }
+
+ baseBuilder := array.NewInt64Builder(memory.DefaultAllocator)
+ baseBuilder.AppendValues(values, nil)
+ base = baseBuilder.NewInt64Array()
+ baseBuilder.Release()
+
+ targetBuilder := array.NewInt64Builder(memory.DefaultAllocator)
+ targetBuilder.AppendValues(targetValues, nil)
+ target = targetBuilder.NewInt64Array()
+ targetBuilder.Release()
+ return
+}
+
+func benchmarkStringArrays(n int, changed bool) (base, target *array.String) {
+ values := make([]string, n)
+ for i := range values {
+ values[i] = "value"
+ }
+ targetValues := append([]string(nil), values...)
+ if changed {
+ targetValues[n-1] = "other"
+ }
+
+ baseBuilder := array.NewStringBuilder(memory.DefaultAllocator)
+ baseBuilder.AppendValues(values, nil)
+ base = baseBuilder.NewStringArray()
+ baseBuilder.Release()
+
+ targetBuilder := array.NewStringBuilder(memory.DefaultAllocator)
+ targetBuilder.AppendValues(targetValues, nil)
+ target = targetBuilder.NewStringArray()
+ targetBuilder.Release()
+ return
+}
+
+func benchmarkBinaryArrays(n int, changed bool) (base, target *array.Binary) {
+ values := make([][]byte, n)
+ for i := range values {
+ values[i] = []byte("value")
+ }
+ targetValues := append([][]byte(nil), values...)
+ if changed {
+ targetValues[n-1] = []byte("other")
+ }
+
+ baseBuilder := array.NewBinaryBuilder(memory.DefaultAllocator,
arrow.BinaryTypes.Binary)
+ baseBuilder.AppendValues(values, nil)
+ base = baseBuilder.NewBinaryArray()
+ baseBuilder.Release()
+
+ targetBuilder := array.NewBinaryBuilder(memory.DefaultAllocator,
arrow.BinaryTypes.Binary)
+ targetBuilder.AppendValues(targetValues, nil)
+ target = targetBuilder.NewBinaryArray()
+ targetBuilder.Release()
+ return
+}
+
+func BenchmarkDiffInt64Equal(b *testing.B) {
+ base, target := benchmarkInt64Arrays(65536, false)
+ defer base.Release()
+ defer target.Release()
+
+ b.ReportAllocs()
+ b.ResetTimer()
+ for range b.N {
+ diffBenchmarkEdits, _ = array.Diff(base, target)
+ }
+}
+
+func BenchmarkDiffInt64ChangedLast(b *testing.B) {
+ base, target := benchmarkInt64Arrays(65536, true)
+ defer base.Release()
+ defer target.Release()
+
+ b.ReportAllocs()
+ b.ResetTimer()
+ for range b.N {
+ diffBenchmarkEdits, _ = array.Diff(base, target)
+ }
+}
+
+func BenchmarkDiffStringEqual(b *testing.B) {
+ base, target := benchmarkStringArrays(65536, false)
+ defer base.Release()
+ defer target.Release()
+
+ b.ReportAllocs()
+ b.ResetTimer()
+ for range b.N {
+ diffBenchmarkEdits, _ = array.Diff(base, target)
+ }
+}
+
+func BenchmarkDiffStringChangedLast(b *testing.B) {
+ base, target := benchmarkStringArrays(65536, true)
+ defer base.Release()
+ defer target.Release()
+
+ b.ReportAllocs()
+ b.ResetTimer()
+ for range b.N {
+ diffBenchmarkEdits, _ = array.Diff(base, target)
+ }
+}
+
+func BenchmarkDiffBinaryEqual(b *testing.B) {
+ base, target := benchmarkBinaryArrays(65536, false)
+ defer base.Release()
+ defer target.Release()
+
+ b.ReportAllocs()
+ b.ResetTimer()
+ for range b.N {
+ diffBenchmarkEdits, _ = array.Diff(base, target)
+ }
+}
+
+func BenchmarkDiffBinaryChangedLast(b *testing.B) {
+ base, target := benchmarkBinaryArrays(65536, true)
+ defer base.Release()
+ defer target.Release()
+
+ b.ReportAllocs()
+ b.ResetTimer()
+ for range b.N {
+ diffBenchmarkEdits, _ = array.Diff(base, target)
+ }
+}
diff --git a/arrow/array/diff_direct_compare_test.go
b/arrow/array/diff_direct_compare_test.go
new file mode 100644
index 00000000..d969c543
--- /dev/null
+++ b/arrow/array/diff_direct_compare_test.go
@@ -0,0 +1,159 @@
+// 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 array_test
+
+import (
+ "testing"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/array"
+ "github.com/apache/arrow-go/v18/arrow/memory"
+)
+
+func TestDiff_DirectComparisonsWithOffsets(t *testing.T) {
+ cases := []struct {
+ name string
+ build func(memory.Allocator) (arrow.Array, arrow.Array)
+ }{
+ {
+ name: "int64",
+ build: func(mem memory.Allocator) (arrow.Array,
arrow.Array) {
+ valid := []bool{true, true, false, true, true,
true}
+ baseBuilder := array.NewInt64Builder(mem)
+ baseBuilder.AppendValues([]int64{0, 1, 2, 3, 5,
6}, valid)
+ base := baseBuilder.NewInt64Array()
+ baseBuilder.Release()
+
+ targetBuilder := array.NewInt64Builder(mem)
+ targetBuilder.AppendValues([]int64{10, 1, 2, 4,
5, 60}, valid)
+ target := targetBuilder.NewInt64Array()
+ targetBuilder.Release()
+ return base, target
+ },
+ },
+ {
+ name: "boolean",
+ build: func(mem memory.Allocator) (arrow.Array,
arrow.Array) {
+ valid := []bool{true, true, false, true, true,
true}
+ baseBuilder := array.NewBooleanBuilder(mem)
+ baseBuilder.AppendValues([]bool{false, true,
false, true, false, true}, valid)
+ base := baseBuilder.NewBooleanArray()
+ baseBuilder.Release()
+
+ targetBuilder := array.NewBooleanBuilder(mem)
+ targetBuilder.AppendValues([]bool{true, true,
true, false, false, false}, valid)
+ target := targetBuilder.NewBooleanArray()
+ targetBuilder.Release()
+ return base, target
+ },
+ },
+ {
+ name: "string",
+ build: func(mem memory.Allocator) (arrow.Array,
arrow.Array) {
+ valid := []bool{true, true, false, true, true,
true}
+ baseBuilder := array.NewStringBuilder(mem)
+ baseBuilder.AppendValues([]string{"before",
"one", "ignored", "three", "five", "after"}, valid)
+ base := baseBuilder.NewStringArray()
+ baseBuilder.Release()
+
+ targetBuilder := array.NewStringBuilder(mem)
+ targetBuilder.AppendValues([]string{"before",
"one", "unused", "four", "five", "after"}, valid)
+ target := targetBuilder.NewStringArray()
+ targetBuilder.Release()
+ return base, target
+ },
+ },
+ {
+ name: "binary",
+ build: func(mem memory.Allocator) (arrow.Array,
arrow.Array) {
+ valid := []bool{true, true, false, true, true,
true}
+ baseBuilder := array.NewBinaryBuilder(mem,
arrow.BinaryTypes.Binary)
+ baseBuilder.AppendValues([][]byte{
+ []byte("before"), []byte("one"),
[]byte("ignored"), []byte("three"), []byte("five"), []byte("after"),
+ }, valid)
+ base := baseBuilder.NewBinaryArray()
+ baseBuilder.Release()
+
+ targetBuilder := array.NewBinaryBuilder(mem,
arrow.BinaryTypes.Binary)
+ targetBuilder.AppendValues([][]byte{
+ []byte("before"), []byte("one"),
[]byte("unused"), []byte("four"), []byte("five"), []byte("after"),
+ }, valid)
+ target := targetBuilder.NewBinaryArray()
+ targetBuilder.Release()
+ return base, target
+ },
+ },
+ {
+ name: "large_string",
+ build: func(mem memory.Allocator) (arrow.Array,
arrow.Array) {
+ valid := []bool{true, true, false, true, true,
true}
+ baseBuilder := array.NewLargeStringBuilder(mem)
+ baseBuilder.AppendValues([]string{"before",
"one", "ignored", "three", "five", "after"}, valid)
+ base := baseBuilder.NewLargeStringArray()
+ baseBuilder.Release()
+
+ targetBuilder :=
array.NewLargeStringBuilder(mem)
+ targetBuilder.AppendValues([]string{"before",
"one", "unused", "four", "five", "after"}, valid)
+ target := targetBuilder.NewLargeStringArray()
+ targetBuilder.Release()
+ return base, target
+ },
+ },
+ {
+ name: "large_binary",
+ build: func(mem memory.Allocator) (arrow.Array,
arrow.Array) {
+ valid := []bool{true, true, false, true, true,
true}
+ baseBuilder := array.NewBinaryBuilder(mem,
arrow.BinaryTypes.LargeBinary)
+ baseBuilder.AppendValues([][]byte{
+ []byte("before"), []byte("one"),
[]byte("ignored"), []byte("three"), []byte("five"), []byte("after"),
+ }, valid)
+ base := baseBuilder.NewLargeBinaryArray()
+ baseBuilder.Release()
+
+ targetBuilder := array.NewBinaryBuilder(mem,
arrow.BinaryTypes.LargeBinary)
+ targetBuilder.AppendValues([][]byte{
+ []byte("before"), []byte("one"),
[]byte("unused"), []byte("four"), []byte("five"), []byte("after"),
+ }, valid)
+ target := targetBuilder.NewLargeBinaryArray()
+ targetBuilder.Release()
+ return base, target
+ },
+ },
+ }
+
+ for _, tc := range cases {
+ t.Run(tc.name, func(t *testing.T) {
+ mem :=
memory.NewCheckedAllocator(memory.NewGoAllocator())
+ defer mem.AssertSize(t, 0)
+
+ baseFull, targetFull := tc.build(mem)
+ defer baseFull.Release()
+ defer targetFull.Release()
+
+ base := array.NewSlice(baseFull, 1, 5)
+ defer base.Release()
+ target := array.NewSlice(targetFull, 1, 5)
+ defer target.Release()
+
+ edits, err := array.Diff(base, target)
+ if err != nil {
+ t.Fatal(err)
+ }
+ validateEditScript(t, edits, base, target)
+ })
+ }
+}
