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 c055f32e perf(arrow/array): compare boolean values by valid runs
(#1186)
c055f32e is described below
commit c055f32ee389b03265366c1c5a075693ecc457af
Author: Minh Vu <[email protected]>
AuthorDate: Fri Aug 28 22:07:38 2026 +0200
perf(arrow/array): compare boolean values by valid runs (#1186)
## What
- compare all-valid Boolean value bitmaps in bulk
- compare nullable values one valid run at a time
- keep tiny runs and fragmented validity on the scalar path
- ignore physical value bits under null slots
Boolean values are already bit-packed, but equality currently extracts
the left and right value bit for every valid row.
The C++ equality path uses the same general shape: scalar comparison for
tiny runs and bitmap comparison for larger runs.
https://github.com/apache/arrow/blob/485499fd02ea2b0c323d67871fbe96aae4232504/cpp/src/arrow/compare.cc#L279-L313
## Benchmark
Apple M1 Pro, Go 1.26.3. Representative medians from five runs:
| Case | Before | After | Change |
|---|---:|---:|---:|
| 65K all valid, equal | 401 us | 219 us | -45% |
| 65K clustered 10% null, equal | 395 us | 225 us | -43% |
| 65K alternating null, equal | 340 us | 331 us | -3% |
| 1M all valid, equal | 6.12 ms | 3.56 ms | -42% |
| 1M clustered 10% null, equal | 6.04 ms | 3.66 ms | -39% |
| 1M unaligned slice, equal | 6.15 ms | 3.51 ms | -43% |
The fragmented-run probe keeps periodic and alternating null patterns
near the existing scalar cost.
## Tests
- `go test -race ./arrow/array -count=1`
- `go vet ./arrow/array`
- `go test ./...`
Co-authored-by: Matt Topol <[email protected]>
---
arrow/array/boolean.go | 80 ++++++++++++++++--
arrow/array/boolean_equality_benchmark_test.go | 88 ++++++++++++++++++++
arrow/array/boolean_equality_test.go | 108 +++++++++++++++++++++++++
3 files changed, 271 insertions(+), 5 deletions(-)
diff --git a/arrow/array/boolean.go b/arrow/array/boolean.go
index 80957f19..52e5a1d3 100644
--- a/arrow/array/boolean.go
+++ b/arrow/array/boolean.go
@@ -24,6 +24,7 @@ import (
"github.com/apache/arrow-go/v18/arrow"
"github.com/apache/arrow-go/v18/arrow/bitutil"
"github.com/apache/arrow-go/v18/arrow/memory"
+ "github.com/apache/arrow-go/v18/internal/bitutils"
"github.com/apache/arrow-go/v18/internal/json"
)
@@ -117,15 +118,84 @@ func (a *Boolean) MarshalJSON() ([]byte, error) {
}
func arrayEqualBoolean(left, right *Boolean) bool {
- for i := 0; i < left.Len(); i++ {
- if left.IsNull(i) {
- continue
+ if useScalarBooleanEquality(left) {
+ for i := range left.Len() {
+ if !left.IsNull(i) && left.Value(i) != right.Value(i) {
+ return false
+ }
}
- if left.Value(i) != right.Value(i) {
+ return true
+ }
+
+ leftOffset := int64(left.Offset())
+ rightOffset := int64(right.Offset())
+ length := int64(left.Len())
+ if left.NullN() == 0 {
+ return booleanBitsEqual(left.values, right.values, leftOffset,
rightOffset, length)
+ }
+
+ runs := bitutils.NewSetBitRunReader(left.NullBitmapBytes(), leftOffset,
length)
+ for {
+ run := runs.NextRun()
+ if run.Length == 0 {
+ return true
+ }
+
+ leftStart := leftOffset + run.Pos
+ rightStart := rightOffset + run.Pos
+ if !booleanBitsEqual(left.values, right.values, leftStart,
rightStart, run.Length) {
+ return false
+ }
+ }
+}
+
+func booleanBitsEqual(left, right []byte, leftOffset, rightOffset, length
int64) bool {
+ const scalarThreshold = 8
+ if length <= scalarThreshold {
+ for i := int64(0); i < length; i++ {
+ if bitutil.BitIsSet(left, int(leftOffset+i)) !=
bitutil.BitIsSet(right, int(rightOffset+i)) {
+ return false
+ }
+ }
+ return true
+ }
+
+ // Align corresponding runs before using BitmapEquals so its
byte-aligned fast path
+ // can compare the bulk of the run without setting up bitmap word
readers.
+ if leftOffset%8 == rightOffset%8 && leftOffset%8 != 0 {
+ prefix := int64(8) - leftOffset%8
+ if !booleanBitsEqual(left, right, leftOffset, rightOffset,
prefix) {
+ return false
+ }
+ leftOffset += prefix
+ rightOffset += prefix
+ length -= prefix
+ }
+ return bitutil.BitmapEquals(left, right, leftOffset, rightOffset,
length)
+}
+
+func useScalarBooleanEquality(values *Boolean) bool {
+ if values.NullN() == 0 {
+ return false
+ }
+
+ // Sampling avoids the run-reader overhead when valid values are highly
fragmented.
+ const (
+ sampleRuns = 8
+ minAverageRunLength = 16
+ )
+ runs := bitutils.NewSetBitRunReader(
+ values.NullBitmapBytes(), int64(values.Offset()),
int64(values.Len()),
+ )
+ validValues := int64(0)
+ for range sampleRuns {
+ run := runs.NextRun()
+ if run.Length == 0 {
return false
}
+ validValues += run.Length
}
- return true
+ return validValues < sampleRuns*minAverageRunLength
}
var (
diff --git a/arrow/array/boolean_equality_benchmark_test.go
b/arrow/array/boolean_equality_benchmark_test.go
new file mode 100644
index 00000000..4ef0fed8
--- /dev/null
+++ b/arrow/array/boolean_equality_benchmark_test.go
@@ -0,0 +1,88 @@
+// 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/array"
+)
+
+var booleanEqualityResult bool
+
+func BenchmarkBooleanEquality(b *testing.B) {
+ for _, length := range []int{64 * 1024, 1024 * 1024} {
+ b.Run(fmt.Sprintf("len_%d", length), func(b *testing.B) {
+ for _, tc := range []struct {
+ name string
+ valid func(int) bool
+ mismatchIndex int
+ offset int
+ }{
+ {name: "all_valid_equal", mismatchIndex: -1},
+ {name: "clustered_10_percent_null", valid:
func(i int) bool { return i >= length/10 }, mismatchIndex: -1},
+ {name: "periodic_10_percent_null", valid:
func(i int) bool { return i%10 != 0 }, mismatchIndex: -1},
+ {name: "alternating_null", valid: func(i int)
bool { return i%2 != 0 }, mismatchIndex: -1},
+ {name: "mismatch_first", mismatchIndex: 0},
+ {name: "mismatch_last", mismatchIndex: length -
1},
+ {name: "unaligned_equal", mismatchIndex: -1,
offset: 3},
+ } {
+ benchmarkBooleanEqualityCase(b, length,
tc.valid, tc.name, tc.mismatchIndex, tc.offset)
+ }
+ })
+ }
+}
+
+func benchmarkBooleanEqualityCase(
+ b *testing.B, length int, validValue func(int) bool, name string,
mismatchIndex, offset int,
+) {
+ b.Helper()
+
+ totalLength := length + offset
+ leftValues := make([]bool, totalLength)
+ rightValues := make([]bool, totalLength)
+ valid := make([]bool, totalLength)
+ for i := range totalLength {
+ leftValues[i] = i%3 == 0
+ rightValues[i] = leftValues[i]
+ valid[i] = i < offset || validValue == nil ||
validValue(i-offset)
+ }
+ if mismatchIndex >= 0 {
+ rightValues[offset+mismatchIndex] =
!rightValues[offset+mismatchIndex]
+ }
+
+ leftBase := makeBooleanEqualityArray(leftValues, valid)
+ rightBase := makeBooleanEqualityArray(rightValues, valid)
+ left := array.NewSlice(leftBase, int64(offset), int64(totalLength))
+ right := array.NewSlice(rightBase, int64(offset), int64(totalLength))
+ b.Cleanup(func() {
+ left.Release()
+ right.Release()
+ leftBase.Release()
+ rightBase.Release()
+ })
+
+ b.Run(name, func(b *testing.B) {
+ b.ReportAllocs()
+ b.ResetTimer()
+ for b.Loop() {
+ booleanEqualityResult = array.Equal(left, right)
+ }
+ })
+}
diff --git a/arrow/array/boolean_equality_test.go
b/arrow/array/boolean_equality_test.go
new file mode 100644
index 00000000..ed25aa6b
--- /dev/null
+++ b/arrow/array/boolean_equality_test.go
@@ -0,0 +1,108 @@
+// 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/array"
+ "github.com/apache/arrow-go/v18/arrow/memory"
+ "github.com/stretchr/testify/assert"
+)
+
+func TestArrayEqualBooleanIgnoresNullValues(t *testing.T) {
+ valid := []bool{true, false, true, false, true, true, false, true,
true, false, true}
+ leftValues := []bool{true, false, false, true, true, false, false,
true, false, true, true}
+ rightValues := append([]bool(nil), leftValues...)
+ for i, isValid := range valid {
+ if !isValid {
+ rightValues[i] = !rightValues[i]
+ }
+ }
+
+ left := makeBooleanEqualityArray(leftValues, valid)
+ defer left.Release()
+ right := makeBooleanEqualityArray(rightValues, valid)
+ defer right.Release()
+
+ assert.True(t, array.Equal(left, right))
+
+ leftSlice := array.NewSlice(left, 1, int64(left.Len()-1))
+ defer leftSlice.Release()
+ rightSlice := array.NewSlice(right, 1, int64(right.Len()-1))
+ defer rightSlice.Release()
+ assert.True(t, array.Equal(leftSlice, rightSlice))
+
+ rightValues[7] = !rightValues[7]
+ different := makeBooleanEqualityArray(rightValues, valid)
+ defer different.Release()
+ differentSlice := array.NewSlice(different, 1, int64(different.Len()-1))
+ defer differentSlice.Release()
+ assert.False(t, array.Equal(leftSlice, differentSlice))
+}
+
+func TestArrayEqualBooleanWithDifferentOffsets(t *testing.T) {
+ values := []bool{true, false, true, true, false, false, true, false,
true, true, false, true}
+ valid := []bool{true, true, false, true, true, false, true, true, true,
false, true, true}
+
+ leftBase := makeBooleanEqualityArray(append([]bool{false}, values...),
append([]bool{true}, valid...))
+ defer leftBase.Release()
+ rightBase := makeBooleanEqualityArray(append([]bool{false, true,
false}, values...), append([]bool{true, true, true}, valid...))
+ defer rightBase.Release()
+
+ left := array.NewSlice(leftBase, 1, int64(leftBase.Len()))
+ defer left.Release()
+ right := array.NewSlice(rightBase, 3, int64(rightBase.Len()))
+ defer right.Release()
+
+ assert.True(t, array.Equal(left, right))
+}
+
+func TestArrayEqualBooleanByValidRuns(t *testing.T) {
+ const length = 130
+ values := make([]bool, length)
+ valid := make([]bool, length)
+ for i := range values {
+ values[i] = i%3 == 0
+ valid[i] = i >= 5 && i < 125
+ }
+ rightValues := append([]bool(nil), values...)
+ for i, isValid := range valid {
+ if !isValid {
+ rightValues[i] = !rightValues[i]
+ }
+ }
+
+ left := makeBooleanEqualityArray(values, valid)
+ defer left.Release()
+ right := makeBooleanEqualityArray(rightValues, valid)
+ defer right.Release()
+ assert.True(t, array.Equal(left, right))
+
+ rightValues[77] = !rightValues[77]
+ different := makeBooleanEqualityArray(rightValues, valid)
+ defer different.Release()
+ assert.False(t, array.Equal(left, different))
+}
+
+func makeBooleanEqualityArray(values, valid []bool) *array.Boolean {
+ builder := array.NewBooleanBuilder(memory.DefaultAllocator)
+ defer builder.Release()
+ builder.AppendValues(values, valid)
+ return builder.NewBooleanArray()
+}
