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 31ef15de perf(arrow/array): compare list values by valid runs (#1184)
31ef15de is described below
commit 31ef15de46ebd3782152e269323b6649a3b3fdff
Author: Minh Vu <[email protected]>
AuthorDate: Fri Aug 14 23:22:36 2026 +0200
perf(arrow/array): compare list values by valid runs (#1184)
## What does this PR do?
- compares List and LargeList child values once per contiguous valid
parent run
- checks every parent list length before combining its child range
- compares FixedSizeList child values once per valid parent run
- avoids creating two child array slices for every valid parent value
ListView and LargeListView are not included because their child ranges
can be non-contiguous.
## Why?
List equality currently creates two temporary child arrays and
recursively calls `Equal` for every valid parent value.
For 65,536 all-valid lists, that creates about 131,000 temporary child
arrays. A valid-run comparison checks the parent lengths and compares
one contiguous child range instead.
This follows the same approach as Arrow C++ list equality.
## Benchmarks
Apple M1 Pro, 65,536 equal parent values:
| case | before | after | change | allocations before | allocations
after |
| --- | ---: | ---: | ---: | ---: | ---: |
| List<Int32>, size 1, all valid | 15.6 ms | 0.82 ms | -95% | 262,145 |
5 |
| List<Int32>, size 4, all valid | 16.5 ms | 2.39 ms | -86% | 262,145 |
5 |
| List<Int32>, size 16, all valid | 22.3 ms | 8.50 ms | -62% | 262,145 |
5 |
| List<String>, size 16, all valid | 23.0 ms | 8.65 ms | -62% | 262,145
| 5 |
| LargeList<Int32>, size 16, all valid | 22.3 ms | 8.47 ms | -62% |
262,145 | 5 |
| FixedSizeList<Int32>, size 16, all valid | 22.5 ms | 8.50 ms | -62% |
262,145 | 5 |
| List<Int32>, size 16, clustered 10% null | 20.1 ms | 7.90 ms | -61% |
235,933 | 9 |
Alternating valid and null parents stays around 11.2 ms in both
versions. This is the most fragmented case, where each valid run
contains one parent value.
```text
go test ./arrow/array -run '^$' -bench '^BenchmarkListEqual$' -benchmem
-benchtime=200ms -count=3
```
## Tests
- checks equal and different child values
- checks different parent list lengths with the same flattened child
values
- checks that null parent payloads are ignored
- checks sliced parents with different left and right offsets
- covers List, LargeList, and FixedSizeList
- ran `go test ./arrow/...`
- ran `go test -race ./arrow/array`
- ran `go vet ./arrow/array`
---
arrow/array/compare.go | 32 ++++++
arrow/array/compare_test.go | 168 +++++++++++++++++++++++++++++++
arrow/array/fixed_size_list.go | 30 +++---
arrow/array/list.go | 36 +------
arrow/array/list_equal_benchmark_test.go | 129 ++++++++++++++++++++++++
5 files changed, 348 insertions(+), 47 deletions(-)
diff --git a/arrow/array/compare.go b/arrow/array/compare.go
index d8a9552e..7624b996 100644
--- a/arrow/array/compare.go
+++ b/arrow/array/compare.go
@@ -361,6 +361,38 @@ func SliceEqual(left arrow.Array, lbeg, lend int64, right
arrow.Array, rbeg, ren
return Equal(l, r)
}
+type listOffset interface {
+ int32 | int64
+}
+
+func arrayEqualListOffsets[T listOffset](leftValues, rightValues arrow.Array,
+ leftOffsets, rightOffsets []T, leftOffset, rightOffset, length int,
validBits []byte) 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 !SliceEqual(leftValues, leftStart, leftEnd,
rightValues, rightStart, rightEnd) {
+ return arrow.ErrInvalid
+ }
+ return nil
+ }) == nil
+}
+
// 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...)
diff --git a/arrow/array/compare_test.go b/arrow/array/compare_test.go
index 0671def6..d89ce42b 100644
--- a/arrow/array/compare_test.go
+++ b/arrow/array/compare_test.go
@@ -85,6 +85,174 @@ func TestArraySliceEqual(t *testing.T) {
}
}
+func TestListEqualByValidRuns(t *testing.T) {
+ for _, dt := range []arrow.DataType{
+ arrow.ListOf(arrow.PrimitiveTypes.Int32),
+ arrow.LargeListOf(arrow.PrimitiveTypes.Int32),
+ } {
+ t.Run(dt.ID().String(), func(t *testing.T) {
+ tests := []struct {
+ name string
+ left, right [][]int32
+ valid []bool
+ want bool
+ }{
+ {
+ name: "equal",
+ left: [][]int32{{1, 2}, {3}, {4, 5,
6}},
+ right: [][]int32{{1, 2}, {3}, {4, 5,
6}},
+ valid: []bool{true, true, true},
+ want: true,
+ },
+ {
+ name: "different list lengths with
equal child values",
+ left: [][]int32{{1}, {2, 3}},
+ right: [][]int32{{1, 2}, {3}},
+ valid: []bool{true, true},
+ want: false,
+ },
+ {
+ name: "ignore null list payloads",
+ left: [][]int32{{1}, {99}, {3, 4}},
+ right: [][]int32{{1}, {100, 101}, {3,
4}},
+ valid: []bool{true, false, true},
+ want: true,
+ },
+ {
+ name: "different valid child values",
+ left: [][]int32{{1}, {99}, {3, 4}},
+ right: [][]int32{{1}, {100}, {3, 5}},
+ valid: []bool{true, false, true},
+ want: false,
+ },
+ }
+
+ for _, tc := range tests {
+ t.Run(tc.name, func(t *testing.T) {
+ mem :=
memory.NewCheckedAllocator(memory.NewGoAllocator())
+ 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))
+ left.Release()
+ right.Release()
+ mem.AssertSize(t, 0)
+ })
+ }
+
+ t.Run("sliced parents", func(t *testing.T) {
+ mem :=
memory.NewCheckedAllocator(memory.NewGoAllocator())
+ left := makeListEqualTestArray(mem, dt,
+ [][]int32{{9}, {1, 2}, {3}, {4, 5}},
[]bool{true, true, false, true})
+ right := makeListEqualTestArray(mem, dt,
+ [][]int32{{7}, {8, 8}, {1, 2}, {99},
{4, 5}}, []bool{true, true, true, false, true})
+ leftSlice := array.NewSlice(left, 1, 4)
+ rightSlice := array.NewSlice(right, 2, 5)
+ assert.True(t, array.Equal(leftSlice,
rightSlice))
+ leftSlice.Release()
+ rightSlice.Release()
+ left.Release()
+ right.Release()
+ mem.AssertSize(t, 0)
+ })
+ })
+ }
+}
+
+func TestFixedSizeListEqualByValidRuns(t *testing.T) {
+ mem := memory.NewCheckedAllocator(memory.NewGoAllocator())
+ dt := arrow.FixedSizeListOf(2, arrow.PrimitiveTypes.Int32)
+
+ left := makeListEqualTestArray(mem, dt,
+ [][]int32{{1, 2}, {99, 98}, {3, 4}}, []bool{true, false, true})
+ right := makeListEqualTestArray(mem, dt,
+ [][]int32{{1, 2}, {100, 101}, {3, 4}}, []bool{true, false,
true})
+ assert.True(t, array.Equal(left, right))
+
+ different := makeListEqualTestArray(mem, dt,
+ [][]int32{{1, 2}, {100, 101}, {3, 5}}, []bool{true, false,
true})
+ assert.False(t, array.Equal(left, different))
+
+ leftWithPrefix := makeListEqualTestArray(mem, dt,
+ [][]int32{{9, 9}, {1, 2}, {99, 98}, {3, 4}}, []bool{true, true,
false, true})
+ rightWithPrefix := makeListEqualTestArray(mem, dt,
+ [][]int32{{7, 7}, {8, 8}, {1, 2}, {100, 101}, {3, 4}},
[]bool{true, true, true, false, true})
+ leftSlice := array.NewSlice(leftWithPrefix, 1, 4)
+ rightSlice := array.NewSlice(rightWithPrefix, 2, 5)
+ assert.True(t, array.Equal(leftSlice, rightSlice))
+
+ left.Release()
+ right.Release()
+ different.Release()
+ leftSlice.Release()
+ rightSlice.Release()
+ leftWithPrefix.Release()
+ rightWithPrefix.Release()
+ mem.AssertSize(t, 0)
+}
+
+func TestListEqualWithEmptyValidityBuffer(t *testing.T) {
+ for _, dt := range []arrow.DataType{
+ arrow.ListOf(arrow.PrimitiveTypes.Int32),
+ arrow.LargeListOf(arrow.PrimitiveTypes.Int32),
+ arrow.FixedSizeListOf(2, arrow.PrimitiveTypes.Int32),
+ } {
+ t.Run(dt.ID().String(), func(t *testing.T) {
+ mem :=
memory.NewCheckedAllocator(memory.NewGoAllocator())
+ values := [][]int32{{1, 2}, {3, 4}}
+ valid := makeListEqualTestArray(mem, dt, values,
[]bool{true, true})
+ emptyValidity :=
makeListEqualTestArrayWithEmptyValidity(mem, dt, values)
+
+ assert.NotNil(t, emptyValidity.NullBitmapBytes())
+ assert.True(t, array.Equal(emptyValidity, valid))
+ assert.True(t, array.Equal(valid, emptyValidity))
+
+ emptyValidity.Release()
+ valid.Release()
+ mem.AssertSize(t, 0)
+ })
+ }
+}
+
+func makeListEqualTestArray(mem memory.Allocator, dt arrow.DataType, values
[][]int32, valid []bool) arrow.Array {
+ switch dt.ID() {
+ case arrow.LIST, arrow.LARGE_LIST:
+ bldr := array.NewBuilder(mem, dt).(array.VarLenListLikeBuilder)
+ child := bldr.ValueBuilder().(*array.Int32Builder)
+ for i, value := range values {
+ bldr.AppendWithSize(valid[i], len(value))
+ child.AppendValues(value, nil)
+ }
+ out := bldr.NewArray()
+ bldr.Release()
+ return out
+ case arrow.FIXED_SIZE_LIST:
+ listSize := dt.(*arrow.FixedSizeListType).Len()
+ bldr := array.NewFixedSizeListBuilder(mem, listSize,
arrow.PrimitiveTypes.Int32)
+ child := bldr.ValueBuilder().(*array.Int32Builder)
+ for i, value := range values {
+ bldr.Append(valid[i])
+ child.AppendValues(value, nil)
+ }
+ out := bldr.NewArray()
+ bldr.Release()
+ return out
+ default:
+ panic("unsupported list type")
+ }
+}
+
+func makeListEqualTestArrayWithEmptyValidity(mem memory.Allocator, dt
arrow.DataType, values [][]int32) arrow.Array {
+ arr := makeListEqualTestArray(mem, dt, values, []bool{true, true})
+ data := arr.Data()
+ buffers := append([]*memory.Buffer(nil), data.Buffers()...)
+ buffers[0] = memory.NewBufferBytes([]byte{})
+ emptyValidityData := array.NewData(data.DataType(), data.Len(),
buffers, data.Children(), data.NullN(), data.Offset())
+ out := array.MakeFromData(emptyValidityData)
+ emptyValidityData.Release()
+ arr.Release()
+ return out
+}
+
func TestArrayApproxEqual(t *testing.T) {
for name, recs := range arrdata.Records {
t.Run(name, func(t *testing.T) {
diff --git a/arrow/array/fixed_size_list.go b/arrow/array/fixed_size_list.go
index 55477f11..c3aafb31 100644
--- a/arrow/array/fixed_size_list.go
+++ b/arrow/array/fixed_size_list.go
@@ -25,6 +25,7 @@ import (
"github.com/apache/arrow-go/v18/arrow/bitutil"
"github.com/apache/arrow-go/v18/arrow/internal/debug"
"github.com/apache/arrow-go/v18/arrow/memory"
+ "github.com/apache/arrow-go/v18/internal/bitutils"
"github.com/apache/arrow-go/v18/internal/json"
)
@@ -88,22 +89,21 @@ func (a *FixedSizeList) setData(data *Data) {
}
func arrayEqualFixedSizeList(left, right *FixedSizeList) 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 Equal(l, r)
- }()
- if !o {
- return false
- }
+ listSize := int64(left.n)
+ validBits := left.NullBitmapBytes()
+ if len(validBits) == 0 {
+ validBits = nil
}
- return true
+ 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 !SliceEqual(left.values, leftStart,
leftStart+length*listSize,
+ right.values, rightStart,
rightStart+length*listSize) {
+ return arrow.ErrInvalid
+ }
+ return nil
+ }) == nil
}
// Len returns the number of elements in the array.
diff --git a/arrow/array/list.go b/arrow/array/list.go
index dd9d82ef..4ccea68e 100644
--- a/arrow/array/list.go
+++ b/arrow/array/list.go
@@ -137,22 +137,8 @@ func (a *List) MarshalJSON() ([]byte, error) {
}
func arrayEqualList(left, right *List) 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 Equal(l, r)
- }()
- if !o {
- return false
- }
- }
- return true
+ return arrayEqualListOffsets(left.values, right.values, left.offsets,
right.offsets,
+ left.data.offset, right.data.offset, left.Len(),
left.NullBitmapBytes())
}
// Len returns the number of elements in the array.
@@ -276,22 +262,8 @@ func (a *LargeList) MarshalJSON() ([]byte, error) {
}
func arrayEqualLargeList(left, right *LargeList) 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 Equal(l, r)
- }()
- if !o {
- return false
- }
- }
- return true
+ return arrayEqualListOffsets(left.values, right.values, left.offsets,
right.offsets,
+ left.data.offset, right.data.offset, left.Len(),
left.NullBitmapBytes())
}
// Len returns the number of elements in the array.
diff --git a/arrow/array/list_equal_benchmark_test.go
b/arrow/array/list_equal_benchmark_test.go
new file mode 100644
index 00000000..bd4bfb9c
--- /dev/null
+++ b/arrow/array/list_equal_benchmark_test.go
@@ -0,0 +1,129 @@
+// 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 (
+ "fmt"
+ "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 benchmarkListEqualResult bool
+
+func BenchmarkListEqual(b *testing.B) {
+ const rows = 65536
+ tests := []struct {
+ listType string
+ child arrow.DataType
+ listSize int
+ validity string
+ }{
+ {"list", arrow.PrimitiveTypes.Int32, 1, "all-valid"},
+ {"list", arrow.PrimitiveTypes.Int32, 4, "all-valid"},
+ {"list", arrow.PrimitiveTypes.Int32, 16, "all-valid"},
+ {"list", arrow.PrimitiveTypes.Int32, 64, "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()
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ benchmarkListEqualResult = array.Equal(left,
right)
+ }
+ })
+ }
+}
+
+func makeListEqualBenchmarkArray(listType string, childType arrow.DataType,
rows, listSize int, validity string) arrow.Array {
+ var (
+ child array.Builder
+ appendParent func(bool)
+ newArray func() arrow.Array
+ release func()
+ )
+
+ switch listType {
+ case "list":
+ bldr := array.NewListBuilder(memory.DefaultAllocator, childType)
+ child = bldr.ValueBuilder()
+ appendParent = bldr.Append
+ newArray = bldr.NewArray
+ release = bldr.Release
+ case "large-list":
+ bldr := array.NewLargeListBuilder(memory.DefaultAllocator,
childType)
+ child = bldr.ValueBuilder()
+ appendParent = bldr.Append
+ newArray = bldr.NewArray
+ release = bldr.Release
+ case "fixed-size-list":
+ bldr := array.NewFixedSizeListBuilder(memory.DefaultAllocator,
int32(listSize), childType)
+ child = bldr.ValueBuilder()
+ appendParent = bldr.Append
+ newArray = bldr.NewArray
+ release = bldr.Release
+ default:
+ panic("unsupported list type")
+ }
+ defer release()
+
+ for i := 0; i < rows; i++ {
+ valid := listBenchmarkValueIsValid(i, rows, validity)
+ appendParent(valid)
+ for j := 0; j < listSize; j++ {
+ switch child := child.(type) {
+ case *array.Int32Builder:
+ child.Append(int32(j))
+ case *array.StringBuilder:
+ child.Append([]string{"alpha", "bravo",
"charlie", "delta"}[j%4])
+ default:
+ panic("unsupported child type")
+ }
+ }
+ }
+ return newArray()
+}
+
+func listBenchmarkValueIsValid(index, length int, pattern string) bool {
+ switch pattern {
+ case "all-valid":
+ return true
+ case "10pct-null":
+ return index%10 != 0
+ case "clustered-10pct-null":
+ return index < length*45/100 || index >= length*55/100
+ case "alternating-null":
+ return index%2 == 0
+ default:
+ panic("unsupported validity pattern")
+ }
+}
