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 17ae3305 perf(arrow/array): pack validity values in batches (#1185)
17ae3305 is described below
commit 17ae3305e5f868e3354c0ec8d597a072e79f4bd4
Author: Minh Vu <[email protected]>
AuthorDate: Fri Aug 14 18:06:45 2026 +0200
perf(arrow/array): pack validity values in batches (#1185)
### Rationale for this change
Appending an explicit `[]bool` validity slice currently updates the
bitmap and null count one value at a time. This is a noticeable part of
`AppendValues` for narrow types.
### What changes are included in this PR?
- handle the unaligned prefix and trailing values individually
- pack aligned validity values eight at a time
- count nulls once per packed byte
- add coverage for all starting bit offsets, different lengths, and
stale neighboring bits
- add helper and builder benchmarks
Benchmarks append 65,536 values on an Apple M1 Pro. Values are medians
from three runs.
| Benchmark | Before | After | Change |
| --- | ---: | ---: | ---: |
| Int8 / all valid | 68.9 us | 19.6 us | 3.51x |
| Int8 / 50% null | 89.9 us | 20.4 us | 4.41x |
| Int64 / all valid | 87.9 us | 31.7 us | 2.77x |
| Int64 / 50% null | 103.0 us | 33.6 us | 3.06x |
| Boolean / all valid | 212.0 us | 162.0 us | 1.31x |
| Boolean / 50% null | 225.0 us | 163.3 us | 1.38x |
| String / all valid | 538.1 us | 471.4 us | 1.14x |
| String / 50% null | 553.9 us | 476.0 us | 1.16x |
No allocations are added.
### Are these changes tested?
Yes.
- `go test ./arrow/...`
- `go test -race ./arrow/array`
- `go vet ./arrow/array`
### Are there any user-facing changes?
No. This only changes how builder validity bitmaps are populated.
---
arrow/array/builder.go | 83 +++++++++++----
arrow/array/builder_test.go | 57 ++++++++++
arrow/array/builder_validity_benchmark_test.go | 138 +++++++++++++++++++++++++
3 files changed, 260 insertions(+), 18 deletions(-)
diff --git a/arrow/array/builder.go b/arrow/array/builder.go
index 2e0500af..cdcd35cd 100644
--- a/arrow/array/builder.go
+++ b/arrow/array/builder.go
@@ -18,6 +18,7 @@ package array
import (
"fmt"
+ "math/bits"
"sync/atomic"
"github.com/apache/arrow-go/v18/arrow"
@@ -196,32 +197,78 @@ func (b *builder) unsafeAppendBoolsToBitmap(valid []bool,
length int) {
return
}
+ validLength := len(valid)
byteOffset := b.length / 8
- bitOffset := byte(b.length % 8)
nullBitmap := b.nullBitmap.Bytes()
- bitSet := nullBitmap[byteOffset]
-
- for _, v := range valid {
- if bitOffset == 8 {
- bitOffset = 0
- nullBitmap[byteOffset] = bitSet
- byteOffset++
- bitSet = nullBitmap[byteOffset]
- }
+ bitOffset := b.length % 8
- if v {
- bitSet |= bitutil.BitMask[bitOffset]
- } else {
- bitSet &= bitutil.FlippedBitMask[bitOffset]
- b.nulls++
+ if bitOffset != 0 {
+ bitSet := nullBitmap[byteOffset]
+ prefixLength := min(8-bitOffset, len(valid))
+ for i, v := range valid[:prefixLength] {
+ if v {
+ bitSet |= bitutil.BitMask[bitOffset+i]
+ } else {
+ bitSet &= bitutil.FlippedBitMask[bitOffset+i]
+ b.nulls++
+ }
}
- bitOffset++
+ nullBitmap[byteOffset] = bitSet
+ valid = valid[prefixLength:]
+ byteOffset++
}
- if bitOffset != 0 {
+ for len(valid) >= 8 {
+ bitSet := packValidityByte(valid)
nullBitmap[byteOffset] = bitSet
+ b.nulls += 8 - bits.OnesCount8(bitSet)
+ valid = valid[8:]
+ byteOffset++
+ }
+
+ if len(valid) != 0 {
+ bitSet := nullBitmap[byteOffset]
+ for i, v := range valid {
+ if v {
+ bitSet |= bitutil.BitMask[i]
+ } else {
+ bitSet &= bitutil.FlippedBitMask[i]
+ b.nulls++
+ }
+ }
+ nullBitmap[byteOffset] = bitSet
+ }
+ b.length += validLength
+}
+
+func packValidityByte(valid []bool) byte {
+ valid = valid[:8]
+ var packed byte
+ if valid[0] {
+ packed |= 1 << 0
+ }
+ if valid[1] {
+ packed |= 1 << 1
+ }
+ if valid[2] {
+ packed |= 1 << 2
+ }
+ if valid[3] {
+ packed |= 1 << 3
+ }
+ if valid[4] {
+ packed |= 1 << 4
+ }
+ if valid[5] {
+ packed |= 1 << 5
+ }
+ if valid[6] {
+ packed |= 1 << 6
+ }
+ if valid[7] {
+ packed |= 1 << 7
}
- b.length += len(valid)
+ return packed
}
// unsafeSetValid sets the next length bits to valid in the validity bitmap.
diff --git a/arrow/array/builder_test.go b/arrow/array/builder_test.go
index 045317dc..166a6a4c 100644
--- a/arrow/array/builder_test.go
+++ b/arrow/array/builder_test.go
@@ -19,6 +19,7 @@ package array
import (
"testing"
+ "github.com/apache/arrow-go/v18/arrow/bitutil"
"github.com/apache/arrow-go/v18/arrow/internal/testing/tools"
"github.com/apache/arrow-go/v18/arrow/memory"
"github.com/stretchr/testify/assert"
@@ -56,6 +57,62 @@ func TestBuilder_UnsafeSetValid(t *testing.T) {
assert.Equal(t, []byte{0xe0, 0xff, 0x3f, 0}, ab.nullBitmap.Bytes())
}
+func TestBuilder_UnsafeAppendBoolsToBitmap(t *testing.T) {
+ patterns := []struct {
+ name string
+ valid func(int) bool
+ }{
+ {"all valid", func(int) bool { return true }},
+ {"all null", func(int) bool { return false }},
+ {"alternating", func(i int) bool { return i%2 == 0 }},
+ {"one in three null", func(i int) bool { return i%3 != 0 }},
+ }
+
+ for _, pattern := range patterns {
+ for offset := 0; offset < 8; offset++ {
+ for length := 1; length <= 33; length++ {
+ b := &builder{mem: memory.NewGoAllocator()}
+ b.init(48)
+ for i := range b.nullBitmap.Bytes() {
+ b.nullBitmap.Bytes()[i] = byte(0x5a +
i*31)
+ }
+
+ expectedBitmap := append([]byte(nil),
b.nullBitmap.Bytes()...)
+ valid := make([]bool, length)
+ expectedNulls := offset -
bitutil.CountSetBits(expectedBitmap, 0, offset)
+ for i := range valid {
+ valid[i] = pattern.valid(i)
+ if valid[i] {
+ bitutil.SetBit(expectedBitmap,
offset+i)
+ } else {
+
bitutil.ClearBit(expectedBitmap, offset+i)
+ expectedNulls++
+ }
+ }
+
+ b.length = offset
+ b.nulls = offset -
bitutil.CountSetBits(b.nullBitmap.Bytes(), 0, offset)
+ b.unsafeAppendBoolsToBitmap(valid, len(valid))
+
+ assert.Equal(t, offset+length, b.Len(), "%s,
offset=%d, length=%d", pattern.name, offset, length)
+ assert.Equal(t, expectedNulls, b.NullN(), "%s,
offset=%d, length=%d", pattern.name, offset, length)
+ assert.Equal(t, expectedBitmap,
b.nullBitmap.Bytes(), "%s, offset=%d, length=%d", pattern.name, offset, length)
+ b.nullBitmap.Release()
+ }
+ }
+ }
+}
+
+func TestPackValidityByte(t *testing.T) {
+ for want := 0; want < 1<<8; want++ {
+ valid := make([]bool, 8)
+ for i := range valid {
+ valid[i] = want&(1<<i) != 0
+ }
+ assert.Equal(t, byte(want), packValidityByte(valid),
"want=%08b", want)
+ }
+}
+
func TestBuilder_resize(t *testing.T) {
b := &builder{mem: memory.NewGoAllocator()}
n := 64
diff --git a/arrow/array/builder_validity_benchmark_test.go
b/arrow/array/builder_validity_benchmark_test.go
new file mode 100644
index 00000000..bb1a9403
--- /dev/null
+++ b/arrow/array/builder_validity_benchmark_test.go
@@ -0,0 +1,138 @@
+// 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 array
+
+import (
+ "fmt"
+ "testing"
+
+ "github.com/apache/arrow-go/v18/arrow/memory"
+)
+
+func BenchmarkAppendBoolsToBitmap(b *testing.B) {
+ const length = 65536
+ patterns := []struct {
+ name string
+ valid []bool
+ }{
+ {"all-valid", makeValidityBenchmarkValues(length, func(int)
bool { return true })},
+ {"1pct-null", makeValidityBenchmarkValues(length, func(i int)
bool { return i%100 != 0 })},
+ {"10pct-null", makeValidityBenchmarkValues(length, func(i int)
bool { return i%10 != 0 })},
+ {"50pct-null", makeValidityBenchmarkValues(length, func(i int)
bool { return i%2 == 0 })},
+ {"runs", makeValidityBenchmarkValues(length, func(i int) bool {
return i%128 < 64 })},
+ }
+
+ for _, pattern := range patterns {
+ for offset := 0; offset < 8; offset++ {
+ b.Run(fmt.Sprintf("%s/offset=%d", pattern.name,
offset), func(b *testing.B) {
+ var bldr builder
+ bldr.mem = memory.DefaultAllocator
+ bldr.init(length + offset)
+ defer bldr.nullBitmap.Release()
+ bldr.length = offset
+
+ b.ReportAllocs()
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ bldr.length = offset
+ bldr.nulls = 0
+
bldr.unsafeAppendBoolsToBitmap(pattern.valid, len(pattern.valid))
+ }
+ })
+ }
+ }
+}
+
+func BenchmarkAppendValuesWithValidity(b *testing.B) {
+ const length = 65536
+ patterns := []struct {
+ name string
+ valid []bool
+ }{
+ {"all-valid", makeValidityBenchmarkValues(length, func(int)
bool { return true })},
+ {"10pct-null", makeValidityBenchmarkValues(length, func(i int)
bool { return i%10 != 0 })},
+ {"50pct-null", makeValidityBenchmarkValues(length, func(i int)
bool { return i%2 == 0 })},
+ }
+ int8Values := make([]int8, length)
+ int64Values := make([]int64, length)
+ boolValues := makeValidityBenchmarkValues(length, func(i int) bool {
return i%2 == 0 })
+ stringValues := make([]string, length)
+ for i := range stringValues {
+ stringValues[i] = "x"
+ }
+
+ for _, pattern := range patterns {
+ b.Run("int8/"+pattern.name, func(b *testing.B) {
+ benchmarkAppendValues(b, func() (func(), func()) {
+ bldr := NewInt8Builder(memory.DefaultAllocator)
+ bldr.Reserve(length)
+ return func() {
+ bldr.AppendValues(int8Values,
pattern.valid)
+ }, bldr.Release
+ })
+ })
+ b.Run("int64/"+pattern.name, func(b *testing.B) {
+ benchmarkAppendValues(b, func() (func(), func()) {
+ bldr := NewInt64Builder(memory.DefaultAllocator)
+ bldr.Reserve(length)
+ return func() {
+ bldr.AppendValues(int64Values,
pattern.valid)
+ }, bldr.Release
+ })
+ })
+ b.Run("boolean/"+pattern.name, func(b *testing.B) {
+ benchmarkAppendValues(b, func() (func(), func()) {
+ bldr :=
NewBooleanBuilder(memory.DefaultAllocator)
+ bldr.Reserve(length)
+ return func() {
+ bldr.AppendValues(boolValues,
pattern.valid)
+ }, bldr.Release
+ })
+ })
+ b.Run("string/"+pattern.name, func(b *testing.B) {
+ benchmarkAppendValues(b, func() (func(), func()) {
+ bldr :=
NewStringBuilder(memory.DefaultAllocator)
+ bldr.Reserve(length)
+ bldr.ReserveData(length)
+ return func() {
+ bldr.AppendValues(stringValues,
pattern.valid)
+ }, bldr.Release
+ })
+ })
+ }
+}
+
+func benchmarkAppendValues(b *testing.B, setup func() (appendValues, release
func())) {
+ b.ReportAllocs()
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ b.StopTimer()
+ appendValues, release := setup()
+ b.StartTimer()
+ appendValues()
+ b.StopTimer()
+ release()
+ }
+}
+
+func makeValidityBenchmarkValues(length int, valid func(int) bool) []bool {
+ values := make([]bool, length)
+ for i := range values {
+ values[i] = valid(i)
+ }
+ return values
+}
