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 913751ce perf(bitutil): process unaligned bitmap operations by word
(#1437)
913751ce is described below
commit 913751ce29539b4fd3d41bd1e48a5f821521a8e4
Author: Minh Vu <[email protected]>
AuthorDate: Mon Nov 2 21:22:18 2026 +0100
perf(bitutil): process unaligned bitmap operations by word (#1437)
## What
Process unaligned bitmap operations with direct word writes when the
output is byte aligned.
## Why
The current path builds word readers and a writer for each operation.
## Implementation
- Write full words, bytes, and partial tails directly.
- Keep the existing path for short inputs, unaligned output, and
overlapping buffers.
- Cover AND, OR, AND-NOT, XOR, and XNOR.
## Benchmark
AND only, input offsets 1 and 3, byte-aligned output. Apple M1 Pro, Go
1.26.3, median of 3 runs:
- **32 bytes:** 277 → 24.4 ns (**11.4x faster**).
- **512 bytes:** 1,174 → 248 ns (**4.7x faster**).
- **8 KiB:** 9.13 → 4.96 µs (**1.8x faster**).
- Allocations for these cases: **192 → 0 B/op**.
An unaligned-output fallback control at 512 bytes measured 1,269 → 1,339
ns; an alternating comparison measured 856 → 861 ns. These are bitmap
operation benchmarks, not end-to-end Arrow results.
`GOMAXPROCS=1 go test ./arrow/bitutil -run '^$' -bench
'^BenchmarkBitmapUnalignedOps/(32B|512B|8192B)/(left1-right3-out0|left1-right3-out1)/(tail0|tail3)/and$'
-benchmem -benchtime=150ms -count=3 -cpu=1`
---------
Signed-off-by: Minh Vu <[email protected]>
---
arrow/bitutil/bitmaps.go | 77 ++++++++++++++++++++++
arrow/bitutil/bitmaps_test.go | 149 ++++++++++++++++++++++++++++++++++++++++++
2 files changed, 226 insertions(+)
diff --git a/arrow/bitutil/bitmaps.go b/arrow/bitutil/bitmaps.go
index bcd20716..0b29318a 100644
--- a/arrow/bitutil/bitmaps.go
+++ b/arrow/bitutil/bitmaps.go
@@ -710,7 +710,84 @@ func alignedBitmapOp(op bitOp, left, right []byte,
lOffset, rOffset int64, out [
}
}
+// bitmapByteRangesOverlap reports whether two byte slices share any addressed
bytes.
+// A bitmap op may write into either input, so the direct word loop is only
used
+// when writes cannot overwrite unread source bytes.
+func bitmapByteRangesOverlap(a, b []byte) bool {
+ if len(a) == 0 || len(b) == 0 {
+ return false
+ }
+ aPtr := uintptr(unsafe.Pointer(&a[0]))
+ bPtr := uintptr(unsafe.Pointer(&b[0]))
+ if aPtr < bPtr {
+ return bPtr-aPtr < uintptr(len(a))
+ }
+ return aPtr-bPtr < uintptr(len(b))
+}
+
func unalignedBitmapOp(op bitOp, left, right []byte, lOffset, rOffset int64,
out []byte, outOffset int64, length int64) {
+ // A byte-aligned output can be written directly in 64-bit words.
+ // Avoid constructing word readers and a writer for larger, non-aliasing
+ // slices. Keep the existing path for overlapping buffers, short inputs,
+ // and destinations with a bit offset.
+ // Require at least two 64-bit words to amortize the extra checks.
+ if outOffset%8 == 0 && length >= 128 {
+ leftStart, rightStart := lOffset/8, rOffset/8
+ outStart := outOffset / 8
+ leftBytes := left[leftStart :
leftStart+BytesForBits(lOffset%8+length)]
+ rightBytes := right[rightStart :
rightStart+BytesForBits(rOffset%8+length)]
+ outBytes := out[outStart : outStart+BytesForBits(length)]
+ if !bitmapByteRangesOverlap(outBytes, leftBytes) &&
+ !bitmapByteRangesOverlap(outBytes, rightBytes) {
+ leftShift, rightShift := uint(lOffset%8),
uint(rOffset%8)
+ nwords := length / 64
+ for i := int64(0); i < nwords; i++ {
+ lword := binary.LittleEndian.Uint64(leftBytes)
+ if leftShift != 0 {
+ lword = (lword >> leftShift) |
uint64(leftBytes[8])<<(64-leftShift)
+ }
+ rword := binary.LittleEndian.Uint64(rightBytes)
+ if rightShift != 0 {
+ rword = (rword >> rightShift) |
uint64(rightBytes[8])<<(64-rightShift)
+ }
+ binary.LittleEndian.PutUint64(outBytes,
op.opWord(lword, rword))
+ leftBytes = leftBytes[8:]
+ rightBytes = rightBytes[8:]
+ outBytes = outBytes[8:]
+ }
+ // Complete bytes at the end also avoid the
reader/writer path.
+ remaining := length % 64
+ for remaining >= 8 {
+ lbyte := leftBytes[0] >> leftShift
+ if leftShift != 0 {
+ lbyte |= leftBytes[1] << (8 - leftShift)
+ }
+ rbyte := rightBytes[0] >> rightShift
+ if rightShift != 0 {
+ rbyte |= rightBytes[1] << (8 -
rightShift)
+ }
+ outBytes[0] = op.opByte(lbyte, rbyte)
+ leftBytes = leftBytes[1:]
+ rightBytes = rightBytes[1:]
+ outBytes = outBytes[1:]
+ remaining -= 8
+ }
+ if remaining != 0 {
+ lbyte := leftBytes[0] >> leftShift
+ if int64(leftShift)+remaining > 8 {
+ lbyte |= leftBytes[1] << (8 - leftShift)
+ }
+ rbyte := rightBytes[0] >> rightShift
+ if int64(rightShift)+remaining > 8 {
+ rbyte |= rightBytes[1] << (8 -
rightShift)
+ }
+ mask := byte((1 << uint(remaining)) - 1)
+ outBytes[0] = (outBytes[0] &^ mask) |
(op.opByte(lbyte, rbyte) & mask)
+ }
+ return
+ }
+ }
+
leftRdr := NewBitmapWordReader(left, int(lOffset), int(length))
rightRdr := NewBitmapWordReader(right, int(rOffset), int(length))
writer := NewBitmapWordWriter(out, int(outOffset), int(length))
diff --git a/arrow/bitutil/bitmaps_test.go b/arrow/bitutil/bitmaps_test.go
index 2936485b..b86c1c99 100644
--- a/arrow/bitutil/bitmaps_test.go
+++ b/arrow/bitutil/bitmaps_test.go
@@ -964,3 +964,152 @@ func TestBitmapTransferZeroLengthNil(t *testing.T) {
bitutil.CopyBitmap(nil, 0, 0, nil, 0)
bitutil.InvertBitmap(nil, 0, 0, nil, 0)
}
+
+type bitmapBinaryOp struct {
+ name string
+ run func([]byte, []byte, int64, int64, []byte, int64, int64)
+ want func(bool, bool) bool
+}
+
+var unalignedBitmapOps = []bitmapBinaryOp{
+ {"and", bitutil.BitmapAnd, func(a, b bool) bool { return a && b }},
+ {"or", bitutil.BitmapOr, func(a, b bool) bool { return a || b }},
+ {"and-not", bitutil.BitmapAndNot, func(a, b bool) bool { return a && !b
}},
+ {"xor", bitutil.BitmapXor, func(a, b bool) bool { return a != b }},
+ {"xnor", bitutil.BitmapXnor, func(a, b bool) bool { return a == b }},
+}
+
+// Use reproducible mixed bit patterns without adding a random source
dependency.
+func fillUnalignedBitmapPattern(data []byte, seed uint32) {
+ x := seed | 1
+ for i := range data {
+ x ^= x << 13
+ x ^= x >> 17
+ x ^= x << 5
+ data[i] = byte(x)
+ }
+}
+
+func TestBitmapUnalignedOpsDirectWords(t *testing.T) {
+ lengths := []int64{0, 1, 2, 7, 8, 9, 15, 16, 31, 32, 63, 64, 65,
+ 127, 128, 129, 191, 192, 193, 255, 256, 257, 511, 512, 513,
1025}
+
+ for _, length := range lengths {
+ for leftOffset := int64(0); leftOffset < 8; leftOffset++ {
+ for rightOffset := int64(0); rightOffset < 8;
rightOffset++ {
+ left := make([]byte, (leftOffset+length+7)/8+1)
+ right := make([]byte,
(rightOffset+length+7)/8+1)
+ fillUnalignedBitmapPattern(left,
uint32(123+length+leftOffset))
+ fillUnalignedBitmapPattern(right,
uint32(456+length+rightOffset))
+ for _, outOffset := range []int64{0, 1, 7} {
+ for _, op := range unalignedBitmapOps {
+ out := make([]byte,
(outOffset+length+7)/8+1)
+ fillUnalignedBitmapPattern(out,
uint32(789+length+outOffset))
+ want := bytes.Clone(out)
+ for i := int64(0); i < length;
i++ {
+ a :=
bitutil.BitIsSet(left, int(leftOffset+i))
+ b :=
bitutil.BitIsSet(right, int(rightOffset+i))
+ bitutil.SetBitTo(want,
int(outOffset+i), op.want(a, b))
+ }
+ op.run(left, right, leftOffset,
rightOffset, out, outOffset, length)
+ if !bytes.Equal(out, want) {
+ t.Fatalf("%s length=%d
offsets=%d/%d/%d: got %x, want %x",
+ op.name,
length, leftOffset, rightOffset, outOffset, out, want)
+ }
+ }
+ }
+ }
+ }
+ }
+}
+
+func TestBitmapUnalignedOpsAliasedOutput(t *testing.T) {
+ const length int64 = 263
+ // The direct path must fall back when the output aliases either input.
+ for _, op := range unalignedBitmapOps {
+ for _, aliasLeft := range []bool{true, false} {
+ left := make([]byte, (length+7)/8+1)
+ right := make([]byte, (length+3+7)/8+1)
+ fillUnalignedBitmapPattern(left, 12345)
+ fillUnalignedBitmapPattern(right, 67890)
+
+ var out []byte
+ var leftOffset, rightOffset int64
+ if aliasLeft {
+ out, leftOffset, rightOffset = left, 0, 3
+ } else {
+ out, leftOffset, rightOffset = right, 3, 0
+ // Both source ranges are large enough for the
chosen offsets.
+ left = make([]byte, (length+leftOffset+7)/8+1)
+ fillUnalignedBitmapPattern(left, 12345)
+ }
+ beforeLeft := bytes.Clone(left)
+ beforeRight := bytes.Clone(right)
+ want := bytes.Clone(out)
+ for i := int64(0); i < length; i++ {
+ a := bitutil.BitIsSet(beforeLeft,
int(leftOffset+i))
+ b := bitutil.BitIsSet(beforeRight,
int(rightOffset+i))
+ bitutil.SetBitTo(want, int(i), op.want(a, b))
+ }
+ op.run(left, right, leftOffset, rightOffset, out, 0,
length)
+ if !bytes.Equal(out, want) {
+ t.Fatalf("%s aliasLeft=%v: got %x, want %x",
op.name, aliasLeft, out, want)
+ }
+ }
+ }
+}
+
+var bitmapUnalignedBenchmarkSink byte
+
+func BenchmarkBitmapUnalignedOps(b *testing.B) {
+ for _, nbytes := range []int{32, 512, 8192, 131072} {
+ for _, offsets := range []struct{ left, right, out int64 }{
+ {0, 1, 0}, {1, 3, 0}, {7, 4, 0}, {1, 3, 1},
+ } {
+ left := make([]byte, int64(nbytes)+2)
+ right := make([]byte, int64(nbytes)+2)
+ out := make([]byte, int64(nbytes)+2)
+ fillUnalignedBitmapPattern(left, 13579)
+ fillUnalignedBitmapPattern(right, 24680)
+ for _, tailBits := range []int64{0, 3} {
+ for _, op := range unalignedBitmapOps {
+
b.Run(fmt.Sprintf("%dB/left%d-right%d-out%d/tail%d/%s",
+ nbytes, offsets.left,
offsets.right, offsets.out, tailBits, op.name), func(b *testing.B) {
+ b.SetBytes(int64(2 * nbytes))
+ b.ReportAllocs()
+ for b.Loop() {
+ op.run(left, right,
offsets.left, offsets.right, out, offsets.out, int64(nbytes*8)-tailBits)
+ }
+ bitmapUnalignedBenchmarkSink ^=
out[0]
+ })
+ }
+ }
+ }
+ }
+}
+
+func TestBitmapUnalignedExactBuffers(t *testing.T) {
+ for _, length := range []int64{128, 129, 135, 191, 192, 193, 255, 256,
257} {
+ for leftOffset := int64(0); leftOffset < 16; leftOffset++ {
+ for rightOffset := int64(0); rightOffset < 16;
rightOffset++ {
+ left := make([]byte, (leftOffset+length+7)/8)
+ right := make([]byte, (rightOffset+length+7)/8)
+ fillUnalignedBitmapPattern(left,
uint32(123+length+leftOffset))
+ fillUnalignedBitmapPattern(right,
uint32(456+length+rightOffset))
+ for _, outOffset := range []int64{0, 8, 16} {
+ for _, op := range unalignedBitmapOps {
+ out :=
bytes.Repeat([]byte{0xa5}, int((outOffset+length+7)/8))
+ want := bytes.Clone(out)
+ for i := int64(0); i < length;
i++ {
+ bitutil.SetBitTo(want,
int(outOffset+i), op.want(bitutil.BitIsSet(left, int(leftOffset+i)),
bitutil.BitIsSet(right, int(rightOffset+i))))
+ }
+ op.run(left, right, leftOffset,
rightOffset, out, outOffset, length)
+ if !bytes.Equal(out, want) {
+ t.Fatalf("%s length=%d
offsets=%d/%d/%d: got %x, want %x", op.name, length, leftOffset, rightOffset,
outOffset, out, want)
+ }
+ }
+ }
+ }
+ }
+ }
+}
