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 f5033852 perf(arrow/array): bulk append list nulls and empty values
(#1187)
f5033852 is described below
commit f5033852c3cdb7077aef7b103a0591b4adf99b3c
Author: Minh Vu <[email protected]>
AuthorDate: Tue Aug 18 22:01:14 2026 +0200
perf(arrow/array): bulk append list nulls and empty values (#1187)
## What
- reserve List and ListView batches once
- update parent validity in bulk
- append repeated offsets and zero sizes through the unsafe builder path
- cover List, LargeList, ListView, and LargeListView
These bulk APIs currently call the scalar append path once per list
slot. Empty and null variable-sized lists do not append child values, so
only the parent validity and dimensions need updating.
This follows the batching shape used by the C++ list builders:
https://github.com/apache/arrow/blob/485499fd02ea2b0c323d67871fbe96aae4232504/cpp/src/arrow/array/builder_nested.h#L138-L160
For ListView, this keeps Go's current physical representation by
repeating the current child offset with a zero size.
## Benchmark
Apple M1 Pro, Go 1.26.3. Representative medians from three to five runs
with 65,536 slots:
| Builder | Operation | Before | After | Change |
|---|---|---:|---:|---:|
| List | nulls | 848 us | 201 us | -76% |
| List | empty | 848 us | 197 us | -77% |
| LargeList | nulls | 1.08 ms | 241 us | -78% |
| LargeList | empty | 1.05 ms | 245 us | -77% |
| ListView | nulls | 1.35 ms | 414 us | -69% |
| ListView | empty | 1.24 ms | 415 us | -67% |
| LargeListView | nulls | 1.47 ms | 509 us | -65% |
| LargeListView | empty | 1.50 ms | 505 us | -66% |
Regular-list allocations drop from 45 to 18 per batch. List-view
allocations drop from 68 to 25. The `n=1` cases stay within benchmark
noise.
## Tests
- `go test ./arrow/array -count=1`
- `go test -race ./arrow/array -run
'TestListBuilderBulkAppendNullsAndEmptyValues|TestList|TestLargeList'
-count=1`
- `go vet ./arrow/array`
- `go test -p 1 ./...`
---
arrow/array/list.go | 60 ++++++--
arrow/array/list_builder_bulk_test.go | 251 ++++++++++++++++++++++++++++++++++
arrow/array/map.go | 14 +-
arrow/array/map_test.go | 86 ++++++++++++
4 files changed, 399 insertions(+), 12 deletions(-)
diff --git a/arrow/array/list.go b/arrow/array/list.go
index 4ccea68e..463da03b 100644
--- a/arrow/array/list.go
+++ b/arrow/array/list.go
@@ -419,6 +419,25 @@ func (b *baseListBuilder) appendNextOffset() {
b.appendOffsetVal(b.values.Len())
}
+func unsafeAppendRepeatedInt(builder Builder, value, n int) {
+ switch builder := builder.(type) {
+ case *Int32Builder:
+ end := builder.length + n
+ for i := builder.length; i < end; i++ {
+ builder.rawData[i] = int32(value)
+ }
+ builder.unsafeAppendBoolsToBitmap(nil, n)
+ case *Int64Builder:
+ end := builder.length + n
+ for i := builder.length; i < end; i++ {
+ builder.rawData[i] = int64(value)
+ }
+ builder.unsafeAppendBoolsToBitmap(nil, n)
+ default:
+ panic(fmt.Sprintf("arrow/array: unsupported list dimension
builder %T", builder))
+ }
+}
+
func (b *baseListBuilder) Append(v bool) {
b.Reserve(1)
b.unsafeAppendBoolToBitmap(v)
@@ -436,9 +455,15 @@ func (b *baseListBuilder) AppendNull() {
}
func (b *baseListBuilder) AppendNulls(n int) {
- for i := 0; i < n; i++ {
- b.AppendNull()
+ if n <= 0 {
+ return
}
+
+ b.Reserve(n)
+ bitutil.SetBitsTo(b.nullBitmap.Bytes(), int64(b.length), int64(n),
false)
+ b.length += n
+ b.nulls += n
+ unsafeAppendRepeatedInt(b.offsets, b.values.Len(), n)
}
func (b *baseListBuilder) AppendEmptyValue() {
@@ -446,9 +471,13 @@ func (b *baseListBuilder) AppendEmptyValue() {
}
func (b *baseListBuilder) AppendEmptyValues(n int) {
- for i := 0; i < n; i++ {
- b.AppendEmptyValue()
+ if n <= 0 {
+ return
}
+
+ b.Reserve(n)
+ b.unsafeAppendBoolsToBitmap(nil, n)
+ unsafeAppendRepeatedInt(b.offsets, b.values.Len(), n)
}
func (b *ListBuilder) AppendValues(offsets []int32, valid []bool) {
@@ -1221,9 +1250,15 @@ func (b *baseListViewBuilder) AppendNull() {
}
func (b *baseListViewBuilder) AppendNulls(n int) {
- for i := 0; i < n; i++ {
- b.AppendNull()
+ if n <= 0 {
+ return
}
+
+ b.Reserve(n)
+ bitutil.SetBitsTo(b.nullBitmap.Bytes(), int64(b.length), int64(n),
false)
+ b.length += n
+ b.nulls += n
+ b.unsafeAppendEmptyDimensions(n)
}
func (b *baseListViewBuilder) AppendEmptyValue() {
@@ -1231,9 +1266,18 @@ func (b *baseListViewBuilder) AppendEmptyValue() {
}
func (b *baseListViewBuilder) AppendEmptyValues(n int) {
- for i := 0; i < n; i++ {
- b.AppendEmptyValue()
+ if n <= 0 {
+ return
}
+
+ b.Reserve(n)
+ b.unsafeAppendBoolsToBitmap(nil, n)
+ b.unsafeAppendEmptyDimensions(n)
+}
+
+func (b *baseListViewBuilder) unsafeAppendEmptyDimensions(n int) {
+ unsafeAppendRepeatedInt(b.offsets, b.values.Len(), n)
+ unsafeAppendRepeatedInt(b.sizes, 0, n)
}
func (b *ListViewBuilder) AppendValuesWithSizes(offsets []int32, sizes
[]int32, valid []bool) {
diff --git a/arrow/array/list_builder_bulk_test.go
b/arrow/array/list_builder_bulk_test.go
new file mode 100644
index 00000000..bb32b9ec
--- /dev/null
+++ b/arrow/array/list_builder_bulk_test.go
@@ -0,0 +1,251 @@
+// 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_test
+
+import (
+ "fmt"
+ "testing"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/array"
+ "github.com/apache/arrow-go/v18/arrow/memory"
+ "github.com/stretchr/testify/assert"
+ "github.com/stretchr/testify/require"
+)
+
+type listBuilderFactory func(memory.Allocator) array.VarLenListLikeBuilder
+
+var listBuilderFactories = []struct {
+ name string
+ view bool
+ new listBuilderFactory
+}{
+ {"list", false, func(mem memory.Allocator) array.VarLenListLikeBuilder {
+ return array.NewListBuilder(mem, arrow.PrimitiveTypes.Int32)
+ }},
+ {"large_list", false, func(mem memory.Allocator)
array.VarLenListLikeBuilder {
+ return array.NewLargeListBuilder(mem,
arrow.PrimitiveTypes.Int32)
+ }},
+ {"list_view", true, func(mem memory.Allocator)
array.VarLenListLikeBuilder {
+ return array.NewListViewBuilder(mem, arrow.PrimitiveTypes.Int32)
+ }},
+ {"large_list_view", true, func(mem memory.Allocator)
array.VarLenListLikeBuilder {
+ return array.NewLargeListViewBuilder(mem,
arrow.PrimitiveTypes.Int32)
+ }},
+}
+
+func TestListBuilderBulkAppendNullsAndEmptyValues(t *testing.T) {
+ for _, tc := range listBuilderFactories {
+ t.Run(tc.name, func(t *testing.T) {
+ mem :=
memory.NewCheckedAllocator(memory.NewGoAllocator())
+ defer mem.AssertSize(t, 0)
+
+ builder := tc.new(mem)
+ defer builder.Release()
+ values := builder.ValueBuilder().(*array.Int32Builder)
+
+ builder.AppendNulls(0)
+ builder.AppendEmptyValues(0)
+ builder.AppendNulls(-1)
+ builder.AppendEmptyValues(-1)
+ require.Zero(t, builder.Len())
+ require.Zero(t, builder.Cap())
+ require.Zero(t, builder.NullN())
+
+ builder.AppendWithSize(true, 2)
+ values.AppendValues([]int32{10, 20}, nil)
+ builder.AppendEmptyValues(4)
+ builder.AppendNulls(5)
+ builder.AppendWithSize(true, 1)
+ values.Append(30)
+
+ arr := builder.NewArray().(array.VarLenListLike)
+ defer arr.Release()
+ require.NoError(t, arr.(interface{ ValidateFull() error
}).ValidateFull())
+
+ assert.Equal(t, 11, arr.Len())
+ assert.Equal(t, 5, arr.NullN())
+ for i := range arr.Len() {
+ assert.Equal(t, i < 5 || i == 10,
arr.IsValid(i), "list value %d", i)
+ start, end := arr.ValueOffsets(i)
+ switch i {
+ case 0:
+ assert.Equal(t, int64(0), start)
+ assert.Equal(t, int64(2), end)
+ case 10:
+ assert.Equal(t, int64(2), start)
+ assert.Equal(t, int64(3), end)
+ default:
+ if tc.view {
+ assert.Equal(t, int64(0), start)
+ assert.Equal(t, int64(0), end)
+ } else {
+ assert.Equal(t, int64(2), start)
+ assert.Equal(t, int64(2), end)
+ }
+ }
+ }
+ switch arr := arr.(type) {
+ case *array.ListView:
+ assert.Equal(t, []int32{0, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2}, arr.Offsets())
+ case *array.LargeListView:
+ assert.Equal(t, []int64{0, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2}, arr.Offsets())
+ }
+
+ child := arr.ListValues().(*array.Int32)
+ require.Equal(t, 3, child.Len())
+ assert.Equal(t, []int32{10, 20, 30},
child.Int32Values())
+ })
+ }
+}
+
+func TestListBuilderBulkAppendMatchesScalar(t *testing.T) {
+ starts := []int{0, 1, 7, 8, 9, 15, 16, 17}
+ batchSizes := []int{-1, 0, 1, 2, 7, 8, 9, 16, 17}
+ operations := []struct {
+ name string
+ bulk func(array.VarLenListLikeBuilder, int)
+ scalar func(array.VarLenListLikeBuilder, int)
+ }{
+ {
+ name: "nulls",
+ bulk: func(builder array.VarLenListLikeBuilder, n int) {
+ builder.AppendNulls(n)
+ },
+ scalar: func(builder array.VarLenListLikeBuilder, n
int) {
+ for i := 0; i < n; i++ {
+ builder.AppendNull()
+ }
+ },
+ },
+ {
+ name: "empty_values",
+ bulk: func(builder array.VarLenListLikeBuilder, n int) {
+ builder.AppendEmptyValues(n)
+ },
+ scalar: func(builder array.VarLenListLikeBuilder, n
int) {
+ for i := 0; i < n; i++ {
+ builder.AppendEmptyValue()
+ }
+ },
+ },
+ }
+
+ for _, factory := range listBuilderFactories {
+ t.Run(factory.name, func(t *testing.T) {
+ for operationIndex, operation := range operations {
+ t.Run(operation.name, func(t *testing.T) {
+ reuseOperation :=
operations[1-operationIndex]
+ for _, start := range starts {
+ for _, batchSize := range
batchSizes {
+
t.Run(fmt.Sprintf("start_%d_batch_%d", start, batchSize), func(t *testing.T) {
+ mem :=
memory.NewCheckedAllocator(memory.NewGoAllocator())
+ defer
mem.AssertSize(t, 0)
+
+ bulk :=
factory.new(mem)
+ defer
bulk.Release()
+ scalar :=
factory.new(mem)
+ defer
scalar.Release()
+
+
appendListBuilderPrefix(bulk, start)
+
appendListBuilderPrefix(scalar, start)
+
operation.bulk(bulk, batchSize)
+
operation.scalar(scalar, batchSize)
+
assertBuilderArrayParity(t, bulk, scalar)
+
+
appendListBuilderPrefix(bulk, start)
+
appendListBuilderPrefix(scalar, start)
+
reuseOperation.bulk(bulk, 9)
+
reuseOperation.scalar(scalar, 9)
+
assertBuilderArrayParity(t, bulk, scalar)
+ })
+ }
+ }
+ })
+ }
+ })
+ }
+}
+
+func appendListBuilderPrefix(builder array.VarLenListLikeBuilder, n int) {
+ values := builder.ValueBuilder().(*array.Int32Builder)
+ for i := 0; i < n; i++ {
+ switch i % 4 {
+ case 0:
+ builder.AppendWithSize(true, 2)
+ values.AppendValues([]int32{int32(i), int32(i + 100)},
nil)
+ case 1:
+ builder.AppendNull()
+ case 2:
+ builder.AppendEmptyValue()
+ case 3:
+ builder.AppendWithSize(true, 1)
+ values.Append(int32(i + 1000))
+ }
+ }
+}
+
+func assertBuilderArrayParity(t *testing.T, bulk, scalar array.Builder) {
+ t.Helper()
+
+ assert.Equal(t, scalar.Len(), bulk.Len())
+ assert.Equal(t, scalar.NullN(), bulk.NullN())
+
+ bulkArray := bulk.NewArray()
+ defer bulkArray.Release()
+ scalarArray := scalar.NewArray()
+ defer scalarArray.Release()
+
+ require.NoError(t, bulkArray.(interface{ ValidateFull() error
}).ValidateFull())
+ require.NoError(t, scalarArray.(interface{ ValidateFull() error
}).ValidateFull())
+ assert.True(t, array.Equal(bulkArray, scalarArray))
+}
+
+func BenchmarkListBuilderBulkAppend(b *testing.B) {
+ for _, tc := range listBuilderFactories {
+ b.Run(tc.name, func(b *testing.B) {
+ for _, rows := range []int{1, 16, 1024, 65536} {
+ b.Run(fmt.Sprintf("rows_%d", rows), func(b
*testing.B) {
+ b.Run("nulls", func(b *testing.B) {
+
benchmarkListBuilderBulkAppend(b, tc.new, rows, false)
+ })
+ b.Run("empty", func(b *testing.B) {
+
benchmarkListBuilderBulkAppend(b, tc.new, rows, true)
+ })
+ })
+ }
+ })
+ }
+}
+
+func benchmarkListBuilderBulkAppend(b *testing.B, factory listBuilderFactory,
rows int, empty bool) {
+ builder := factory(memory.DefaultAllocator)
+ defer builder.Release()
+ b.ReportAllocs()
+
+ for b.Loop() {
+ if empty {
+ builder.AppendEmptyValues(rows)
+ } else {
+ builder.AppendNulls(rows)
+ }
+
+ arr := builder.NewArray()
+ arr.Release()
+ }
+}
diff --git a/arrow/array/map.go b/arrow/array/map.go
index 1a7d9e19..d8ad4730 100644
--- a/arrow/array/map.go
+++ b/arrow/array/map.go
@@ -233,9 +233,12 @@ func (b *MapBuilder) AppendNull() {
// AppendNulls adds null map entry to the array.
func (b *MapBuilder) AppendNulls(n int) {
- for i := 0; i < n; i++ {
- b.AppendNull()
+ if n <= 0 {
+ return
}
+
+ b.adjustStructBuilderLen()
+ b.listBuilder.AppendNulls(n)
}
func (b *MapBuilder) SetNull(i int) {
@@ -247,9 +250,12 @@ func (b *MapBuilder) AppendEmptyValue() {
}
func (b *MapBuilder) AppendEmptyValues(n int) {
- for i := 0; i < n; i++ {
- b.AppendEmptyValue()
+ if n <= 0 {
+ return
}
+
+ b.adjustStructBuilderLen()
+ b.listBuilder.AppendEmptyValues(n)
}
// Reserve enough space for n maps
diff --git a/arrow/array/map_test.go b/arrow/array/map_test.go
index e45ac133..3e9f1667 100644
--- a/arrow/array/map_test.go
+++ b/arrow/array/map_test.go
@@ -17,6 +17,7 @@
package array_test
import (
+ "fmt"
"strconv"
"testing"
@@ -327,3 +328,88 @@ func TestMapBuilder_SetNull(t *testing.T) {
assert.True(t, arr.IsValid(1))
assert.True(t, arr.IsNull(3))
}
+
+func TestMapBuilderBulkAppendMatchesScalar(t *testing.T) {
+ starts := []int{0, 1, 7, 8, 9, 15, 16, 17}
+ batchSizes := []int{-1, 0, 1, 2, 7, 8, 9, 16, 17}
+ operations := []struct {
+ name string
+ bulk func(*array.MapBuilder, int)
+ scalar func(*array.MapBuilder, int)
+ }{
+ {
+ name: "nulls",
+ bulk: func(builder *array.MapBuilder, n int) {
+ builder.AppendNulls(n)
+ },
+ scalar: func(builder *array.MapBuilder, n int) {
+ for i := 0; i < n; i++ {
+ builder.AppendNull()
+ }
+ },
+ },
+ {
+ name: "empty_values",
+ bulk: func(builder *array.MapBuilder, n int) {
+ builder.AppendEmptyValues(n)
+ },
+ scalar: func(builder *array.MapBuilder, n int) {
+ for i := 0; i < n; i++ {
+ builder.AppendEmptyValue()
+ }
+ },
+ },
+ }
+
+ for operationIndex, operation := range operations {
+ t.Run(operation.name, func(t *testing.T) {
+ reuseOperation := operations[1-operationIndex]
+ for _, start := range starts {
+ for _, batchSize := range batchSizes {
+ t.Run(fmt.Sprintf("start_%d_batch_%d",
start, batchSize), func(t *testing.T) {
+ mem :=
memory.NewCheckedAllocator(memory.NewGoAllocator())
+ defer mem.AssertSize(t, 0)
+
+ bulk :=
array.NewMapBuilder(mem, arrow.PrimitiveTypes.Int32,
arrow.PrimitiveTypes.Int32, false)
+ defer bulk.Release()
+ scalar :=
array.NewMapBuilder(mem, arrow.PrimitiveTypes.Int32,
arrow.PrimitiveTypes.Int32, false)
+ defer scalar.Release()
+
+ appendMapBuilderPrefix(bulk,
start)
+ appendMapBuilderPrefix(scalar,
start)
+ operation.bulk(bulk, batchSize)
+ operation.scalar(scalar,
batchSize)
+ assertBuilderArrayParity(t,
bulk, scalar)
+
+ appendMapBuilderPrefix(bulk,
start)
+ appendMapBuilderPrefix(scalar,
start)
+ reuseOperation.bulk(bulk, 9)
+ reuseOperation.scalar(scalar, 9)
+ assertBuilderArrayParity(t,
bulk, scalar)
+ })
+ }
+ }
+ })
+ }
+}
+
+func appendMapBuilderPrefix(builder *array.MapBuilder, n int) {
+ keys := builder.KeyBuilder().(*array.Int32Builder)
+ items := builder.ItemBuilder().(*array.Int32Builder)
+ for i := 0; i < n; i++ {
+ switch i % 4 {
+ case 0:
+ builder.Append(true)
+ keys.Append(int32(i))
+ items.Append(int32(i + 100))
+ case 1:
+ builder.AppendNull()
+ case 2:
+ builder.AppendEmptyValue()
+ case 3:
+ builder.Append(true)
+ keys.Append(int32(i + 1000))
+ items.Append(int32(i + 1100))
+ }
+ }
+}
