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 9cc8131a perf(bitutil): pack boolean bitmap writes by byte (#1402)
9cc8131a is described below
commit 9cc8131aec84edfa4bf7a4cc66ce36fd64ad96ad
Author: Minh Vu <[email protected]>
AuthorDate: Tue Oct 27 16:08:19 2026 +0100
perf(bitutil): pack boolean bitmap writes by byte (#1402)
## What
Pack booleans eight bits at a time in `BitmapWriter.AppendBools`.
## Why
Reduce per-bit work when writing boolean arrays into bitmaps.
## Implementation
- Keep partial-byte writes and adjacent bits intact.
- Add chunked-write coverage and an `AppendBools` benchmark.
## Benchmark
Go 1.26.3, Apple M1 Pro (`darwin/arm64`), `GOMAXPROCS=1`; 10 runs of 200
ms per case. Base `de0c94e` vs head `5cd78dc`.
| Metric | Before | After | Change |
| --- | ---: | ---: | ---: |
| AppendBools, 64 values, aligned | 149.40 ns/op | 19.13 ns/op | -87.19%
|
| AppendBools, 64 values, offset 3, split | 162.45 ns/op | 35.83 ns/op |
-77.94% |
| AppendBools, 1,024 values, aligned | 2,444.0 ns/op | 258.6 ns/op |
-89.42% |
| AppendBools, 1,024 values, offset 3, split | 2,443.0 ns/op | 276.2
ns/op | -88.69% |
| AppendBools, 8,192 values, aligned | 20.497 µs/op | 2.017 µs/op |
-90.16% |
| AppendBools, 8,192 values, offset 3, split | 19.643 µs/op | 2.078
µs/op | -89.42% |
| AppendBools, 65,536 values, aligned | 158.86 µs/op | 16.24 µs/op |
-89.78% |
| AppendBools, 65,536 values, offset 3, split | 156.13 µs/op | 16.31
µs/op | -89.56% |
| Geometric mean, 16 cases | 5.849 µs/op | 706.0 ns/op | -87.93% |
All 16 cases improved by 76.85%–90.16%. Allocations remained at 0 B/op
and 0 allocs/op.
---
arrow/bitutil/bitmaps.go | 88 ++++++++++++++---
arrow/bitutil/bitmaps_append_bools_test.go | 151 +++++++++++++++++++++++++++++
2 files changed, 226 insertions(+), 13 deletions(-)
diff --git a/arrow/bitutil/bitmaps.go b/arrow/bitutil/bitmaps.go
index e0e332ad..db1c0abc 100644
--- a/arrow/bitutil/bitmaps.go
+++ b/arrow/bitutil/bitmaps.go
@@ -139,8 +139,8 @@ func (b *BitmapWriter) Next() {
}
}
-// AppendBools writes a series of booleans to the bitmapwriter and returns
-// the number of remaining bytes left in the buffer for writing.
+// AppendBools writes up to the remaining number of bits from in and returns
+// the number of boolean values written.
func (b *BitmapWriter) AppendBools(in []bool) int {
space := min(b.length-b.pos, len(in))
if space == 0 {
@@ -148,26 +148,88 @@ func (b *BitmapWriter) AppendBools(in []bool) int {
}
bitOffset := bits.TrailingZeros32(uint32(b.bitMask))
- // location that the first byte needs to be written to for appending
- appslice := b.buf[int(b.byteOffset) :
b.byteOffset+int(BytesForBits(int64(bitOffset+space)))]
- // update everything but curByte
- appslice[0] = b.curByte
- for i, b := range in[:space] {
- if b {
- SetBit(appslice, i+bitOffset)
- } else {
- ClearBit(appslice, i+bitOffset)
+ byteOffset := b.byteOffset
+ values := in[:space]
+
+ // Finish the first partial byte without changing unrelated bits.
+ if bitOffset != 0 {
+ n := min(len(values), 8-bitOffset)
+ current := b.curByte
+ for i, v := range values[:n] {
+ mask := byte(1) << uint(bitOffset+i)
+ if v {
+ current |= mask
+ } else {
+ current &^= mask
+ }
+ }
+ b.buf[byteOffset] = current
+ values = values[n:]
+ if n == 8-bitOffset {
+ byteOffset++
}
}
+ // Write eight booleans per byte instead of updating each bit
individually.
+ for len(values) >= 8 {
+ b.buf[byteOffset] = packBoolByte(values)
+ byteOffset++
+ values = values[8:]
+ }
+
+ if len(values) != 0 {
+ current := b.buf[byteOffset]
+ for i, v := range values {
+ mask := byte(1) << uint(i)
+ if v {
+ current |= mask
+ } else {
+ current &^= mask
+ }
+ }
+ b.buf[byteOffset] = current
+ }
+
b.pos += space
b.bitMask = BitMask[(bitOffset+space)%8]
b.byteOffset += (bitOffset + space) / 8
- b.curByte = appslice[len(appslice)-1]
-
+ // At a byte boundary, the next write must start with the next byte's
+ // existing bits, not the last byte written by this call.
+ if b.byteOffset < len(b.buf) {
+ b.curByte = b.buf[b.byteOffset]
+ }
return space
}
+func packBoolByte(values []bool) byte {
+ var packed byte
+ if values[0] {
+ packed |= 1 << 0
+ }
+ if values[1] {
+ packed |= 1 << 1
+ }
+ if values[2] {
+ packed |= 1 << 2
+ }
+ if values[3] {
+ packed |= 1 << 3
+ }
+ if values[4] {
+ packed |= 1 << 4
+ }
+ if values[5] {
+ packed |= 1 << 5
+ }
+ if values[6] {
+ packed |= 1 << 6
+ }
+ if values[7] {
+ packed |= 1 << 7
+ }
+ return packed
+}
+
// AppendBitmap writes bits directly from a source bitmap to this bitmap
writer,
// avoiding the intermediate []bool conversion. Returns the number of bits
written.
func (b *BitmapWriter) AppendBitmap(srcBitmap []byte, srcOffset int64, length
int64) int64 {
diff --git a/arrow/bitutil/bitmaps_append_bools_test.go
b/arrow/bitutil/bitmaps_append_bools_test.go
new file mode 100644
index 00000000..9397de4a
--- /dev/null
+++ b/arrow/bitutil/bitmaps_append_bools_test.go
@@ -0,0 +1,151 @@
+// 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 (
+ "bytes"
+ "fmt"
+ "math/rand"
+ "testing"
+
+ "github.com/apache/arrow-go/v18/arrow/bitutil"
+)
+
+func TestBitmapWriterAppendBoolsChunking(t *testing.T) {
+ rng := rand.New(rand.NewSource(42))
+ for offset := 0; offset < 16; offset++ {
+ for length := 0; length <= 129; length++ {
+ original := make([]byte,
int(bitutil.BytesForBits(int64(offset+length)))+8)
+ _, _ = rng.Read(original)
+ values := make([]bool, length+7)
+ for i := range values {
+ values[i] = rng.Intn(2) == 0
+ }
+
+ want := append([]byte(nil), original...)
+ for i, v := range values[:length] {
+ bitutil.SetBitTo(want, offset+i, v)
+ }
+
+ for _, chunkSize := range []int{1, 2, 7, 8, 9, 31, 256}
{
+ got := append([]byte(nil), original...)
+ writer := bitutil.NewBitmapWriter(got, offset,
length)
+ pos := 0
+ if chunkSize == 256 {
+ // Request extra values to cover the
writer's capacity limit.
+ pos = writer.AppendBools(values)
+ } else {
+ for pos < length {
+ end := min(pos+chunkSize,
length)
+ written :=
writer.AppendBools(values[pos:end])
+ if written != end-pos {
+ t.Fatalf("offset=%d
length=%d chunk=%d: wrote %d", offset, length, chunkSize, written)
+ }
+ pos += written
+ }
+ }
+ if pos != length ||
writer.AppendBools(values[length:]) != 0 {
+ t.Fatalf("offset=%d length=%d chunk=%d:
wrong capacity", offset, length, chunkSize)
+ }
+ writer.Finish()
+ if !bytes.Equal(got, want) {
+ t.Fatalf("offset=%d length=%d chunk=%d:
got %x, want %x", offset, length, chunkSize, got, want)
+ }
+ }
+ }
+ }
+}
+
+func TestBitmapWriterAppendBoolsWithOtherWrites(t *testing.T) {
+ const length = 64
+ values := make([]bool, length)
+ for i := range values {
+ values[i] = i%3 == 0
+ }
+ src := []byte{0x92, 0xb6, 0x03, 0x77}
+ for offset := 0; offset < 10; offset++ {
+ got := bytes.Repeat([]byte{0xa5}, 24)
+ want := append([]byte(nil), got...)
+ writer := bitutil.NewBitmapWriter(got, offset, length)
+ for i := 0; i < 11; i++ {
+ if values[i] {
+ writer.Set()
+ } else {
+ writer.Clear()
+ }
+ writer.Next()
+ }
+ if n := writer.AppendBools(values[11:28]); n != 17 {
+ t.Fatalf("expected 17 booleans, got %d", n)
+ }
+ if n := writer.AppendBitmap(src, 5, 19); n != 19 {
+ t.Fatalf("expected 19 bitmap bits, got %d", n)
+ }
+ for i := 47; i < length; i++ {
+ if values[i] {
+ writer.Set()
+ } else {
+ writer.Clear()
+ }
+ writer.Next()
+ }
+ writer.Finish()
+
+ for i := 0; i < length; i++ {
+ value := values[i]
+ if i >= 28 && i < 47 {
+ value = bitutil.BitIsSet(src, 5+i-28)
+ }
+ bitutil.SetBitTo(want, offset+i, value)
+ }
+ if !bytes.Equal(got, want) {
+ t.Fatalf("offset=%d: got %x, want %x", offset, got,
want)
+ }
+ }
+}
+
+func BenchmarkBitmapWriterAppendBools(b *testing.B) {
+ for _, size := range []int{64, 1024, 8192, 65536} {
+ values := make([]bool, size)
+ for i := range values {
+ values[i] = (i*37)%11 < 5
+ }
+ for _, offset := range []int{0, 3} {
+ for _, split := range []bool{false, true} {
+ b.Run(fmt.Sprintf("size=%d/offset=%d/split=%t",
size, offset, split), func(b *testing.B) {
+ out := make([]byte,
int(bitutil.BytesForBits(int64(offset+size)))+8)
+ writer := bitutil.NewBitmapWriter(out,
offset, size)
+ b.SetBytes(int64(size))
+ b.ReportAllocs()
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ writer.Reset(offset, size)
+ if split {
+ oneThird := size / 3
+
writer.AppendBools(values[:oneThird])
+
writer.AppendBools(values[oneThird : oneThird*2])
+
writer.AppendBools(values[oneThird*2:])
+ } else {
+
writer.AppendBools(values)
+ }
+ writer.Finish()
+ }
+ })
+ }
+ }
+ }
+}
