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 0bf2789b perf(bitutil): accelerate misaligned bitmap equality (#1414)
0bf2789b is described below
commit 0bf2789bed952ea322f17fe35a231beb2403b49b
Author: Minh Vu <[email protected]>
AuthorDate: Mon Oct 26 18:54:32 2026 +0100
perf(bitutil): accelerate misaligned bitmap equality (#1414)
## What
Speed up BitmapEquals for sliced, misaligned ranges.
## Why
Unaligned slices use word readers and allocate temporary buffers.
## Implementation
- Use masked edge bytes and bytes.Equal for matching byte offsets.
- Read packed words directly for other offsets.
- Keep bounds checks and add parity cases for offsets and tails.
## Benchmark
**6.53x geometric mean** across 32 isolated cases. Unaligned cases drop
from 2 allocs/op to 0.
---------
Co-authored-by: Matt Topol <[email protected]>
---
arrow/bitutil/bitmap_equals_offset_test.go | 104 +++++++++++++++++++++
.../bitmap_equals_offsets_benchmark_test.go | 70 ++++++++++++++
arrow/bitutil/bitmaps.go | 92 +++++++++++++++---
3 files changed, 251 insertions(+), 15 deletions(-)
diff --git a/arrow/bitutil/bitmap_equals_offset_test.go
b/arrow/bitutil/bitmap_equals_offset_test.go
new file mode 100644
index 00000000..935f16f2
--- /dev/null
+++ b/arrow/bitutil/bitmap_equals_offset_test.go
@@ -0,0 +1,104 @@
+// 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 bitutil_test
+
+import (
+ "fmt"
+ "testing"
+
+ "github.com/apache/arrow-go/v18/arrow/bitutil"
+)
+
+func TestBitmapEqualsOffsetParity(t *testing.T) {
+ offsets := []int{0, 1, 2, 3, 7, 8, 11, 15, 16, 19, 31, 64, 71}
+ lengths := []int{0, 1, 2, 3, 7, 8, 9, 15, 16, 17, 31, 32, 63, 64, 65,
66, 127, 128, 129, 255, 256, 257, 511, 512, 513}
+ for _, length := range lengths {
+ for _, lo := range offsets {
+ for _, ro := range offsets {
+ left := make([]byte,
bitutil.BytesForBits(int64(lo+length)))
+ right := make([]byte,
bitutil.BytesForBits(int64(ro+length)))
+ for i := range left {
+ left[i] = 0xa5
+ }
+ for i := range right {
+ right[i] = 0x5a
+ }
+ for i := 0; i < length; i++ {
+ val := (i*31+i/7)%11 < 5
+ bitutil.SetBitTo(left, lo+i, val)
+ bitutil.SetBitTo(right, ro+i, val)
+ }
+ if !bitutil.BitmapEquals(left, right,
int64(lo), int64(ro), int64(length)) {
+ t.Fatalf("equal ranges: len=%d left=%d
right=%d", length, lo, ro)
+ }
+ for _, pos := range []int{0, length / 2, length
- 1} {
+ if pos < 0 || pos >= length {
+ continue
+ }
+ index := ro + pos
+ right[index/8] ^= byte(1) <<
uint(index%8)
+ if bitutil.BitmapEquals(left, right,
int64(lo), int64(ro), int64(length)) {
+ t.Fatalf("missed difference:
len=%d left=%d right=%d pos=%d", length, lo, ro, pos)
+ }
+ right[index/8] ^= byte(1) <<
uint(index%8)
+ }
+ }
+ }
+ }
+}
+
+func TestBitmapEqualsLargeOffsetParity(t *testing.T) {
+ const length = 1 << 20
+ for _, pair := range []struct{ left, right int }{{0, 0}, {3, 11}, {7,
15}, {3, 6}, {0, 7}, {15, 31}} {
+ t.Run(fmt.Sprintf("%d_%d", pair.left, pair.right), func(t
*testing.T) {
+ left := make([]byte,
bitutil.BytesForBits(length+int64(pair.left)))
+ right := make([]byte,
bitutil.BytesForBits(length+int64(pair.right)))
+ for i := 0; i < length; i++ {
+ v := (i*7+i/29)%11 < 5
+ bitutil.SetBitTo(left, pair.left+i, v)
+ bitutil.SetBitTo(right, pair.right+i, v)
+ }
+ if !bitutil.BitmapEquals(left, right, int64(pair.left),
int64(pair.right), length) {
+ t.Fatal("large equal bitmap ranges differ")
+ }
+ index := pair.right + length - 1
+ right[index/8] ^= 1 << uint(index%8)
+ if bitutil.BitmapEquals(left, right, int64(pair.left),
int64(pair.right), length) {
+ t.Fatal("missed difference at end of large
range")
+ }
+ })
+ }
+}
+
+func TestBitmapEqualsUnalignedBounds(t *testing.T) {
+ for _, tc := range []struct {
+ name string
+ lo, ro, length int64
+ }{
+ {name: "same offset", lo: 3, ro: 11, length: 128},
+ {name: "different offset", lo: 3, ro: 6, length: 128},
+ } {
+ t.Run(tc.name, func(t *testing.T) {
+ defer func() {
+ if recover() == nil {
+ t.Fatal("expected out-of-bounds range
to panic")
+ }
+ }()
+ bitutil.BitmapEquals([]byte{0xff}, []byte{0}, tc.lo,
tc.ro, tc.length)
+ })
+ }
+}
diff --git a/arrow/bitutil/bitmap_equals_offsets_benchmark_test.go
b/arrow/bitutil/bitmap_equals_offsets_benchmark_test.go
new file mode 100644
index 00000000..d731780b
--- /dev/null
+++ b/arrow/bitutil/bitmap_equals_offsets_benchmark_test.go
@@ -0,0 +1,70 @@
+// 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 bitutil_test
+
+import (
+ "fmt"
+ "math/rand"
+ "testing"
+
+ "github.com/apache/arrow-go/v18/arrow/bitutil"
+)
+
+var bitmapEqualsOffsetBenchmarkResult bool
+
+func BenchmarkBitmapEqualsOffsets(b *testing.B) {
+ for _, nbits := range []int{64, 1024, 65536, 1048576} {
+ for _, pair := range []struct {
+ name string
+ lo, ro int
+ }{
+ {name: "aligned", lo: 0, ro: 0},
+ {name: "same3", lo: 3, ro: 11},
+ {name: "same7", lo: 7, ro: 15},
+ {name: "different", lo: 3, ro: 6},
+ } {
+ for _, lastMismatch := range []bool{false, true} {
+ name := "equal"
+ if lastMismatch {
+ name = "lastMismatch"
+ }
+ left := make([]byte,
bitutil.BytesForBits(int64(nbits+pair.lo)))
+ right := make([]byte,
bitutil.BytesForBits(int64(nbits+pair.ro)))
+ rng := rand.New(rand.NewSource(55))
+ _, _ = rng.Read(left)
+ for i := 0; i < nbits; i++ {
+ if bitutil.BitIsSet(left, pair.lo+i) {
+ bitutil.SetBit(right, pair.ro+i)
+ }
+ }
+ if lastMismatch {
+ i := pair.ro + nbits - 1
+ right[i/8] ^= 1 << uint(i%8)
+ }
+ b.Run(fmt.Sprintf("bits=%d/%s/%s", nbits,
pair.name, name), func(b *testing.B) {
+ b.SetBytes(int64((nbits + 7) / 8 * 2))
+ b.ReportAllocs()
+ for b.Loop() {
+
bitmapEqualsOffsetBenchmarkResult = bitutil.BitmapEquals(
+ left, right,
int64(pair.lo), int64(pair.ro), int64(nbits),
+ )
+ }
+ })
+ }
+ }
+ }
+}
diff --git a/arrow/bitutil/bitmaps.go b/arrow/bitutil/bitmaps.go
index ac61397a..e0e332ad 100644
--- a/arrow/bitutil/bitmaps.go
+++ b/arrow/bitutil/bitmaps.go
@@ -18,6 +18,7 @@ package bitutil
import (
"bytes"
+ "encoding/binary"
"errors"
"math/bits"
"unsafe"
@@ -658,17 +659,17 @@ func BitmapXnorAlloc(mem memory.Allocator, left, right
[]byte, lOffset, rOffset
return BitmapOpAlloc(mem, bitXnorOp, left, right, lOffset, rOffset,
length, outOffset)
}
+// BitmapEquals reports whether the selected ranges have the same bits.
+// Bytes outside the compared ranges are ignored.
func BitmapEquals(left, right []byte, lOffset, rOffset int64, length int64)
bool {
if lOffset%8 == 0 && rOffset%8 == 0 {
- // byte aligned, fast path, can use bytes.Equal (memcmp)
+ // Byte aligned: use bytes.Equal for the bulk and compare
trailing bits.
byteLen := length / 8
lStart := lOffset / 8
rStart := rOffset / 8
if !bytes.Equal(left[lStart:lStart+byteLen],
right[rStart:rStart+byteLen]) {
return false
}
-
- // check trailing bits
for i := (length / 8) * 8; i < length; i++ {
if BitIsSet(left, int(lOffset+i)) != BitIsSet(right,
int(rOffset+i)) {
return false
@@ -677,25 +678,86 @@ func BitmapEquals(left, right []byte, lOffset, rOffset
int64, length int64) bool
return true
}
- lrdr := NewBitmapWordReader(left, int(lOffset), int(length))
- rrdr := NewBitmapWordReader(right, int(rOffset), int(length))
+ // Slice up front, as the word-reader path did, so out-of-bounds
+ // ranges still panic even when the first compared bits differ.
+ lshift, rshift := uint(lOffset%8), uint(rOffset%8)
+ left = left[lOffset/8 : lOffset/8+(int64(lshift)+length+7)/8]
+ right = right[rOffset/8 : rOffset/8+(int64(rshift)+length+7)/8]
- nwords := lrdr.Words()
- for nwords > 0 {
- nwords--
- if lrdr.NextWord() != rrdr.NextWord() {
+ if lshift == rshift {
+ // Equal intra-byte offsets: compare the leading partial byte,
+ // all complete middle bytes using memcmp, then the trailing
bits.
+ if length == 0 {
+ return true
+ }
+ leading := length
+ if leading > int64(8-lshift) {
+ leading = int64(8 - lshift)
+ }
+ mask := byte((1<<uint(leading))-1) << lshift
+ if (left[0]^right[0])&mask != 0 {
+ return false
+ }
+ if leading == length {
+ return true
+ }
+ left, right = left[1:], right[1:]
+ length -= leading
+ nbytes := length / 8
+ if !bytes.Equal(left[:nbytes], right[:nbytes]) {
return false
}
+ if tail := length % 8; tail != 0 {
+ mask := byte((1 << uint(tail)) - 1)
+ return (left[nbytes]^right[nbytes])&mask == 0
+ }
+ return true
}
- nbytes := lrdr.TrailingBytes()
- for nbytes > 0 {
- nbytes--
- lbt, _ := lrdr.NextTrailingByte()
- rbt, _ := rrdr.NextTrailingByte()
- if lbt != rbt {
+ // Different offsets: unpack directly from the input slices without
+ // constructing two BitmapWordReaders. Compare full 64-bit words first.
+ for length >= 64 {
+ lword := binary.LittleEndian.Uint64(left)
+ if lshift != 0 {
+ lword = (lword >> lshift) | uint64(left[8])<<(64-lshift)
+ }
+ rword := binary.LittleEndian.Uint64(right)
+ if rshift != 0 {
+ rword = (rword >> rshift) |
uint64(right[8])<<(64-rshift)
+ }
+ if lword != rword {
return false
}
+ left, right = left[8:], right[8:]
+ length -= 64
+ }
+
+ for length >= 8 {
+ lbyte := left[0] >> lshift
+ if lshift != 0 {
+ lbyte |= left[1] << (8 - lshift)
+ }
+ rbyte := right[0] >> rshift
+ if rshift != 0 {
+ rbyte |= right[1] << (8 - rshift)
+ }
+ if lbyte != rbyte {
+ return false
+ }
+ left, right = left[1:], right[1:]
+ length -= 8
+ }
+ if length != 0 {
+ lbyte := left[0] >> lshift
+ if length+int64(lshift) > 8 {
+ lbyte |= left[1] << (8 - lshift)
+ }
+ rbyte := right[0] >> rshift
+ if length+int64(rshift) > 8 {
+ rbyte |= right[1] << (8 - rshift)
+ }
+ mask := byte((1 << uint(length)) - 1)
+ return (lbyte^rbyte)&mask == 0
}
return true
}
