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 fbb14d11 perf(arrow/array): concatenate bitmaps directly (#1224)
fbb14d11 is described below
commit fbb14d11080069733c5015a37db03d27afab1056
Author: Minh Vu <[email protected]>
AuthorDate: Mon Aug 31 20:14:32 2026 +0200
perf(arrow/array): concatenate bitmaps directly (#1224)
## What does this change?
- `concat` used to build a temporary `[]bitmap` for each bitmap it
concatenated.
- `concatBitmaps` now reads the input `ArrayData` directly by buffer
index.
- Keep the existing nil bitmap behavior for all-valid inputs and
preserve sliced bitmap offsets.
## Benchmark
Command:
```text
go test ./arrow/array -run '^$' -bench '^BenchmarkConcatenateBitmaps$'
-benchmem -benchtime=200ms -count=3
```
Apple M1 Pro, Go 1.26.3. The benchmark concatenates 65,536 rows split
across 64, 1,024, and 8,192 chunks.
| Input | Chunks | Before ns/op | After ns/op | Before B/op | After B/op
| Allocs before/after |
| --- | ---: | ---: | ---: | ---: | ---: | ---: |
| nullable Boolean | 64 | 6,965 | 5,689 | 25,824 | 20,448 | 10 / 8 |
| nullable Boolean | 1,024 | 55,375 | 41,568 | 119,648 | 37,728 | 10 / 8
|
| nullable Boolean | 8,192 | 412,768 | 276,285 | 805,730 | 150,368 | 10
/ 8 |
| nullable int32 | 8,192 | 313,516 | 269,165 | 738,913 | 411,233 | 9 / 8
|
## Tests
- `go test ./arrow/array -count=1`
- `go test ./arrow/... ./internal/...`
---
arrow/array/concat.go | 47 +++++-------
arrow/array/concat_bitmap_benchmark_test.go | 107 ++++++++++++++++++++++++++++
arrow/array/concat_bitmap_test.go | 68 ++++++++++++++++++
arrow/array/concat_test.go | 22 ++++++
4 files changed, 214 insertions(+), 30 deletions(-)
diff --git a/arrow/array/concat.go b/arrow/array/concat.go
index 9a35daae..592ca28a 100644
--- a/arrow/array/concat.go
+++ b/arrow/array/concat.go
@@ -67,26 +67,6 @@ type rng struct {
offset, len int
}
-// simple bitmap struct to reference a specific slice of a bitmap where the
range
-// offset and length are in bits
-type bitmap struct {
- data []byte
- rng rng
-}
-
-// gather up the bitmaps from the passed in data objects
-func gatherBitmaps(data []arrow.ArrayData, idx int) []bitmap {
- out := make([]bitmap, len(data))
- for i, d := range data {
- if d.Buffers()[idx] != nil {
- out[i].data = d.Buffers()[idx].Bytes()
- }
- out[i].rng.offset = d.Offset()
- out[i].rng.len = d.Len()
- }
- return out
-}
-
// gatherFixedBuffers gathers up the buffer objects of the given index,
specifically
// returning only the slices of the buffers which are relevant to the passed
in arrays
// in case they are themselves slices of other arrays. nil buffers are ignored
and not
@@ -674,7 +654,7 @@ func concat(data []arrow.ArrayData, mem memory.Allocator)
(arr arrow.ArrayData,
out.buffers = make([]*memory.Buffer, len(data[0].Buffers()))
if out.nulls != 0 && out.dtype.ID() != arrow.NULL {
- bm, err := concatBitmaps(gatherBitmaps(data, 0), mem)
+ bm, err := concatBitmaps(data, 0, mem)
if err != nil {
return nil, err
}
@@ -689,7 +669,7 @@ func concat(data []arrow.ArrayData, mem memory.Allocator)
(arr arrow.ArrayData,
switch dt := dt.(type) {
case *arrow.NullType:
case *arrow.BooleanType:
- bm, err := concatBitmaps(gatherBitmaps(data, 1), mem)
+ bm, err := concatBitmaps(data, 1, mem)
if err != nil {
return nil, err
}
@@ -917,31 +897,38 @@ func addOvf(x, y int) (int, bool) {
}
// concatenate bitmaps together and return a buffer with the combined bitmaps
-func concatBitmaps(bitmaps []bitmap, mem memory.Allocator) (*memory.Buffer,
error) {
+func concatBitmaps(data []arrow.ArrayData, idx int, mem memory.Allocator)
(*memory.Buffer, error) {
var (
outlen int
overflow bool
)
- for _, bm := range bitmaps {
- if outlen, overflow = addOvf(outlen, bm.rng.len); overflow {
+ for _, d := range data {
+ if outlen, overflow = addOvf(outlen, d.Len()); overflow {
return nil, errors.New("length overflow when
concatenating arrays")
}
}
out := memory.NewResizableBuffer(mem)
+ success := false
+ defer func() {
+ if !success {
+ out.Release()
+ }
+ }()
out.Resize(int(bitutil.BytesForBits(int64(outlen))))
dst := out.Bytes()
offset := 0
- for _, bm := range bitmaps {
- if bm.data == nil { // if the bitmap is nil, that implies that
the value is true for all elements
- bitutil.SetBitsTo(out.Bytes(), int64(offset),
int64(bm.rng.len), true)
+ for _, d := range data {
+ if buf := d.Buffers()[idx]; buf == nil { // if the bitmap is
nil, that implies that the value is true for all elements
+ bitutil.SetBitsTo(out.Bytes(), int64(offset),
int64(d.Len()), true)
} else {
- bitutil.CopyBitmap(bm.data, bm.rng.offset, bm.rng.len,
dst, offset)
+ bitutil.CopyBitmap(buf.Bytes(), d.Offset(), d.Len(),
dst, offset)
}
- offset += bm.rng.len
+ offset += d.Len()
}
+ success = true
return out, nil
}
diff --git a/arrow/array/concat_bitmap_benchmark_test.go
b/arrow/array/concat_bitmap_benchmark_test.go
new file mode 100644
index 00000000..54713be9
--- /dev/null
+++ b/arrow/array/concat_bitmap_benchmark_test.go
@@ -0,0 +1,107 @@
+// 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"
+)
+
+func BenchmarkConcatenateBitmaps(b *testing.B) {
+ const totalValues = 1 << 16
+
+ buildBoolean := func(mem memory.Allocator) arrow.Array {
+ values := make([]bool, totalValues)
+ valid := make([]bool, totalValues)
+ for i := range values {
+ values[i] = i%3 == 0
+ valid[i] = i%7 != 0
+ }
+
+ bldr := array.NewBooleanBuilder(mem)
+ bldr.AppendValues(values, valid)
+ result := bldr.NewBooleanArray()
+ bldr.Release()
+ return result
+ }
+
+ buildInt32 := func(mem memory.Allocator) arrow.Array {
+ values := make([]int32, totalValues)
+ valid := make([]bool, totalValues)
+ for i := range values {
+ values[i] = int32(i)
+ valid[i] = i%7 != 0
+ }
+
+ bldr := array.NewInt32Builder(mem)
+ bldr.AppendValues(values, valid)
+ result := bldr.NewInt32Array()
+ bldr.Release()
+ return result
+ }
+
+ inputs := []struct {
+ name string
+ build func(memory.Allocator) arrow.Array
+ }{
+ {"boolean-nullable", buildBoolean},
+ {"int32-nullable", buildInt32},
+ }
+
+ for _, input := range inputs {
+ input := input
+ b.Run(input.name, func(b *testing.B) {
+ mem := memory.NewGoAllocator()
+ backing := input.build(mem)
+ defer backing.Release()
+
+ for _, chunkCount := range []int{64, 1024, 8192} {
+ chunkCount := chunkCount
+ b.Run(fmt.Sprintf("chunks-%d", chunkCount),
func(b *testing.B) {
+ chunkSize := totalValues / chunkCount
+ chunks := make([]arrow.Array,
chunkCount)
+ for i := range chunks {
+ begin := int64(i * chunkSize)
+ chunks[i] =
array.NewSlice(backing, begin, begin+int64(chunkSize))
+ }
+ defer func() {
+ for _, chunk := range chunks {
+ chunk.Release()
+ }
+ }()
+
+ b.ReportAllocs()
+ b.ResetTimer()
+ for b.Loop() {
+ result, err :=
array.Concatenate(chunks, mem)
+ if err != nil {
+ b.Fatal(err)
+ }
+ if result.Len() != totalValues {
+ b.Fatalf("result length
= %d, want %d", result.Len(), totalValues)
+ }
+ result.Release()
+ }
+ })
+ }
+ })
+ }
+}
diff --git a/arrow/array/concat_bitmap_test.go
b/arrow/array/concat_bitmap_test.go
new file mode 100644
index 00000000..344cfe91
--- /dev/null
+++ b/arrow/array/concat_bitmap_test.go
@@ -0,0 +1,68 @@
+// 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 (
+ "strings"
+ "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"
+)
+
+func TestConcatenateBooleanBitmapSlices(t *testing.T) {
+ mem := memory.NewCheckedAllocator(memory.DefaultAllocator)
+ defer mem.AssertSize(t, 0)
+
+ values := memory.NewResizableBuffer(mem)
+ values.Resize(1)
+ values.Bytes()[0] = 0b00010101
+ allValid := array.NewBoolean(5, values, nil, 0)
+ defer allValid.Release()
+ values.Release()
+
+ bldr := array.NewBooleanBuilder(mem)
+ bldr.AppendValues(
+ []bool{true, false, true, false, true, false},
+ []bool{true, false, true, true, true, true},
+ )
+ nullable := bldr.NewBooleanArray()
+ bldr.Release()
+ defer nullable.Release()
+
+ input := []arrow.Array{
+ array.NewSlice(allValid, 0, 5),
+ array.NewSlice(nullable, 1, 5),
+ }
+ for _, arr := range input {
+ defer arr.Release()
+ }
+
+ actual, err := array.Concatenate(input, mem)
+ require.NoError(t, err)
+ defer actual.Release()
+
+ expected, _, err := array.FromJSON(mem, arrow.FixedWidthTypes.Boolean,
+ strings.NewReader("[true, false, true, false, true, null, true,
false, true]"))
+ require.NoError(t, err)
+ defer expected.Release()
+
+ assert.True(t, array.Equal(expected, actual))
+}
diff --git a/arrow/array/concat_test.go b/arrow/array/concat_test.go
index 135f9991..972024d8 100644
--- a/arrow/array/concat_test.go
+++ b/arrow/array/concat_test.go
@@ -1073,6 +1073,28 @@ func TestConcatPanic(t *testing.T) {
assert.Nil(t, concat)
}
+type missingBuffersArray struct {
+ arrow.Array
+ data arrow.ArrayData
+}
+
+func (a *missingBuffersArray) Data() arrow.ArrayData { return a.data }
+
+func TestConcatMissingBitmapBufferReleasesOutput(t *testing.T) {
+ mem := memory.NewCheckedAllocator(memory.DefaultAllocator)
+ defer mem.AssertSize(t, 0)
+
+ backing := array.NewBoolean(512, nil, nil, 1)
+ defer backing.Release()
+ data := array.NewData(arrow.FixedWidthTypes.Boolean, backing.Len(),
nil, nil, 1, 0)
+ defer data.Release()
+
+ input := &missingBuffersArray{Array: backing, data: data}
+ concat, err := array.Concatenate([]arrow.Array{input}, mem)
+ require.Error(t, err)
+ require.Nil(t, concat)
+}
+
// github.com/apache/arrow-go/issues/562
func TestREESliceAndConcatenate(t *testing.T) {
mem := memory.DefaultAllocator
