You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@arrow.apache.org by ze...@apache.org on 2026/10/21 17:55:14 UTC
(arrow-go) branch main updated: fix(arrow/bitutil): preserve overlapping bitmap transfers (#1389)
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 54075bfd fix(arrow/bitutil): preserve overlapping bitmap transfers (#1389)
54075bfd is described below
commit 54075bfded0be54c11e828a43931570b6ad30828
Author: Minh Vu <vu...@gmail.com>
AuthorDate: Wed Oct 21 19:55:09 2026 +0200
fix(arrow/bitutil): preserve overlapping bitmap transfers (#1389)
**What**
- Support overlapping source and destination ranges for bitmap copies
and inversions.
**Why**
- Writes can overwrite source bits before the transfer reads them.
**Implementation**
- Detect overlapping byte ranges and copy the source bytes before
writing.
- Keep the non-overlapping path allocation-free.
### Benchmark
Go 1.26.3, Apple M1 Pro, 64 KiB aligned ranges; medians of 10 x 300 ms
runs (before -> after).
| Metric | Before | After | Change |
|---|---:|---:|---:|
| Disjoint copy (ns/op) | 840 | 816 | 2.9% faster |
| Disjoint invert (µs/op) | 20.8 | 20.9 | 0.5% slower |
| Overlapping copy (µs/op) | 0.88 | 5.68 | 6.5x slower |
| Overlapping invert (µs/op) | 142 | 29.2 | 4.9x faster |
| Overlapping operations allocations | 0 allocs/op | 1 alloc/op (64 KiB)
| +1 allocation |
---
arrow/bitutil/bitmaps.go | 22 +++++-
arrow/bitutil/bitmaps_test.go | 53 ++++++++++++++
arrow/bitutil/bitmaps_transfer_benchmark_test.go | 92 ++++++++++++++++++++++++
3 files changed, 166 insertions(+), 1 deletion(-)
diff --git a/arrow/bitutil/bitmaps.go b/arrow/bitutil/bitmaps.go
index c4cef33a..ac61397a 100644
--- a/arrow/bitutil/bitmaps.go
+++ b/arrow/bitutil/bitmaps.go
@@ -421,6 +421,25 @@ func transferBitmap(mode transferMode, src []byte, srcOffset, length int, dst []
return
}
+ // Both transfer paths can overwrite source bytes before reading them when
+ // the ranges alias. Only snapshot the source when their byte spans overlap.
+ srcStart := srcOffset / 8
+ dstStart := dstOffset / 8
+ srcBytes := src[srcStart : srcStart+int(BytesForBits(int64(srcOffset%8)+int64(length)))]
+ dstBytes := dst[dstStart : dstStart+int(BytesForBits(int64(dstOffset%8)+int64(length)))]
+ srcPtr := uintptr(unsafe.Pointer(&srcBytes[0]))
+ dstPtr := uintptr(unsafe.Pointer(&dstBytes[0]))
+ var overlaps bool
+ if srcPtr < dstPtr {
+ overlaps = dstPtr-srcPtr < uintptr(len(srcBytes))
+ } else {
+ overlaps = srcPtr-dstPtr < uintptr(len(dstBytes))
+ }
+ if overlaps {
+ src = bytes.Clone(srcBytes)
+ srcOffset %= 8
+ }
+
bitOffset := srcOffset % 8
destBitOffset := dstOffset % 8
@@ -480,12 +499,13 @@ func transferBitmap(mode transferMode, src []byte, srcOffset, length int, dst []
// CopyBitmap copies the bitmap indicated by src, starting at bit offset srcOffset,
// and copying length bits into dst, starting at bit offset dstOffset.
+// Source and destination ranges may overlap.
func CopyBitmap(src []byte, srcOffset, length int, dst []byte, dstOffset int) {
transferBitmap(transferCopy, src, srcOffset, length, dst, dstOffset)
}
// InvertBitmap copies a bit range of a bitmap, inverting it as it copies
-// over into the destination.
+// over into the destination. Source and destination ranges may overlap.
func InvertBitmap(src []byte, srcOffset, length int, dst []byte, dstOffset int) {
transferBitmap(transferInvert, src, srcOffset, length, dst, dstOffset)
}
diff --git a/arrow/bitutil/bitmaps_test.go b/arrow/bitutil/bitmaps_test.go
index 0f836837..46dada0b 100644
--- a/arrow/bitutil/bitmaps_test.go
+++ b/arrow/bitutil/bitmaps_test.go
@@ -214,6 +214,59 @@ func TestCopyBitmap(t *testing.T) {
}
}
+func TestTransferBitmapOverlapping(t *testing.T) {
+ tests := []struct {
+ name string
+ srcSlice, dstSlice int
+ srcOffset int
+ dstOffset int
+ length int
+ }{
+ {name: "aligned right partial", srcOffset: 0, dstOffset: 8, length: 31},
+ {name: "aligned left partial", srcOffset: 8, dstOffset: 0, length: 31},
+ {name: "aligned full bytes", srcOffset: 0, dstOffset: 16, length: 64},
+ {name: "unaligned right", srcOffset: 3, dstOffset: 11, length: 145},
+ {name: "unaligned left", srcOffset: 11, dstOffset: 3, length: 145},
+ {name: "same byte different bit offsets", srcOffset: 0, dstOffset: 1, length: 9},
+ {name: "same bit range", srcOffset: 5, dstOffset: 5, length: 145},
+ {name: "aliased slice views", srcSlice: 2, dstSlice: 3, srcOffset: 3, dstOffset: 2, length: 145},
+ {name: "adjacent bits", srcOffset: 5, dstOffset: 6, length: 1},
+ {name: "disjoint ranges", srcOffset: 0, dstOffset: 256, length: 32},
+ }
+
+ for _, tt := range tests {
+ for _, invert := range []bool{false, true} {
+ t.Run(fmt.Sprintf("%s/invert=%t", tt.name, invert), func(t *testing.T) {
+ original := make([]byte, 64)
+ for i := range original {
+ original[i] = byte(i*37 + 0x5b)
+ }
+ got := append([]byte(nil), original...)
+ want := append([]byte(nil), original...)
+
+ srcStart := tt.srcSlice*8 + tt.srcOffset
+ dstStart := tt.dstSlice*8 + tt.dstOffset
+ for i := 0; i < tt.length; i++ {
+ bit := bitutil.BitIsSet(original, srcStart+i)
+ if invert {
+ bit = !bit
+ }
+ bitutil.SetBitTo(want, dstStart+i, bit)
+ }
+
+ src := got[tt.srcSlice:]
+ dst := got[tt.dstSlice:]
+ if invert {
+ bitutil.InvertBitmap(src, tt.srcOffset, tt.length, dst, tt.dstOffset)
+ } else {
+ bitutil.CopyBitmap(src, tt.srcOffset, tt.length, dst, tt.dstOffset)
+ }
+ assert.Equal(t, want, got)
+ })
+ }
+ }
+}
+
func benchmarkCopyBitmapN(b *testing.B, offsetSrc, offsetDest, n int) {
nbits := n * 8
// random bytes
diff --git a/arrow/bitutil/bitmaps_transfer_benchmark_test.go b/arrow/bitutil/bitmaps_transfer_benchmark_test.go
new file mode 100644
index 00000000..fa4a18cc
--- /dev/null
+++ b/arrow/bitutil/bitmaps_transfer_benchmark_test.go
@@ -0,0 +1,92 @@
+// 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 (
+ "strconv"
+ "testing"
+
+ "github.com/apache/arrow-go/v18/arrow/bitutil"
+)
+
+// BenchmarkTransferBitmapAliasing measures the overlap snapshot path and the
+// allocation-free path, including disjoint ranges in the same backing buffer.
+func BenchmarkTransferBitmapAliasing(b *testing.B) {
+ operations := []struct {
+ name string
+ transfer func([]byte, int, int, []byte, int)
+ }{
+ {name: "copy", transfer: bitutil.CopyBitmap},
+ {name: "invert", transfer: bitutil.InvertBitmap},
+ }
+ offsets := []struct {
+ name string
+ src, dst int
+ }{
+ {name: "aligned"},
+ {name: "unaligned", src: 3, dst: 5},
+ }
+ layouts := []struct {
+ name string
+ separate, disjoint bool
+ srcByte, dstByte int
+ }{
+ {name: "separate", separate: true},
+ {name: "disjoint-same-buffer", disjoint: true},
+ {name: "overlap-forward", dstByte: 1},
+ {name: "overlap-backward", srcByte: 1},
+ {name: "same-range"},
+ }
+
+ for _, operation := range operations {
+ b.Run(operation.name, func(b *testing.B) {
+ for _, nbytes := range []int{32, 1024, 64 * 1024} {
+ b.Run(strconv.Itoa(nbytes), func(b *testing.B) {
+ for _, offset := range offsets {
+ b.Run(offset.name, func(b *testing.B) {
+ for _, layout := range layouts {
+ b.Run(layout.name, func(b *testing.B) {
+ var src, dst []byte
+ if layout.separate {
+ src = make([]byte, nbytes+8)
+ dst = make([]byte, nbytes+8)
+ } else {
+ backing := make([]byte, 2*nbytes+32)
+ srcByte, dstByte := layout.srcByte, layout.dstByte
+ if layout.disjoint {
+ dstByte = nbytes + 16
+ }
+ src, dst = backing[srcByte:], backing[dstByte:]
+ }
+ for i := range src {
+ src[i] = byte(i*37 + 0x5b)
+ }
+
+ b.SetBytes(int64(nbytes))
+ b.ReportAllocs()
+ for b.Loop() {
+ operation.transfer(src, offset.src, nbytes*8, dst, offset.dst)
+ }
+ })
+ }
+ })
+ }
+ })
+ }
+ })
+ }
+}