You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@arrow.apache.org by ze...@apache.org on 2026/08/28 19:54:50 UTC

(arrow-go) branch main updated: perf(arrow/array): compare fixed-width values in bulk (#1171)

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 <vu...@gmail.com>
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 {