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 f82b95de perf(arrow/array): compare approximate list values by valid
runs (#1330)
f82b95de is described below
commit f82b95de8195cc3e74040d516eb34b234fbbaae7
Author: Minh Vu <[email protected]>
AuthorDate: Tue Oct 6 16:24:31 2026 +0200
perf(arrow/array): compare approximate list values by valid runs (#1330)
## What
Speed up `ApproxEqual` for list arrays.
## Why
The old path created and released one child slice for every valid list
item. This is expensive for large arrays.
## Implementation
- Compare contiguous valid runs for `List`, `LargeList`, and
`FixedSizeList`.
- Reuse direct child comparison when a run covers the full child array.
- Keep concrete scalar fallbacks for fragmented validity bitmaps.
- Add coverage for full-range approximate slices and generic arrays.
- Add benchmark coverage for common null patterns.
## Benchmark
Apple M1 Pro, Go 1.26.3, `GOMAXPROCS=1`, 65,536 rows, Int32 child
values, list size 16. Median of 3 runs. Lower `ns/op` is better.
| Case | upstream/main | This PR | Speed | PR allocs/op |
| --- | ---: | ---: | ---: | ---: |
| list / all-valid | 17.8 ms | 0.197 ms | 90.5x | 2 |
| large-list / all-valid | 18.9 ms | 0.216 ms | 87.8x | 2 |
| fixed-size-list / all-valid | 18.0 ms | 0.145 ms | 124x | 2 |
| list / 10% null | 16.2 ms | 2.15 ms | 7.5x | 26,218 |
| list / clustered 10% null | 16.0 ms | 0.195 ms | 81.9x | 10 |
| list / alternating null | 8.72 ms | 8.71 ms | 1.00x, near parity |
131,074 |
---
arrow/array/compare.go | 162 ++++++++++++++++++++---------
arrow/array/compare_binary_builder_test.go | 60 +++++++++++
arrow/array/compare_test.go | 95 +++++++++++++++++
arrow/array/list_equal_benchmark_test.go | 33 ++++++
4 files changed, 303 insertions(+), 47 deletions(-)
diff --git a/arrow/array/compare.go b/arrow/array/compare.go
index 76e420e3..419add8c 100644
--- a/arrow/array/compare.go
+++ b/arrow/array/compare.go
@@ -379,8 +379,13 @@ func canEqualDirectly(left, right arrow.Array) bool {
}
switch left.(type) {
- case *Null, *Boolean, *FixedSizeBinary, *Binary, *String,
- *LargeBinary, *LargeString, *BinaryView, *StringView,
+ case *Binary:
+ // Binary builders can retain string datatypes, which need
normalization.
+ return left.DataType().ID() == arrow.BINARY &&
right.DataType().ID() == arrow.BINARY
+ case *LargeBinary:
+ return left.DataType().ID() == arrow.LARGE_BINARY &&
right.DataType().ID() == arrow.LARGE_BINARY
+ case *Null, *Boolean, *FixedSizeBinary, *String,
+ *LargeString, *BinaryView, *StringView,
*Int8, *Int16, *Int32, *Int64, *Uint8, *Uint16, *Uint32,
*Uint64,
*Float16, *Float32, *Float64,
*Decimal32, *Decimal64, *Decimal128, *Decimal256,
@@ -427,6 +432,79 @@ func arrayEqualListOffsets[T listOffset](leftValues,
rightValues arrow.Array,
}) == nil
}
+func arrayApproxEqualListOffsets[T listOffset](leftValues, rightValues
arrow.Array,
+ leftOffsets, rightOffsets []T, leftOffset, rightOffset, length int,
validBits []byte, opt equalOption) bool {
+ if len(validBits) == 0 {
+ validBits = nil
+ }
+ return bitutils.VisitSetBitRuns(validBits, int64(leftOffset),
int64(length),
+ func(pos, runLength int64) error {
+ leftIndex := leftOffset + int(pos)
+ rightIndex := rightOffset + int(pos)
+ for i := range int(runLength) {
+ leftLength := int64(leftOffsets[leftIndex+i+1])
- int64(leftOffsets[leftIndex+i])
+ rightLength :=
int64(rightOffsets[rightIndex+i+1]) - int64(rightOffsets[rightIndex+i])
+ if leftLength != rightLength {
+ return arrow.ErrInvalid
+ }
+ }
+
+ leftStart := int64(leftOffsets[leftIndex])
+ rightStart := int64(rightOffsets[rightIndex])
+ leftEnd := int64(leftOffsets[leftIndex+int(runLength)])
+ rightEnd :=
int64(rightOffsets[rightIndex+int(runLength)])
+ if !sliceApproxEqual(leftValues, leftStart, leftEnd,
rightValues, rightStart, rightEnd, opt) {
+ return arrow.ErrInvalid
+ }
+ return nil
+ }) == nil
+}
+
+type listArrayWithValue interface {
+ arrow.Array
+ newListValue(int) arrow.Array
+}
+
+func arrayApproxEqualListScalar(left, right listArrayWithValue, opt
equalOption) bool {
+ for i := 0; i < left.Len(); i++ {
+ if left.IsNull(i) {
+ continue
+ }
+ equal := func() bool {
+ l := left.newListValue(i)
+ defer l.Release()
+ r := right.newListValue(i)
+ defer r.Release()
+ return arrayApproxEqual(l, r, opt)
+ }()
+ if !equal {
+ return false
+ }
+ }
+ return true
+}
+
+func useScalarListEquality(validBits []byte, offset, length int64) bool {
+ if len(validBits) == 0 || length <= 64 {
+ return len(validBits) != 0
+ }
+
+ const (
+ sampleRuns = 8
+ minAverageRunLength = 4
+ )
+ runs := bitutils.NewSetBitRunReader(validBits, offset, length)
+ validValues := int64(0)
+ for range sampleRuns {
+ run := runs.NextRun()
+ if run.Length == 0 {
+ return false
+ }
+ validValues += run.Length
+ }
+ return validValues < sampleRuns*minAverageRunLength
+}
+
// SliceApproxEqual reports whether slices left[lbeg:lend] and
right[rbeg:rend] are approximately equal.
func SliceApproxEqual(left arrow.Array, lbeg, lend int64, right arrow.Array,
rbeg, rend int64, opts ...EqualOption) bool {
opt := newEqualOption(opts...)
@@ -434,6 +512,16 @@ func SliceApproxEqual(left arrow.Array, lbeg, lend int64,
right arrow.Array, rbe
}
func sliceApproxEqual(left arrow.Array, lbeg, lend int64, right arrow.Array,
rbeg, rend int64, opt equalOption) bool {
+ if lbeg == 0 && lend == int64(left.Len()) &&
+ rbeg == 0 && rend == int64(right.Len()) &&
+ canEqualDirectly(left, right) {
+ return arrayApproxEqual(left, right, opt)
+ }
+
+ return sliceApproxEqualDirect(left, lbeg, lend, right, rbeg, rend, opt)
+}
+
+func sliceApproxEqualDirect(left arrow.Array, lbeg, lend int64, right
arrow.Array, rbeg, rend int64, opt equalOption) bool {
l := NewSlice(left, lbeg, lend)
defer l.Release()
r := NewSlice(right, rbeg, rend)
@@ -795,41 +883,19 @@ func arrayApproxEqualFloat64(left, right *Float64, opt
equalOption) bool {
}
func arrayApproxEqualList(left, right *List, opt equalOption) bool {
- for i := 0; i < left.Len(); i++ {
- if left.IsNull(i) {
- continue
- }
- o := func() bool {
- l := left.newListValue(i)
- defer l.Release()
- r := right.newListValue(i)
- defer r.Release()
- return arrayApproxEqual(l, r, opt)
- }()
- if !o {
- return false
- }
+ if useScalarListEquality(left.NullBitmapBytes(), int64(left.Offset()),
int64(left.Len())) {
+ return arrayApproxEqualListScalar(left, right, opt)
}
- return true
+ return arrayApproxEqualListOffsets(left.values, right.values,
left.offsets, right.offsets,
+ left.data.offset, right.data.offset, left.Len(),
left.NullBitmapBytes(), opt)
}
func arrayApproxEqualLargeList(left, right *LargeList, opt equalOption) bool {
- for i := 0; i < left.Len(); i++ {
- if left.IsNull(i) {
- continue
- }
- o := func() bool {
- l := left.newListValue(i)
- defer l.Release()
- r := right.newListValue(i)
- defer r.Release()
- return arrayApproxEqual(l, r, opt)
- }()
- if !o {
- return false
- }
+ if useScalarListEquality(left.NullBitmapBytes(), int64(left.Offset()),
int64(left.Len())) {
+ return arrayApproxEqualListScalar(left, right, opt)
}
- return true
+ return arrayApproxEqualListOffsets(left.values, right.values,
left.offsets, right.offsets,
+ left.data.offset, right.data.offset, left.Len(),
left.NullBitmapBytes(), opt)
}
func arrayApproxEqualListView(left, right *ListView, opt equalOption) bool {
@@ -871,22 +937,24 @@ func arrayApproxEqualLargeListView(left, right
*LargeListView, opt equalOption)
}
func arrayApproxEqualFixedSizeList(left, right *FixedSizeList, opt
equalOption) bool {
- for i := 0; i < left.Len(); i++ {
- if left.IsNull(i) {
- continue
- }
- o := func() bool {
- l := left.newListValue(i)
- defer l.Release()
- r := right.newListValue(i)
- defer r.Release()
- return arrayApproxEqual(l, r, opt)
- }()
- if !o {
- return false
- }
+ if useScalarListEquality(left.NullBitmapBytes(), int64(left.Offset()),
int64(left.Len())) {
+ return arrayApproxEqualListScalar(left, right, opt)
}
- return true
+ listSize := int64(left.n)
+ validBits := left.NullBitmapBytes()
+ if len(validBits) == 0 {
+ validBits = nil
+ }
+ return bitutils.VisitSetBitRuns(validBits, int64(left.Offset()),
int64(left.Len()),
+ func(pos, length int64) error {
+ leftStart := (int64(left.Offset()) + pos) * listSize
+ rightStart := (int64(right.Offset()) + pos) * listSize
+ if !sliceApproxEqual(left.values, leftStart,
leftStart+length*listSize,
+ right.values, rightStart,
rightStart+length*listSize, opt) {
+ return arrow.ErrInvalid
+ }
+ return nil
+ }) == nil
}
func arrayApproxEqualStruct(left, right *Struct, opt equalOption) bool {
diff --git a/arrow/array/compare_binary_builder_test.go
b/arrow/array/compare_binary_builder_test.go
new file mode 100644
index 00000000..07977abe
--- /dev/null
+++ b/arrow/array/compare_binary_builder_test.go
@@ -0,0 +1,60 @@
+// 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"
+ "github.com/stretchr/testify/assert"
+)
+
+func TestSliceApproxEqualBinaryBuilderLogicalType(t *testing.T) {
+ for _, dtype := range []arrow.BinaryDataType{
+ arrow.BinaryTypes.Binary,
+ arrow.BinaryTypes.String,
+ arrow.BinaryTypes.LargeBinary,
+ arrow.BinaryTypes.LargeString,
+ } {
+ t.Run(dtype.Name(), func(t *testing.T) {
+ mem :=
memory.NewCheckedAllocator(memory.DefaultAllocator)
+ defer mem.AssertSize(t, 0)
+ builder := array.NewBinaryBuilder(mem, dtype)
+ defer builder.Release()
+ builder.AppendValues([][]byte{[]byte("a\x00"),
[]byte("same"), []byte("x\x00")}, nil)
+ left := builder.NewArray()
+ defer left.Release()
+ builder.AppendValues([][]byte{[]byte("a"),
[]byte("same"), []byte("x")}, nil)
+ right := builder.NewArray()
+ defer right.Release()
+
+ want := dtype.ID() == arrow.STRING || dtype.ID() ==
arrow.LARGE_STRING
+ assert.Equal(t, want, array.SliceApproxEqual(left, 0,
3, right, 0, 3))
+ assert.Equal(t, want, array.SliceApproxEqual(right, 0,
3, left, 0, 3))
+ assert.Equal(t, want, array.SliceApproxEqual(left, 0,
1, right, 0, 1))
+ assert.True(t, array.SliceApproxEqual(left, 1, 2,
right, 1, 2))
+ assert.False(t, array.SliceEqual(left, 0, 3, right, 0,
3))
+
+ normalized := array.MakeFromData(right.Data())
+ defer normalized.Release()
+ assert.Equal(t, want, array.SliceApproxEqual(left, 0,
3, normalized, 0, 3))
+ assert.Equal(t, want,
array.SliceApproxEqual(normalized, 0, 3, left, 0, 3))
+ })
+ }
+}
diff --git a/arrow/array/compare_test.go b/arrow/array/compare_test.go
index f7af93c9..60e49fb2 100644
--- a/arrow/array/compare_test.go
+++ b/arrow/array/compare_test.go
@@ -149,6 +149,49 @@ func TestArraySliceEqualFullRangeMismatchedConcreteTypes(t
*testing.T) {
))
}
+func TestArraySliceApproxEqualFullRange(t *testing.T) {
+ leftBuilder := array.NewFloat64Builder(memory.DefaultAllocator)
+ leftBuilder.AppendValues([]float64{1, 2, 3}, nil)
+ left := leftBuilder.NewFloat64Array()
+ leftBuilder.Release()
+ defer left.Release()
+
+ rightBuilder := array.NewFloat64Builder(memory.DefaultAllocator)
+ rightBuilder.AppendValues([]float64{1.000001, 2, 3}, nil)
+ right := rightBuilder.NewFloat64Array()
+ rightBuilder.Release()
+ defer right.Release()
+
+ assert.True(t, array.SliceApproxEqual(
+ left, 0, int64(left.Len()),
+ right, 0, int64(right.Len()),
+ array.WithAbsTolerance(1e-5),
+ ))
+ assert.False(t, array.SliceApproxEqual(
+ left, 0, int64(left.Len()),
+ right, 0, int64(right.Len()),
+ array.WithAbsTolerance(1e-7),
+ ))
+}
+
+func TestArraySliceApproxEqualFullRangeGenericArray(t *testing.T) {
+ builder := array.NewInt64Builder(memory.DefaultAllocator)
+ builder.AppendValues([]int64{1, 2, 3}, nil)
+ arr := builder.NewInt64Array()
+ builder.Release()
+ defer arr.Release()
+
+ wrapped := arrayWrapper{Array: arr}
+ assert.True(t, array.SliceApproxEqual(
+ wrapped, 0, int64(wrapped.Len()),
+ wrapped, 0, int64(wrapped.Len()),
+ ))
+ assert.True(t, array.SliceApproxEqual(
+ arr, 0, int64(arr.Len()),
+ wrapped, 0, int64(wrapped.Len()),
+ ))
+}
+
func TestListEqualByValidRuns(t *testing.T) {
for _, dt := range []arrow.DataType{
arrow.ListOf(arrow.PrimitiveTypes.Int32),
@@ -197,6 +240,7 @@ func TestListEqualByValidRuns(t *testing.T) {
left := makeListEqualTestArray(mem, dt,
tc.left, tc.valid)
right := makeListEqualTestArray(mem,
dt, tc.right, tc.valid)
assert.Equal(t, tc.want,
array.Equal(left, right))
+ assert.Equal(t, tc.want,
array.ApproxEqual(left, right))
left.Release()
right.Release()
mem.AssertSize(t, 0)
@@ -212,6 +256,7 @@ func TestListEqualByValidRuns(t *testing.T) {
leftSlice := array.NewSlice(left, 1, 4)
rightSlice := array.NewSlice(right, 2, 5)
assert.True(t, array.Equal(leftSlice,
rightSlice))
+ assert.True(t, array.ApproxEqual(leftSlice,
rightSlice))
leftSlice.Release()
rightSlice.Release()
left.Release()
@@ -231,10 +276,12 @@ func TestFixedSizeListEqualByValidRuns(t *testing.T) {
right := makeListEqualTestArray(mem, dt,
[][]int32{{1, 2}, {100, 101}, {3, 4}}, []bool{true, false,
true})
assert.True(t, array.Equal(left, right))
+ assert.True(t, array.ApproxEqual(left, right))
different := makeListEqualTestArray(mem, dt,
[][]int32{{1, 2}, {100, 101}, {3, 5}}, []bool{true, false,
true})
assert.False(t, array.Equal(left, different))
+ assert.False(t, array.ApproxEqual(left, different))
leftWithPrefix := makeListEqualTestArray(mem, dt,
[][]int32{{9, 9}, {1, 2}, {99, 98}, {3, 4}}, []bool{true, true,
false, true})
@@ -243,6 +290,7 @@ func TestFixedSizeListEqualByValidRuns(t *testing.T) {
leftSlice := array.NewSlice(leftWithPrefix, 1, 4)
rightSlice := array.NewSlice(rightWithPrefix, 2, 5)
assert.True(t, array.Equal(leftSlice, rightSlice))
+ assert.True(t, array.ApproxEqual(leftSlice, rightSlice))
left.Release()
right.Release()
@@ -268,7 +316,9 @@ func TestListEqualWithEmptyValidityBuffer(t *testing.T) {
assert.NotNil(t, emptyValidity.NullBitmapBytes())
assert.True(t, array.Equal(emptyValidity, valid))
+ assert.True(t, array.ApproxEqual(emptyValidity, valid))
assert.True(t, array.Equal(valid, emptyValidity))
+ assert.True(t, array.ApproxEqual(valid, emptyValidity))
emptyValidity.Release()
valid.Release()
@@ -1249,3 +1299,48 @@ func TestTableEqual(t *testing.T) {
})
}
}
+
+func TestListApproxEqualValidRunsOptions(t *testing.T) {
+ for _, dt := range
[]arrow.DataType{arrow.ListOf(arrow.PrimitiveTypes.Float64),
arrow.LargeListOf(arrow.PrimitiveTypes.Float64), arrow.FixedSizeListOf(2,
arrow.PrimitiveTypes.Float64)} {
+ t.Run(dt.String(), func(t *testing.T) {
+ mem :=
memory.NewCheckedAllocator(memory.DefaultAllocator)
+ defer mem.AssertSize(t, 0)
+ makeInput := func(prefix int, delta float64, mismatch
bool) arrow.Array {
+ builder := array.NewBuilder(mem, dt)
+ defer builder.Release()
+ child := builder.(interface{ ValueBuilder()
array.Builder }).ValueBuilder().(*array.Float64Builder)
+ for i := -prefix; i < 128; i++ {
+ valid := i < 32 || i >= 64
+ builder.(interface{ Append(bool)
}).Append(valid)
+ if i >= 32 && i < 64 {
+
child.AppendValues([]float64{float64(prefix) * 999, -float64(prefix) * 999},
nil)
+ } else if i == 80 {
+ child.Append(math.NaN())
+ child.AppendNull()
+ } else {
+ value := float64(i) + delta
+ if mismatch && i == 100 {
+ value += 10
+ }
+
child.AppendValues([]float64{value, value}, nil)
+ }
+ }
+ base := builder.NewArray()
+ defer base.Release()
+ return array.NewSlice(base, int64(prefix),
int64(prefix+128))
+ }
+ left := makeInput(1, 0, false)
+ defer left.Release()
+ right := makeInput(3, 0.01, false)
+ defer right.Release()
+ mismatch := makeInput(2, 0.01, true)
+ defer mismatch.Release()
+ opts :=
[]array.EqualOption{array.WithAbsTolerance(0.1), array.WithNaNsEqual(true)}
+ assert.True(t, array.ApproxEqual(left, right, opts...))
+ assert.True(t, array.ApproxEqual(right, left, opts...))
+ assert.False(t, array.ApproxEqual(left, right,
array.WithNaNsEqual(true)))
+ assert.False(t, array.ApproxEqual(left, right,
array.WithAbsTolerance(0.1)))
+ assert.False(t, array.ApproxEqual(left, mismatch,
opts...))
+ })
+ }
+}
diff --git a/arrow/array/list_equal_benchmark_test.go
b/arrow/array/list_equal_benchmark_test.go
index bd4bfb9c..14883a6a 100644
--- a/arrow/array/list_equal_benchmark_test.go
+++ b/arrow/array/list_equal_benchmark_test.go
@@ -64,6 +64,39 @@ func BenchmarkListEqual(b *testing.B) {
}
}
+func BenchmarkListApproxEqual(b *testing.B) {
+ const rows = 65536
+ tests := []struct {
+ listType string
+ child arrow.DataType
+ listSize int
+ validity string
+ }{
+ {"list", arrow.PrimitiveTypes.Int32, 16, "all-valid"},
+ {"list", arrow.BinaryTypes.String, 16, "all-valid"},
+ {"large-list", arrow.PrimitiveTypes.Int32, 16, "all-valid"},
+ {"fixed-size-list", arrow.PrimitiveTypes.Int32, 16,
"all-valid"},
+ {"list", arrow.PrimitiveTypes.Int32, 16, "10pct-null"},
+ {"list", arrow.PrimitiveTypes.Int32, 16,
"clustered-10pct-null"},
+ {"list", arrow.PrimitiveTypes.Int32, 16, "alternating-null"},
+ }
+
+ for _, tc := range tests {
+ name := fmt.Sprintf("%s/%s/size=%d/%s", tc.listType,
tc.child.Name(), tc.listSize, tc.validity)
+ b.Run(name, func(b *testing.B) {
+ left := makeListEqualBenchmarkArray(tc.listType,
tc.child, rows, tc.listSize, tc.validity)
+ right := makeListEqualBenchmarkArray(tc.listType,
tc.child, rows, tc.listSize, tc.validity)
+ defer left.Release()
+ defer right.Release()
+
+ b.ReportAllocs()
+ for b.Loop() {
+ benchmarkListEqualResult =
array.ApproxEqual(left, right)
+ }
+ })
+ }
+}
+
func makeListEqualBenchmarkArray(listType string, childType arrow.DataType,
rows, listSize int, validity string) arrow.Array {
var (
child array.Builder
