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 816ad55a perf(arrow/array): compare fixed-width values in bulk (#1171)
816ad55a is described below
commit 816ad55aaba8788490704729bd487f8811114a20
Author: Minh Vu <[email protected]>
AuthorDate: Fri Aug 28 21:54:44 2026 +0200
perf(arrow/array): compare fixed-width values in bulk (#1171)
### Rationale for this change
Fixed-width array equality currently checks validity and values one
element at a time. The values are already contiguous, so larger arrays
can be compared much more efficiently in bulk.
### What changes are included in this PR?
- Compare validity bitmaps in bulk.
- Compare null-free integer and temporal arrays with `bytes.Equal`.
- Walk contiguous valid runs for nullable arrays, ignoring bytes under
null slots.
- Keep floating-point arrays on the scalar path to preserve NaN and
signed-zero behavior.
- Keep arrays shorter than 8 values on the scalar path.
- Add benchmarks for int32/int64 arrays, several null patterns, and
mismatch positions.
- Add tests for null-slot and floating-point semantics.
On an M1 Pro with GOMAXPROCS=1, 65,536-value equality benchmarks
improved as follows:
| Case | Before | After |
| --- | ---: | ---: |
| int32, all valid | 505.9 µs | 6.5 µs |
| int32, 1% null | 516.2 µs | 14.2 µs |
| int32, alternating null | 432.2 µs | 247.9 µs |
| int64, all valid | 520.0 µs | 13.2 µs |
| int64, 1% null | 523.0 µs | 20.3 µs |
| int64, alternating null | 439.0 µs | 245.9 µs |
Allocations remain at zero.
### Are these changes tested?
- `go test ./arrow/...`
- `go test -race ./arrow/array`
- `go vet -composites=false ./arrow/array`
The full Arrow test run used the checked-out Parquet test data.
### Are there any user-facing changes?
No.
---
arrow/array/compare.go | 33 +++++--
arrow/array/compare_benchmark_test.go | 155 +++++++++++++++++++++++++++++++
arrow/array/compare_test.go | 170 ++++++++++++++++++++++++++++++++++
arrow/array/numeric_generic.go | 46 ++++++++-
arrow/array/timestamp.go | 10 +-
5 files changed, 394 insertions(+), 20 deletions(-)
diff --git a/arrow/array/compare.go b/arrow/array/compare.go
index 7624b996..37ef0594 100644
--- a/arrow/array/compare.go
+++ b/arrow/array/compare.go
@@ -21,6 +21,7 @@ import (
"math"
"github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/bitutil"
"github.com/apache/arrow-go/v18/arrow/float16"
"github.com/apache/arrow-go/v18/internal/bitutils"
)
@@ -264,13 +265,13 @@ func Equal(left, right arrow.Array) bool {
return arrayEqualFixedWidth(l, r)
case *Float16:
r := right.(*Float16)
- return arrayEqualFixedWidth(l, r)
+ return arrayEqualFixedWidthScalar(l, r)
case *Float32:
r := right.(*Float32)
- return arrayEqualFixedWidth(l, r)
+ return arrayEqualFixedWidthScalar(l, r)
case *Float64:
r := right.(*Float64)
- return arrayEqualFixedWidth(l, r)
+ return arrayEqualFixedWidthScalar(l, r)
case *Decimal32:
r := right.(*Decimal32)
return arrayEqualDecimal(l, r)
@@ -663,17 +664,29 @@ func baseArrayEqual(left, right arrow.Array) bool {
}
func validityBitmapEqual(left, right arrow.Array) bool {
- // TODO(alexandreyc): make it faster by comparing byte slices of the
validity bitmap?
- n := left.Len()
- if n != right.Len() {
+ if left.Len() != right.Len() {
return false
}
- for i := 0; i < n; i++ {
- if left.IsNull(i) != right.IsNull(i) {
- return false
+
+ leftBitmap := left.NullBitmapBytes()
+ rightBitmap := right.NullBitmapBytes()
+ if left.NullN() == 0 && len(leftBitmap) == 0 && len(rightBitmap) == 0 {
+ return true
+ }
+
+ if len(leftBitmap) == 0 || len(rightBitmap) == 0 {
+ for i := range left.Len() {
+ if left.IsNull(i) != right.IsNull(i) {
+ return false
+ }
}
+ return true
}
- return true
+
+ return bitutil.BitmapEquals(
+ leftBitmap, rightBitmap,
+ int64(left.Data().Offset()), int64(right.Data().Offset()),
int64(left.Len()),
+ )
}
func arrayApproxEqualString(left, right *String) bool {
diff --git a/arrow/array/compare_benchmark_test.go
b/arrow/array/compare_benchmark_test.go
new file mode 100644
index 00000000..f80fe263
--- /dev/null
+++ b/arrow/array/compare_benchmark_test.go
@@ -0,0 +1,155 @@
+// 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"
+)
+
+type fixedWidthArrayFactory func([]int64, []bool) arrow.Array
+
+func BenchmarkEqualFixedWidth(b *testing.B) {
+ types := []struct {
+ name string
+ factory fixedWidthArrayFactory
+ }{
+ {"int32", makeInt32Array},
+ {"int64", makeInt64Array},
+ }
+ nullPatterns := []struct {
+ name string
+ valid func(int) []bool
+ }{
+ {"all-valid", func(int) []bool { return nil }},
+ {"one-percent-null", makeValidityEvery(100)},
+ {"alternating-null", makeValidityEvery(2)},
+ {"clustered-null", makeClusteredValidity},
+ }
+
+ for _, typ := range types {
+ b.Run(typ.name, func(b *testing.B) {
+ for _, length := range []int{1024, 65536} {
+ b.Run(fmt.Sprintf("len-%d", length), func(b
*testing.B) {
+ for _, pattern := range nullPatterns {
+ b.Run(pattern.name, func(b
*testing.B) {
+ values :=
makeBenchmarkValues(length)
+ valid :=
pattern.valid(length)
+ rightValues :=
append([]int64(nil), values...)
+ for idx, isValid :=
range valid {
+ if !isValid {
+
rightValues[idx]++
+ }
+ }
+
+ left :=
typ.factory(values, valid)
+ defer left.Release()
+ right :=
typ.factory(rightValues, valid)
+ defer right.Release()
+
+ b.ReportAllocs()
+ b.ResetTimer()
+ for b.Loop() {
+ if
!array.Equal(left, right) {
+
b.Fatal("expected arrays to be equal")
+ }
+ }
+ })
+ }
+ })
+ }
+
+ for _, mismatch := range []struct {
+ name string
+ pos int
+ }{
+ {"mismatch-first", 0},
+ {"mismatch-middle", 65536 / 2},
+ {"mismatch-last", 65536 - 1},
+ } {
+ b.Run(mismatch.name, func(b *testing.B) {
+ values := makeBenchmarkValues(65536)
+ rightValues := append([]int64(nil),
values...)
+ rightValues[mismatch.pos]++
+
+ left := typ.factory(values, nil)
+ defer left.Release()
+ right := typ.factory(rightValues, nil)
+ defer right.Release()
+
+ b.ReportAllocs()
+ b.ResetTimer()
+ for b.Loop() {
+ if array.Equal(left, right) {
+ b.Fatal("expected
arrays to differ")
+ }
+ }
+ })
+ }
+ })
+ }
+}
+
+func makeBenchmarkValues(length int) []int64 {
+ values := make([]int64, length)
+ for idx := range values {
+ values[idx] = int64(idx*17 + idx%11)
+ }
+ return values
+}
+
+func makeValidityEvery(n int) func(int) []bool {
+ return func(length int) []bool {
+ valid := make([]bool, length)
+ for idx := range valid {
+ valid[idx] = idx%n != 0
+ }
+ return valid
+ }
+}
+
+func makeClusteredValidity(length int) []bool {
+ valid := make([]bool, length)
+ for idx := length / 2; idx < length; idx++ {
+ valid[idx] = true
+ }
+ return valid
+}
+
+func makeInt32Array(values []int64, valid []bool) arrow.Array {
+ builder := array.NewInt32Builder(memory.DefaultAllocator)
+ defer builder.Release()
+
+ converted := make([]int32, len(values))
+ for idx, value := range values {
+ converted[idx] = int32(value)
+ }
+ builder.AppendValues(converted, valid)
+ return builder.NewInt32Array()
+}
+
+func makeInt64Array(values []int64, valid []bool) arrow.Array {
+ builder := array.NewInt64Builder(memory.DefaultAllocator)
+ defer builder.Release()
+
+ builder.AppendValues(values, valid)
+ return builder.NewInt64Array()
+}
diff --git a/arrow/array/compare_test.go b/arrow/array/compare_test.go
index d89ce42b..4c5d0373 100644
--- a/arrow/array/compare_test.go
+++ b/arrow/array/compare_test.go
@@ -781,6 +781,176 @@ func TestArrayEqualBaseArray(t *testing.T) {
}
}
+func TestArrayEqualFloatingPointSemantics(t *testing.T) {
+ negativeZero := math.Copysign(0, -1)
+ tests := []struct {
+ name string
+ left interface{}
+ right interface{}
+ want bool
+ }{
+ {"float16 signed zero", []float16.Num{float16.New(0)},
[]float16.Num{float16.New(float32(negativeZero))}, false},
+ {"float16 NaN",
[]float16.Num{float16.New(float32(math.NaN()))},
[]float16.Num{float16.New(float32(math.NaN()))}, true},
+ {"float32 signed zero", []float32{0},
[]float32{float32(negativeZero)}, true},
+ {"float32 NaN", []float32{float32(math.NaN())},
[]float32{float32(math.NaN())}, false},
+ {"float64 signed zero", []float64{0}, []float64{negativeZero},
true},
+ {"float64 NaN", []float64{math.NaN()}, []float64{math.NaN()},
false},
+ }
+
+ for _, test := range tests {
+ t.Run(test.name, func(t *testing.T) {
+ left := arrayOf(nil, test.left, nil)
+ defer left.Release()
+ right := arrayOf(nil, test.right, nil)
+ defer right.Release()
+
+ assert.Equal(t, test.want, array.Equal(left, right))
+ })
+ }
+}
+
+const fixedWidthEqualityTestLength = 72
+
+func fixedWidthEqualityValidity() []bool {
+ valid := make([]bool, fixedWidthEqualityTestLength)
+ for i := range valid {
+ valid[i] = true
+ }
+ for _, i := range []int{0, 11, 30, 60, 68} {
+ valid[i] = false
+ }
+ return valid
+}
+
+func makeSlicedInt64EqualityArray(values []int64, valid []bool, offset int)
*array.Int64 {
+ baseValues := make([]int64, offset+len(values)+1)
+ baseValid := make([]bool, len(baseValues))
+ for i := range baseValid {
+ baseValid[i] = true
+ }
+ copy(baseValues[offset:], values)
+ copy(baseValid[offset:], valid)
+
+ builder := array.NewInt64Builder(memory.DefaultAllocator)
+ builder.AppendValues(baseValues, baseValid)
+ base := builder.NewInt64Array()
+ builder.Release()
+
+ sliced := array.NewSlice(base, int64(offset),
int64(offset+len(values))).(*array.Int64)
+ base.Release()
+ return sliced
+}
+
+func makeSlicedTimestampEqualityArray(values []arrow.Timestamp, valid []bool,
offset int) *array.Timestamp {
+ baseValues := make([]arrow.Timestamp, offset+len(values)+1)
+ baseValid := make([]bool, len(baseValues))
+ for i := range baseValid {
+ baseValid[i] = true
+ }
+ copy(baseValues[offset:], values)
+ copy(baseValid[offset:], valid)
+
+ builder := array.NewTimestampBuilder(memory.DefaultAllocator,
arrow.FixedWidthTypes.Timestamp_ms.(*arrow.TimestampType))
+ builder.AppendValues(baseValues, baseValid)
+ base := builder.NewTimestampArray()
+ builder.Release()
+
+ sliced := array.NewSlice(base, int64(offset),
int64(offset+len(values))).(*array.Timestamp)
+ base.Release()
+ return sliced
+}
+
+func makeInt64EqualityArrayWithValidity(validity []byte, nulls int)
*array.Int64 {
+ validityBuffer := memory.NewBufferBytes(validity)
+ valuesBuffer := memory.NewBufferBytes(make([]byte, 8*8))
+ data := array.NewData(
+ arrow.PrimitiveTypes.Int64,
+ 8,
+ []*memory.Buffer{validityBuffer, valuesBuffer},
+ nil,
+ nulls,
+ 0,
+ )
+ validityBuffer.Release()
+ valuesBuffer.Release()
+
+ result := array.NewInt64Data(data)
+ data.Release()
+ return result
+}
+
+func TestArrayEqualFixedWidthIgnoresNullValues(t *testing.T) {
+ const sliceLength = fixedWidthEqualityTestLength
+ valid := fixedWidthEqualityValidity()
+
+ leftValues := make([]int64, sliceLength)
+ rightValues := make([]int64, sliceLength)
+ for i := range leftValues {
+ leftValues[i] = int64(i + 1)
+ rightValues[i] = leftValues[i]
+ if !valid[i] {
+ rightValues[i] = -rightValues[i]
+ }
+ }
+
+ left := makeSlicedInt64EqualityArray(leftValues, valid, 3)
+ defer left.Release()
+ right := makeSlicedInt64EqualityArray(rightValues, valid, 5)
+ defer right.Release()
+
+ assert.Equal(t, 3, left.Data().Offset())
+ assert.Equal(t, 5, right.Data().Offset())
+ assert.True(t, array.Equal(left, right))
+
+ rightValues[5]++
+ different := makeSlicedInt64EqualityArray(rightValues, valid, 5)
+ defer different.Release()
+ assert.False(t, array.Equal(left, different))
+}
+
+func TestArrayEqualFixedWidthTimestamp(t *testing.T) {
+ const length = fixedWidthEqualityTestLength
+ valid := fixedWidthEqualityValidity()
+
+ leftValues := make([]arrow.Timestamp, length)
+ rightValues := make([]arrow.Timestamp, length)
+ for i := range leftValues {
+ leftValues[i] = arrow.Timestamp(i + 1)
+ rightValues[i] = leftValues[i]
+ if !valid[i] {
+ rightValues[i] = -rightValues[i]
+ }
+ }
+
+ left := makeSlicedTimestampEqualityArray(leftValues, valid, 3)
+ defer left.Release()
+ right := makeSlicedTimestampEqualityArray(rightValues, valid, 5)
+ defer right.Release()
+
+ assert.True(t, array.Equal(left, right))
+}
+
+func TestArrayEqualFixedWidthEmptyNullBitmap(t *testing.T) {
+ left := makeInt64EqualityArrayWithValidity(nil, 1)
+ defer left.Release()
+ right := makeInt64EqualityArrayWithValidity(nil, 1)
+ defer right.Release()
+
+ assert.NotPanics(t, func() {
+ assert.True(t, array.Equal(left, right))
+ assert.True(t, array.Equal(right, left))
+ })
+}
+
+func TestArrayEqualValidityBitmapWithZeroNullCount(t *testing.T) {
+ left := makeInt64EqualityArrayWithValidity([]byte{0xff}, 0)
+ defer left.Release()
+ right := makeInt64EqualityArrayWithValidity([]byte{0xfe}, 0)
+ defer right.Release()
+
+ assert.False(t, array.Equal(left, right))
+}
+
func TestArrayEqualNull(t *testing.T) {
mem := memory.NewCheckedAllocator(memory.NewGoAllocator())
defer mem.AssertSize(t, 0)
diff --git a/arrow/array/numeric_generic.go b/arrow/array/numeric_generic.go
index 2ff88427..7d7de68d 100644
--- a/arrow/array/numeric_generic.go
+++ b/arrow/array/numeric_generic.go
@@ -17,6 +17,7 @@
package array
import (
+ "bytes"
"fmt"
"strconv"
"strings"
@@ -24,6 +25,7 @@ import (
"unsafe"
"github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/internal/bitutils"
"github.com/apache/arrow-go/v18/internal/json"
)
@@ -497,7 +499,49 @@ func NewDate64Data(data arrow.ArrayData) *Date64 {
func (a *Date64) Date64Values() []arrow.Date64 { return a.Values() }
-func arrayEqualFixedWidth[T arrow.FixedWidthType](left, right
arrow.TypedArray[T]) bool {
+type fixedWidthArray[T arrow.FixedWidthType] interface {
+ arrow.TypedArray[T]
+ Values() []T
+}
+
+func arrayEqualFixedWidth[T arrow.FixedWidthType](left, right
fixedWidthArray[T]) bool {
+ // Avoid the fixed cost of bytes.Equal for very small arrays.
+ if left.Len() < 8 {
+ return arrayEqualFixedWidthScalar(left, right)
+ }
+
+ leftValues := left.Values()
+ rightValues := right.Values()
+ if left.NullN() == 0 {
+ return bytes.Equal(arrow.GetBytes(leftValues),
arrow.GetBytes(rightValues))
+ }
+
+ leftBitmap := left.NullBitmapBytes()
+ if len(leftBitmap) == 0 {
+ return arrayEqualFixedWidthScalar(left, right)
+ }
+
+ runs := bitutils.NewSetBitRunReader(
+ leftBitmap, int64(left.Data().Offset()), int64(left.Len()),
+ )
+ for {
+ run := runs.NextRun()
+ if run.Length == 0 {
+ return true
+ }
+
+ start := int(run.Pos)
+ end := start + int(run.Length)
+ if !bytes.Equal(
+ arrow.GetBytes(leftValues[start:end]),
+ arrow.GetBytes(rightValues[start:end]),
+ ) {
+ return false
+ }
+ }
+}
+
+func arrayEqualFixedWidthScalar[T arrow.FixedWidthType](left, right
arrow.TypedArray[T]) bool {
for i := range left.Len() {
if left.IsNull(i) {
continue
diff --git a/arrow/array/timestamp.go b/arrow/array/timestamp.go
index c3d9f190..1b17c3e2 100644
--- a/arrow/array/timestamp.go
+++ b/arrow/array/timestamp.go
@@ -133,15 +133,7 @@ func (a *Timestamp) MarshalJSON() ([]byte, error) {
}
func arrayEqualTimestamp(left, right *Timestamp) bool {
- for i := 0; i < left.Len(); i++ {
- if left.IsNull(i) {
- continue
- }
- if left.Value(i) != right.Value(i) {
- return false
- }
- }
- return true
+ return arrayEqualFixedWidth(left, right)
}
type TimestampBuilder struct {
