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 7e4c9c87 perf(arrow/array): reuse dictionary mappings and handle empty
chunks in Concatenate (#1403)
7e4c9c87 is described below
commit 7e4c9c871cd2c4fd83f4c89a37da302dbf6e5a09
Author: Minh Vu <[email protected]>
AuthorDate: Fri Oct 23 18:34:57 2026 +0200
perf(arrow/array): reuse dictionary mappings and handle empty chunks in
Concatenate (#1403)
## What
Reuse dictionary checks and index mappings in `array.Concatenate`.
## Why
Many chunks share dictionary data. Rechecking values and rebuilding
mappings for each chunk adds repeated work.
## Implementation
- Skip value comparison when chunks share the same dictionary data.
- Reuse transposition buffers for repeated dictionaries.
- Add correctness coverage and a public API benchmark.
## Benchmark
Public `array.Concatenate` call with 12 chunks and 8,192 dictionary
entries. Go 1.26.3, Apple M1 Pro (`darwin/arm64`), `GOMAXPROCS=1`; 10
runs of 200 ms per case. Base `de0c94e` vs head `651fe14`.
| Metric | Before | After | Change |
| --- | ---: | ---: | ---: |
| Shared dictionary, time | 82.374 µs/op | 3.723 µs/op | -95.48% |
| Repeated mixed dictionaries, time | 5.593 ms/op | 2.039 ms/op |
-63.54% |
| Shared dictionary, bytes | 15.42 KiB/op | 14.48 KiB/op | -6.08% |
| Repeated mixed dictionaries, bytes | 4.262 MiB/op | 2.784 MiB/op |
-34.69% |
| Shared dictionary, allocations | 23 allocs/op | 11 allocs/op | -52.17%
|
| Repeated mixed dictionaries, allocations | 99.04k allocs/op | 25.26k
allocs/op | -74.49% |
Both time cases improved. The benchmark excludes setup and releases each
output. Command: `GOMAXPROCS=1 go test ./arrow/array -run '^$' -bench
'^BenchmarkConcatenateDictionaryReuse$' -benchmem -benchtime=200ms
-count=10 -cpu=1`.
---
arrow/array/concat.go | 35 +++++-
arrow/array/concat_dictionary_reuse_test.go | 167 ++++++++++++++++++++++++++++
2 files changed, 197 insertions(+), 5 deletions(-)
diff --git a/arrow/array/concat.go b/arrow/array/concat.go
index 5fb9cb4b..2c04ec09 100644
--- a/arrow/array/concat.go
+++ b/arrow/array/concat.go
@@ -326,13 +326,29 @@ func unifyDictionaries(mem memory.Allocator, data
[]arrow.ArrayData, dt *arrow.D
defer unifier.Release()
newLookup := make([]*memory.Buffer, len(data))
+ // Reusing the same dictionary data must also reuse its transposition.
+ // A dictionary's indices in the unified result never change as new
+ // dictionaries are added to the unifier.
+ transpositions := make(map[arrow.ArrayData]*memory.Buffer)
for i, d := range data {
- dictArr := MakeFromData(d.Dictionary())
- defer dictArr.Release()
+ dictData := d.Dictionary()
+ if existing, ok := transpositions[dictData]; ok {
+ // concatDictIndices releases one buffer per input
chunk.
+ existing.Retain()
+ newLookup[i] = existing
+ continue
+ }
+
+ dictArr := MakeFromData(dictData)
newLookup[i], err = unifier.UnifyAndTranspose(dictArr)
+ dictArr.Release()
if err != nil {
+ for _, b := range newLookup[:i] {
+ b.Release()
+ }
return nil, nil, err
}
+ transpositions[dictData] = newLookup[i]
}
unified, err := unifier.GetResultWithIndexType(dt.IndexType)
@@ -365,6 +381,9 @@ func concatDictIndices(mem memory.Allocator, data
[]arrow.ArrayData, idxType arr
outData := out.Bytes()
for i, d := range data {
+ if d.Len() == 0 {
+ continue
+ }
transposeMap :=
arrow.Int32Traits.CastFromBytes(transpositions[i].Bytes())
src := d.Buffers()[1].Bytes()
if d.Buffers()[0] == nil {
@@ -607,13 +626,19 @@ func concat(data []arrow.ArrayData, mem memory.Allocator)
(arr arrow.ArrayData,
dict0 := MakeFromData(data[0].Dictionary())
defer dict0.Release()
for _, d := range data {
+ // Chunked arrays often share one immutable dictionary.
Its
+ // backing Data pointer is enough to prove equality,
avoiding
+ // a full scan of the dictionary for every chunk.
+ if d.Dictionary() == data[0].Dictionary() {
+ continue
+ }
dict := MakeFromData(d.Dictionary())
- if !Equal(dict0, dict) {
- dict.Release()
+ equal := Equal(dict0, dict)
+ dict.Release()
+ if !equal {
dictsSame = false
break
}
- dict.Release()
}
if dictsSame {
diff --git a/arrow/array/concat_dictionary_reuse_test.go
b/arrow/array/concat_dictionary_reuse_test.go
new file mode 100644
index 00000000..8a5ad7d3
--- /dev/null
+++ b/arrow/array/concat_dictionary_reuse_test.go
@@ -0,0 +1,167 @@
+// 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/require"
+)
+
+// makeConcatDictionaryChunks reuses the same dictionary Data for all chunks
+// selecting the same values entry, including when the indices differ.
+func makeConcatDictionaryChunks(mem memory.Allocator, valueSets [][]string,
sequence []int, rows int, nullable, sliced bool) []arrow.Array {
+ dictionaries := make([]arrow.Array, len(valueSets))
+ for i, values := range valueSets {
+ builder := array.NewStringBuilder(mem)
+ builder.AppendValues(values, nil)
+ dictionaries[i] = builder.NewArray()
+ builder.Release()
+ }
+ defer func() {
+ for _, dict := range dictionaries {
+ dict.Release()
+ }
+ }()
+
+ dtype := &arrow.DictionaryType{
+ IndexType: arrow.PrimitiveTypes.Int32,
+ ValueType: arrow.BinaryTypes.String,
+ }
+ out := make([]arrow.Array, 0, len(sequence))
+ for chunkIndex, dictIndex := range sequence {
+ builder := array.NewInt32Builder(mem)
+ for row := 0; row < rows; row++ {
+ if nullable && (row+chunkIndex)%11 == 0 {
+ builder.AppendNull()
+ } else {
+ builder.Append(int32((row + chunkIndex) %
len(valueSets[dictIndex])))
+ }
+ }
+ indices := builder.NewArray()
+ builder.Release()
+ dictArray := array.NewDictionaryArray(dtype, indices,
dictionaries[dictIndex])
+ indices.Release()
+
+ if sliced && rows > 1 {
+ start := int64(chunkIndex % 2)
+ slice := array.NewSlice(dictArray, start, int64(rows))
+ dictArray.Release()
+ dictArray = slice.(*array.Dictionary)
+ }
+ out = append(out, dictArray)
+ }
+ return out
+}
+
+func releaseConcatDictionaryChunks(chunks []arrow.Array) {
+ for _, chunk := range chunks {
+ chunk.Release()
+ }
+}
+
+func TestConcatenateDictionaryReuse(t *testing.T) {
+ base := []string{"alpha", "beta", "gamma", "delta", "epsilon"}
+ reversed := []string{"epsilon", "gamma", "alpha", "zeta", "beta"}
+ tests := []struct {
+ name string
+ valueSets [][]string
+ sequence []int
+ rows int
+ nullable bool
+ sliced bool
+ }{
+ {"shared", [][]string{base}, []int{0, 0, 0, 0}, 29, false,
false},
+ {"shared_sliced_nulls", [][]string{base}, []int{0, 0, 0, 0, 0},
29, true, true},
+ {"equal_distinct_data", [][]string{base, append([]string(nil),
base...)}, []int{0, 1, 0, 1}, 29, true, false},
+ {"mixed_repeated", [][]string{base, reversed}, []int{0, 1, 0,
1, 1, 0, 1, 0}, 37, true, true},
+ {"mixed_empty_chunks", [][]string{base, reversed}, []int{0, 1,
0, 1}, 0, false, false},
+ {"single_chunk", [][]string{base}, []int{0}, 31, true, false},
+ }
+
+ for _, tc := range tests {
+ t.Run(tc.name, func(t *testing.T) {
+ mem :=
memory.NewCheckedAllocator(memory.NewGoAllocator())
+ defer mem.AssertSize(t, 0)
+
+ inputs := makeConcatDictionaryChunks(mem, tc.valueSets,
tc.sequence, tc.rows, tc.nullable, tc.sliced)
+ defer releaseConcatDictionaryChunks(inputs)
+ expected := make([]string, 0)
+ for _, in := range inputs {
+ for i := 0; i < in.Len(); i++ {
+ expected = append(expected,
in.ValueStr(i))
+ }
+ }
+
+ combined, err := array.Concatenate(inputs, mem)
+ require.NoError(t, err)
+ defer combined.Release()
+ require.NoError(t, array.ValidateFull(combined))
+ require.Equal(t, len(expected), combined.Len())
+ for i, want := range expected {
+ require.Equal(t, want, combined.ValueStr(i),
"row %d", i)
+ }
+ })
+ }
+}
+
+// BenchmarkConcatenateDictionaryReuse measures the complete public concatenate
+// call with shared dictionaries and repeated dictionary versions. Run with:
+// go test ./arrow/array -run '^$' -bench
'^BenchmarkConcatenateDictionaryReuse$' -benchmem
+func BenchmarkConcatenateDictionaryReuse(b *testing.B) {
+ base := make([]string, 8192)
+ for i := range base {
+ base[i] = fmt.Sprintf("dictionary-value-%06d", i)
+ }
+ changed := append([]string(nil), base...)
+ for i := 0; i < len(changed); i += 16 {
+ changed[i] = fmt.Sprintf("new-value-%06d", i)
+ }
+ second := append([]string(nil), base...)
+ for i := 1; i < len(second); i += 16 {
+ second[i] = fmt.Sprintf("another-new-value-%06d", i)
+ }
+
+ cases := []struct {
+ name string
+ valueSets [][]string
+ sequence []int
+ }{
+ {"shared_dictionary", [][]string{base}, []int{0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0}},
+ {"repeated_mixed_dictionaries", [][]string{base, changed,
second}, []int{0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2}},
+ }
+ for _, tc := range cases {
+ b.Run(tc.name, func(b *testing.B) {
+ mem := memory.NewGoAllocator()
+ inputs := makeConcatDictionaryChunks(mem, tc.valueSets,
tc.sequence, 256, true, false)
+ defer releaseConcatDictionaryChunks(inputs)
+ b.ReportAllocs()
+ b.ResetTimer()
+ for b.Loop() {
+ output, err := array.Concatenate(inputs, mem)
+ if err != nil {
+ b.Fatal(err)
+ }
+ output.Release()
+ }
+ })
+ }
+}
