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 0c599c7d perf(arrow/bitutil): bulk-transfer unaligned bitmap ranges
(#1416)
0c599c7d is described below
commit 0c599c7d1f6dd6b15dd89951ef78e2d844b18713
Author: Minh Vu <[email protected]>
AuthorDate: Tue Oct 27 17:20:17 2026 +0100
perf(arrow/bitutil): bulk-transfer unaligned bitmap ranges (#1416)
## What
Speed up unaligned CopyBitmap and InvertBitmap ranges.
## Why
The reader and writer paths process shifted ranges in small steps and
allocate.
## Implementation
- Use masks for partial bytes and bulk writes for aligned spans.
- Decode shifted spans in 64-bit chunks.
- Preserve overlap handling and add offset and aliasing coverage.
## Benchmark
**5.35x geometric mean** across unaligned isolated cases.
Non-overlapping cases drop from 1 alloc/op to 0.
---------
Co-authored-by: Matt Topol <[email protected]>
---
arrow/bitutil/bitmaps.go | 106 ++++++++++++++++++-----
arrow/bitutil/bitmaps_test.go | 72 +++++++++++++++
arrow/bitutil/bitmaps_transfer_benchmark_test.go | 32 +++++++
3 files changed, 188 insertions(+), 22 deletions(-)
diff --git a/arrow/bitutil/bitmaps.go b/arrow/bitutil/bitmaps.go
index db1c0abc..bcd20716 100644
--- a/arrow/bitutil/bitmaps.go
+++ b/arrow/bitutil/bitmaps.go
@@ -478,6 +478,87 @@ const (
transferInvert
)
+// transferBitmapUnaligned copies full destination bytes in bulk, handling only
+// the first and last partial bytes separately. The caller has checked buffer
+// bounds and snapshotted any overlapping source and destination byte spans.
+func transferBitmapUnaligned(mode transferMode, src []byte, srcOffset, length
int, dst []byte, dstOffset int) {
+ // Keep the bits preceding a non-byte-aligned destination untouched.
+ if bit := dstOffset & 7; bit != 0 {
+ count := min(length, 8-bit)
+ shift := uint(srcOffset & 7)
+ value := src[srcOffset/8] >> shift
+ if int(shift)+count > 8 {
+ value |= src[srcOffset/8+1] << (8 - shift)
+ }
+ if mode == transferInvert {
+ value = ^value
+ }
+ mask := byte((1<<uint(count))-1) << uint(bit)
+ at := dstOffset / 8
+ dst[at] = (dst[at] &^ mask) | ((value << uint(bit)) & mask)
+ srcOffset += count
+ dstOffset += count
+ length -= count
+ }
+
+ if length >= 8 {
+ nbytes := length / 8
+ out := dst[dstOffset/8 : dstOffset/8+nbytes]
+ in := src[srcOffset/8:]
+ shift := uint(srcOffset & 7)
+ if shift == 0 {
+ if mode == transferCopy {
+ copy(out, in[:nbytes])
+ } else {
+ for len(out) >= 8 {
+ binary.LittleEndian.PutUint64(out,
^binary.LittleEndian.Uint64(in))
+ out = out[8:]
+ in = in[8:]
+ }
+ for i := range out {
+ out[i] = ^in[i]
+ }
+ }
+ } else {
+ // A shifted 64-bit source word needs nine source bytes.
+ for len(out) >= 8 {
+ value := binary.LittleEndian.Uint64(in)>>shift
| uint64(in[8])<<(64-shift)
+ if mode == transferInvert {
+ value = ^value
+ }
+ binary.LittleEndian.PutUint64(out, value)
+ in = in[8:]
+ out = out[8:]
+ }
+ for i := range out {
+ value := in[i]>>shift | in[i+1]<<(8-shift)
+ if mode == transferInvert {
+ value = ^value
+ }
+ out[i] = value
+ }
+ }
+ srcOffset += nbytes * 8
+ dstOffset += nbytes * 8
+ length -= nbytes * 8
+ }
+
+ // Preserve any bits beyond the requested destination range.
+ if length > 0 {
+ shift := uint(srcOffset & 7)
+ value := src[srcOffset/8] >> shift
+ if int(shift)+length > 8 {
+ value |= src[srcOffset/8+1] << (8 - shift)
+ }
+ if mode == transferInvert {
+ value = ^value
+ }
+ mask := byte((1 << uint(length)) - 1)
+ at := dstOffset / 8
+ dst[at] = (dst[at] &^ mask) | (value & mask)
+ }
+}
+
func transferBitmap(mode transferMode, src []byte, srcOffset, length int, dst
[]byte, dstOffset int) {
if length == 0 {
// if there's nothing to write, end early.
@@ -506,29 +587,10 @@ func transferBitmap(mode transferMode, src []byte,
srcOffset, length int, dst []
bitOffset := srcOffset % 8
destBitOffset := dstOffset % 8
- // slow path, one of the bitmaps are not byte aligned.
+ // Transfer bytes and words directly instead of creating word readers
and
+ // writers for unaligned ranges.
if bitOffset != 0 || destBitOffset != 0 {
- rdr := NewBitmapWordReader(src, srcOffset, length)
- wr := NewBitmapWordWriter(dst, dstOffset, length)
-
- nwords := rdr.Words()
- for nwords > 0 {
- nwords--
- if mode == transferInvert {
- wr.PutNextWord(^rdr.NextWord())
- } else {
- wr.PutNextWord(rdr.NextWord())
- }
- }
- nbytes := rdr.TrailingBytes()
- for nbytes > 0 {
- nbytes--
- bt, validBits := rdr.NextTrailingByte()
- if mode == transferInvert {
- bt = ^bt
- }
- wr.PutNextTrailingByte(bt, validBits)
- }
+ transferBitmapUnaligned(mode, src, srcOffset, length, dst,
dstOffset)
return
}
diff --git a/arrow/bitutil/bitmaps_test.go b/arrow/bitutil/bitmaps_test.go
index 46dada0b..2936485b 100644
--- a/arrow/bitutil/bitmaps_test.go
+++ b/arrow/bitutil/bitmaps_test.go
@@ -17,6 +17,7 @@
package bitutil_test
import (
+ "bytes"
"fmt"
"math/rand"
"strconv"
@@ -892,3 +893,74 @@ func TestBitmapOpsBoundaries(t *testing.T) {
})
}
}
+
+func transferScalarReference(invert bool, src []byte, srcOffset, length int,
dst []byte, dstOffset int) {
+ snapshot := bytes.Clone(src)
+ for i := range length {
+ bit := bitutil.BitIsSet(snapshot, srcOffset+i)
+ if invert {
+ bit = !bit
+ }
+ bitutil.SetBitTo(dst, dstOffset+i, bit)
+ }
+}
+
+func TestBitmapTransferOffsetsParity(t *testing.T) {
+ rng := rand.New(rand.NewSource(20261024))
+ lengths := []int{0, 1, 2, 3, 4, 7, 8, 9, 15, 16, 17, 31, 32, 33, 63,
64, 65, 127, 128, 129, 511, 512, 513, 1024}
+ for _, invert := range []bool{false, true} {
+ for srcOffset := range 16 {
+ for dstOffset := range 16 {
+ for _, n := range lengths {
+ src := make([]byte, (srcOffset+n+7)/8)
+ dst := make([]byte, (dstOffset+n+7)/8)
+ rng.Read(src)
+ rng.Read(dst)
+ want := bytes.Clone(dst)
+ transferScalarReference(invert, src,
srcOffset, n, want, dstOffset)
+ if invert {
+ bitutil.InvertBitmap(src,
srcOffset, n, dst, dstOffset)
+ } else {
+ bitutil.CopyBitmap(src,
srcOffset, n, dst, dstOffset)
+ }
+ if !bytes.Equal(dst, want) {
+ t.Fatalf("invert=%t
srcOffset=%d dstOffset=%d len=%d", invert, srcOffset, dstOffset, n)
+ }
+ }
+ }
+ }
+ }
+}
+
+func TestBitmapTransferSubsliceOverlap(t *testing.T) {
+ rng := rand.New(rand.NewSource(20261025))
+ for _, invert := range []bool{false, true} {
+ for srcByte := range 6 {
+ for dstByte := range 6 {
+ for srcOffset := range 8 {
+ for dstOffset := range 8 {
+ for _, n := range []int{0, 1,
5, 8, 31, 64, 65, 127, 512} {
+ backing := make([]byte,
128)
+ rng.Read(backing)
+ want :=
bytes.Clone(backing)
+
transferScalarReference(invert, backing[srcByte:], srcOffset, n,
want[dstByte:], dstOffset)
+ if invert {
+
bitutil.InvertBitmap(backing[srcByte:], srcOffset, n, backing[dstByte:],
dstOffset)
+ } else {
+
bitutil.CopyBitmap(backing[srcByte:], srcOffset, n, backing[dstByte:],
dstOffset)
+ }
+ if
!bytes.Equal(backing, want) {
+
t.Fatalf("invert=%t srcByte=%d dstByte=%d srcBit=%d dstBit=%d len=%d", invert,
srcByte, dstByte, srcOffset, dstOffset, n)
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+}
+
+func TestBitmapTransferZeroLengthNil(t *testing.T) {
+ bitutil.CopyBitmap(nil, 0, 0, nil, 0)
+ bitutil.InvertBitmap(nil, 0, 0, nil, 0)
+}
diff --git a/arrow/bitutil/bitmaps_transfer_benchmark_test.go
b/arrow/bitutil/bitmaps_transfer_benchmark_test.go
index fa4a18cc..315a14a0 100644
--- a/arrow/bitutil/bitmaps_transfer_benchmark_test.go
+++ b/arrow/bitutil/bitmaps_transfer_benchmark_test.go
@@ -17,6 +17,7 @@
package bitutil_test
import (
+ "fmt"
"strconv"
"testing"
@@ -90,3 +91,34 @@ func BenchmarkTransferBitmapAliasing(b *testing.B) {
})
}
}
+
+var bitmapTransferBenchmarkSink byte
+
+func BenchmarkBitmapTransferOffsets(b *testing.B) {
+ for _, operation := range []struct {
+ name string
+ transfer func([]byte, int, int, []byte, int)
+ }{
+ {name: "copy", transfer: bitutil.CopyBitmap},
+ {name: "invert", transfer: bitutil.InvertBitmap},
+ } {
+ for _, length := range []int{64, 1024, 65536, 1048576} {
+ for _, offsets := range [][2]int{{0, 0}, {3, 3}, {3,
6}, {0, 5}, {7, 0}} {
+ name := fmt.Sprintf("%s/%dbits/%d-%d",
operation.name, length, offsets[0], offsets[1])
+ b.Run(name, func(b *testing.B) {
+ src := make([]byte, (length+64)/8+16)
+ dst := make([]byte, len(src))
+ for i := range src {
+ src[i] = byte(i*31 + 7)
+ }
+ b.ReportAllocs()
+ b.SetBytes(int64(length / 8))
+ for b.Loop() {
+ operation.transfer(src,
offsets[0], length, dst, offsets[1])
+ }
+ bitmapTransferBenchmarkSink = dst[10]
+ })
+ }
+ }
+ }
+}
