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 802431b7 perf(arrow/array): compare fixed-size binary values in bulk
(#1347)
802431b7 is described below
commit 802431b7521df5465c684bdc60abd921cf92f2fe
Author: Minh Vu <[email protected]>
AuthorDate: Tue Oct 6 16:24:58 2026 +0200
perf(arrow/array): compare fixed-size binary values in bulk (#1347)
### What
- Compare valid fixed-size binary values in contiguous byte ranges.
- Keep scalar comparison for short or fragmented arrays.
### Why
- Reduce per-value checks for larger arrays.
### Implementation
- Add null, offset, and validity bitmap cases.
- Benchmark 8/32/128-byte values at 4/8/64/1K/64K items with all-valid,
1%-null, alternating-null, and clustered-null patterns.
### Benchmark results
- Compared with `upstream/main` (`954bc067`) on an Apple M1 Pro with Go
1.26.3; median of 5 runs.
- At 65,536 values, all-valid was 1.4–16.1x faster, 1%-null 1.3–12.5x,
and clustered-null 2.1–13.8x.
- Alternating-null results were within 7% of baseline.
---
arrow/array/binary.go | 4 +
arrow/array/fixedsize_binary.go | 45 +++
.../fixedsize_binary_equality_benchmark_test.go | 131 ++++++++
arrow/array/fixedsize_binary_equality_test.go | 345 +++++++++++++++++++++
4 files changed, 525 insertions(+)
diff --git a/arrow/array/binary.go b/arrow/array/binary.go
index c2fde2af..1095d090 100644
--- a/arrow/array/binary.go
+++ b/arrow/array/binary.go
@@ -465,6 +465,10 @@ func useScalarVariableWidthEquality(values arrow.Array)
bool {
if values.NullN() == 0 {
return false
}
+ return useScalarEqualityForValidityRuns(values)
+}
+
+func useScalarEqualityForValidityRuns(values arrow.Array) bool {
if values.Len() <= 64 || len(values.NullBitmapBytes()) == 0 {
return true
}
diff --git a/arrow/array/fixedsize_binary.go b/arrow/array/fixedsize_binary.go
index 567bcba0..b14846b0 100644
--- a/arrow/array/fixedsize_binary.go
+++ b/arrow/array/fixedsize_binary.go
@@ -23,6 +23,8 @@ import (
"strings"
"github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/bitutil"
+ "github.com/apache/arrow-go/v18/internal/bitutils"
"github.com/apache/arrow-go/v18/internal/json"
)
@@ -117,6 +119,49 @@ func (a *FixedSizeBinary) MarshalJSON() ([]byte, error) {
}
func arrayEqualFixedSizeBinary(left, right *FixedSizeBinary) bool {
+ if left.Len() < 8 {
+ return arrayEqualFixedSizeBinaryScalar(left, right)
+ }
+
+ width := int(left.bytewidth)
+ leftStart := left.Offset() * width
+ leftEnd := leftStart + left.Len()*width
+ rightStart := right.Offset() * width
+ rightEnd := rightStart + right.Len()*width
+ leftBitmap := left.NullBitmapBytes()
+ if len(leftBitmap) == 0 ||
+ (left.NullN() == 0 && bitutil.CountSetBits(leftBitmap,
left.Offset(), left.Len()) == left.Len()) {
+ return bytes.Equal(left.valueBytes[leftStart:leftEnd],
right.valueBytes[rightStart:rightEnd])
+ }
+ if useScalarEqualityForValidityRuns(left) {
+ return arrayEqualFixedSizeBinaryScalar(left, right)
+ }
+
+ runs := bitutils.NewSetBitRunReader(
+ leftBitmap, int64(left.Offset()), int64(left.Len()),
+ )
+ for {
+ run := runs.NextRun()
+ if run.Length == 0 {
+ return true
+ }
+
+ start := int(run.Pos)
+ end := start + int(run.Length)
+ leftRunStart := (left.Offset() + start) * width
+ leftRunEnd := (left.Offset() + end) * width
+ rightRunStart := (right.Offset() + start) * width
+ rightRunEnd := (right.Offset() + end) * width
+ if !bytes.Equal(
+ left.valueBytes[leftRunStart:leftRunEnd],
+ right.valueBytes[rightRunStart:rightRunEnd],
+ ) {
+ return false
+ }
+ }
+}
+
+func arrayEqualFixedSizeBinaryScalar(left, right *FixedSizeBinary) bool {
for i := 0; i < left.Len(); i++ {
if left.IsNull(i) {
continue
diff --git a/arrow/array/fixedsize_binary_equality_benchmark_test.go
b/arrow/array/fixedsize_binary_equality_benchmark_test.go
new file mode 100644
index 00000000..e9e22f81
--- /dev/null
+++ b/arrow/array/fixedsize_binary_equality_benchmark_test.go
@@ -0,0 +1,131 @@
+// 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 fixedSizeBinaryEqualityResult bool
+
+func BenchmarkFixedSizeBinaryEquality(b *testing.B) {
+ const length = 64 * 1024
+ for _, width := range []int{8, 32, 128} {
+ for _, size := range []int{4, 8, 64, 1024, length} {
+ for _, pattern := range []struct {
+ name string
+ valid func(int) []bool
+ }{
+ {name: "all_valid"},
+ {name: "materialized_all_valid", valid: func(n
int) []bool {
+ valid := make([]bool, n)
+ for i := range valid {
+ valid[i] = true
+ }
+ return valid
+ }},
+ {name: "one_percent_null", valid: func(n int)
[]bool {
+ valid := make([]bool, n)
+ for i := range valid {
+ valid[i] = i%100 != 0
+ }
+ return valid
+ }},
+ {name: "alternating_null", valid: func(n int)
[]bool {
+ valid := make([]bool, n)
+ for i := range valid {
+ valid[i] = i%2 == 0
+ }
+ return valid
+ }},
+ {name: "clustered_null", valid: func(n int)
[]bool {
+ valid := make([]bool, n)
+ for i := range valid {
+ valid[i] = i >= n/2
+ }
+ return valid
+ }},
+ } {
+ b.Run(fmt.Sprintf("width_%d/length_%d/%s",
width, size, pattern.name), func(b *testing.B) {
+ leftValues := make([]byte, size*width)
+ for i := range leftValues {
+ leftValues[i] = byte(i*31 +
i/width*17)
+ }
+ rightValues := append([]byte(nil),
leftValues...)
+ var valid []bool
+ if pattern.valid != nil {
+ valid = pattern.valid(size)
+ }
+ nulls := 0
+ for i, isValid := range valid {
+ if !isValid {
+ nulls++
+ rightValues[i*width]++
+ }
+ }
+
+ left :=
makeFixedSizeBinaryEqualityArray(width, leftValues, valid, size, 0, nulls)
+ right :=
makeFixedSizeBinaryEqualityArray(width, rightValues, valid, size, 0, nulls)
+ b.Cleanup(left.Release)
+ b.Cleanup(right.Release)
+
+ b.ReportAllocs()
+ b.SetBytes(int64(size * width))
+ for b.Loop() {
+ fixedSizeBinaryEqualityResult =
array.Equal(left, right)
+ }
+ })
+ }
+ }
+ }
+}
+
+func BenchmarkFixedSizeBinaryEqualityMismatch(b *testing.B) {
+ const size = 64 * 1024
+ for _, width := range []int{8, 32, 128} {
+ for _, mismatch := range []struct {
+ name string
+ row int
+ }{
+ {name: "first", row: 0},
+ {name: "last", row: size - 1},
+ } {
+ b.Run(fmt.Sprintf("width_%d/%s", width, mismatch.name),
func(b *testing.B) {
+ leftValues := make([]byte, size*width)
+ for i := range leftValues {
+ leftValues[i] = byte(i*31 + i/width*17)
+ }
+ rightValues := append([]byte(nil),
leftValues...)
+ rightValues[mismatch.row*width]++
+
+ left := makeFixedSizeBinaryEqualityArray(width,
leftValues, nil, size, 0, 0)
+ right :=
makeFixedSizeBinaryEqualityArray(width, rightValues, nil, size, 0, 0)
+ b.Cleanup(left.Release)
+ b.Cleanup(right.Release)
+
+ b.ReportAllocs()
+ b.SetBytes(int64(size * width))
+ for b.Loop() {
+ fixedSizeBinaryEqualityResult =
array.Equal(left, right)
+ }
+ })
+ }
+ }
+}
diff --git a/arrow/array/fixedsize_binary_equality_test.go
b/arrow/array/fixedsize_binary_equality_test.go
new file mode 100644
index 00000000..3c06a2e4
--- /dev/null
+++ b/arrow/array/fixedsize_binary_equality_test.go
@@ -0,0 +1,345 @@
+// 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/bitutil"
+ "github.com/apache/arrow-go/v18/arrow/memory"
+ "github.com/stretchr/testify/assert"
+)
+
+func TestFixedSizeBinaryEqualityByValidRuns(t *testing.T) {
+ valid := []bool{true, true, false, true, false, false, true, true}
+ leftNulls := []byte("aaaabbbbLEFTddddLEFTLEFTgggghhhh")
+ rightNulls := []byte("aaaabbbbxxxxddddyyyyzzzzgggghhhh")
+
+ leftOffsetValues := concatFixedSizeBinaryRows("LPRF", "one1", "left",
"two2", "thre", "LSUF")
+ rightOffsetValues := concatFixedSizeBinaryRows("RPRF", "free", "one1",
"diff", "two2", "thre", "RSUF")
+ leftOffsetValid := []bool{true, true, false, true, true, true}
+ rightOffsetValid := []bool{true, true, true, false, true, true, true}
+
+ allValid := make([]bool, 8)
+ for i := range allValid {
+ allValid[i] = true
+ }
+
+ tests := []struct {
+ name string
+ leftValues, rightValues []byte
+ leftValid, rightValid []bool
+ length int
+ leftOffset, rightOffset int
+ leftNulls, rightNulls int
+ want bool
+ }{
+ {
+ name: "equal values",
+ leftValues: concatFixedSizeBinaryRows("aaaa", "bbbb",
"cccc", "dddd", "eeee", "ffff", "gggg", "hhhh"),
+ rightValues: concatFixedSizeBinaryRows("aaaa", "bbbb",
"cccc", "dddd", "eeee", "ffff", "gggg", "hhhh"),
+ length: 8,
+ want: true,
+ },
+ {
+ name: "ignore bytes under null slots",
+ leftValues: leftNulls,
+ rightValues: rightNulls,
+ leftValid: valid,
+ rightValid: valid,
+ length: len(valid),
+ leftNulls: 3,
+ rightNulls: 3,
+ want: true,
+ },
+ {
+ name: "detect mismatch in a later valid run",
+ leftValues: concatFixedSizeBinaryRows("aaaa", "bbbb",
"cccc", "dddd", "eeee", "ffff", "gggg", "hhhh"),
+ rightValues: concatFixedSizeBinaryRows("aaaa", "bbbb",
"cccc", "dddd", "eeee", "ffff", "GGGG", "hhhh"),
+ leftValid: valid,
+ rightValid: valid,
+ length: 8,
+ leftNulls: 3,
+ rightNulls: 3,
+ want: false,
+ },
+ {
+ name: "different physical offsets with nulls",
+ leftValues: leftOffsetValues,
+ rightValues: rightOffsetValues,
+ leftValid: leftOffsetValid,
+ rightValid: rightOffsetValid,
+ length: 4,
+ leftOffset: 1,
+ rightOffset: 2,
+ leftNulls: 1,
+ rightNulls: 1,
+ want: true,
+ },
+ {
+ name: "materialized bitmap remains authoritative
with zero declared nulls",
+ leftValues: concatFixedSizeBinaryRows("aaaa", "LEFT",
"cccc", "dddd", "eeee", "ffff", "gggg", "hhhh"),
+ rightValues: concatFixedSizeBinaryRows("aaaa", "DIFF",
"cccc", "dddd", "eeee", "ffff", "gggg", "hhhh"),
+ leftValid: []bool{true, false, true, true, true,
true, true, true},
+ rightValid: []bool{true, false, true, true, true,
true, true, true},
+ length: 8,
+ want: true,
+ },
+ {
+ name: "absent and all-valid materialized
bitmaps",
+ leftValues: concatFixedSizeBinaryRows("aaaa", "bbbb",
"cccc", "dddd", "eeee", "ffff", "gggg", "hhhh"),
+ rightValues: concatFixedSizeBinaryRows("aaaa", "bbbb",
"cccc", "dddd", "eeee", "ffff", "gggg", "hhhh"),
+ rightValid: allValid,
+ length: 8,
+ want: true,
+ },
+ {
+ name: "both materialized all-valid bitmaps",
+ leftValues: concatFixedSizeBinaryRows("aaaa", "bbbb",
"cccc", "dddd", "eeee", "ffff", "gggg", "hhhh"),
+ rightValues: concatFixedSizeBinaryRows("aaaa", "bbbb",
"cccc", "dddd", "eeee", "ffff", "gggg", "hhhh"),
+ leftValid: allValid,
+ rightValid: allValid,
+ length: 8,
+ want: true,
+ },
+ {
+ name: "different validity positions with the
same null count",
+ leftValues: concatFixedSizeBinaryRows("aaaa", "bbbb",
"cccc", "dddd", "eeee", "ffff", "gggg", "hhhh"),
+ rightValues: concatFixedSizeBinaryRows("aaaa", "bbbb",
"cccc", "dddd", "eeee", "ffff", "gggg", "hhhh"),
+ leftValid: []bool{true, false, true, true, true,
true, true, true},
+ rightValid: []bool{true, true, false, true, true,
true, true, true},
+ length: 8,
+ leftNulls: 1,
+ rightNulls: 1,
+ want: false,
+ },
+ {
+ name: "all-null payloads are ignored",
+ leftValues: concatFixedSizeBinaryRows("LEFT", "LEFT",
"LEFT", "LEFT", "LEFT", "LEFT", "LEFT", "LEFT"),
+ rightValues: concatFixedSizeBinaryRows("DIFF", "DIFF",
"DIFF", "DIFF", "DIFF", "DIFF", "DIFF", "DIFF"),
+ leftValid: []bool{false, false, false, false, false,
false, false, false},
+ rightValid: []bool{false, false, false, false, false,
false, false, false},
+ length: 8,
+ leftNulls: 8,
+ rightNulls: 8,
+ want: true,
+ },
+ {
+ name: "empty arrays without buffers",
+ length: 0,
+ want: true,
+ },
+ }
+
+ for _, tc := range tests {
+ t.Run(tc.name, func(t *testing.T) {
+ left := makeFixedSizeBinaryEqualityArray(4,
tc.leftValues, tc.leftValid, tc.length, tc.leftOffset, tc.leftNulls)
+ defer left.Release()
+ right := makeFixedSizeBinaryEqualityArray(4,
tc.rightValues, tc.rightValid, tc.length, tc.rightOffset, tc.rightNulls)
+ defer right.Release()
+
+ assert.Equal(t, tc.want, array.Equal(left, right))
+ assert.Equal(t, tc.want, array.Equal(right, left))
+ })
+ }
+}
+
+func TestFixedSizeBinaryEqualityLongValidRuns(t *testing.T) {
+ const (
+ width = 4
+ length = 256
+ )
+
+ valid := make([]bool, length)
+ leftValues := make([]byte, length*width)
+ rightValues := make([]byte, length*width)
+ nulls := 0
+ for i := range length {
+ valid[i] = (i/8)%2 == 0
+ if !valid[i] {
+ nulls++
+ }
+ for j := range width {
+ value := byte(i*7 + j*11)
+ leftValues[i*width+j] = value
+ rightValues[i*width+j] = value
+ }
+ if !valid[i] {
+ rightValues[i*width]++
+ }
+ }
+
+ left := makeFixedSizeBinaryEqualityArray(width, leftValues, valid,
length, 0, nulls)
+ defer left.Release()
+ right := makeFixedSizeBinaryEqualityArray(width, rightValues, valid,
length, 0, nulls)
+ assert.True(t, array.Equal(left, right))
+ right.Release()
+
+ rightValues[240*width]++
+ right = makeFixedSizeBinaryEqualityArray(width, rightValues, valid,
length, 0, nulls)
+ defer right.Release()
+ assert.False(t, array.Equal(left, right))
+}
+
+func TestFixedSizeBinaryEqualityWithZeroDeclaredNullCount(t *testing.T) {
+ const (
+ width = 4
+ length = 128
+ )
+
+ valid := make([]bool, length)
+ leftValues := make([]byte, length*width)
+ rightValues := make([]byte, length*width)
+ for i := range length {
+ valid[i] = (i/8)%2 == 0
+ for j := range width {
+ value := byte(i*7 + j*11)
+ leftValues[i*width+j] = value
+ rightValues[i*width+j] = value
+ }
+ if !valid[i] {
+ rightValues[i*width]++
+ }
+ }
+
+ left := makeFixedSizeBinaryEqualityArray(width, leftValues, valid,
length, 0, 0)
+ defer left.Release()
+ right := makeFixedSizeBinaryEqualityArray(width, rightValues, valid,
length, 0, 0)
+ defer right.Release()
+
+ assert.True(t, array.Equal(left, right))
+}
+
+func TestFixedSizeBinaryEqualityWithDifferentLongOffsets(t *testing.T) {
+ const (
+ width = 4
+ length = 128
+ leftOffset = 1
+ rightOffset = 3
+ )
+
+ leftValues := make([]byte, (leftOffset+length)*width)
+ rightValues := make([]byte, (rightOffset+length)*width)
+ leftValid := make([]bool, leftOffset+length)
+ rightValid := make([]bool, rightOffset+length)
+ nulls := 0
+ for i := range length {
+ isValid := (i/8)%2 == 0
+ leftValid[leftOffset+i] = isValid
+ rightValid[rightOffset+i] = isValid
+ if !isValid {
+ nulls++
+ }
+ for j := range width {
+ value := byte(i*7 + j*11)
+ leftValues[(leftOffset+i)*width+j] = value
+ rightValues[(rightOffset+i)*width+j] = value
+ }
+ if !isValid {
+ rightValues[(rightOffset+i)*width]++
+ }
+ }
+
+ left := makeFixedSizeBinaryEqualityArray(width, leftValues, leftValid,
length, leftOffset, nulls)
+ defer left.Release()
+ right := makeFixedSizeBinaryEqualityArray(width, rightValues,
rightValid, length, rightOffset, nulls)
+ assert.True(t, array.Equal(left, right))
+ right.Release()
+
+ rightValues[(rightOffset+112)*width]++
+ right = makeFixedSizeBinaryEqualityArray(width, rightValues,
rightValid, length, rightOffset, nulls)
+ defer right.Release()
+ assert.False(t, array.Equal(left, right))
+}
+
+func TestFixedSizeBinaryEqualityWithFragmentedValidity(t *testing.T) {
+ const (
+ width = 4
+ length = 128
+ )
+
+ valid := make([]bool, length)
+ leftValues := make([]byte, length*width)
+ rightValues := make([]byte, length*width)
+ nulls := 0
+ for i := range length {
+ valid[i] = i%2 == 0
+ if !valid[i] {
+ nulls++
+ }
+ for j := range width {
+ value := byte(i*7 + j*11)
+ leftValues[i*width+j] = value
+ rightValues[i*width+j] = value
+ }
+ if !valid[i] {
+ rightValues[i*width]++
+ }
+ }
+
+ left := makeFixedSizeBinaryEqualityArray(width, leftValues, valid,
length, 0, nulls)
+ defer left.Release()
+ right := makeFixedSizeBinaryEqualityArray(width, rightValues, valid,
length, 0, nulls)
+ assert.True(t, array.Equal(left, right))
+ right.Release()
+
+ rightValues[126*width]++
+ right = makeFixedSizeBinaryEqualityArray(width, rightValues, valid,
length, 0, nulls)
+ defer right.Release()
+ assert.False(t, array.Equal(left, right))
+}
+
+func makeFixedSizeBinaryEqualityArray(
+ width int, values []byte, valid []bool, length, offset, nulls int,
+) *array.FixedSizeBinary {
+ var validityBuffer *memory.Buffer
+ if valid != nil {
+ validity := make([]byte, (len(valid)+7)/8)
+ for i, isValid := range valid {
+ if isValid {
+ bitutil.SetBit(validity, i)
+ }
+ }
+ validityBuffer = memory.NewBufferBytes(validity)
+ defer validityBuffer.Release()
+ }
+
+ valuesBuffer := memory.NewBufferBytes(values)
+ defer valuesBuffer.Release()
+
+ data := array.NewData(
+ &arrow.FixedSizeBinaryType{ByteWidth: width},
+ length,
+ []*memory.Buffer{validityBuffer, valuesBuffer},
+ nil,
+ nulls,
+ offset,
+ )
+ defer data.Release()
+
+ return array.NewFixedSizeBinaryData(data)
+}
+
+func concatFixedSizeBinaryRows(rows ...string) []byte {
+ var values []byte
+ for _, row := range rows {
+ values = append(values, row...)
+ }
+ return values
+}
