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 b4b0c04a perf(compute): use typed memo insertion for binary hashes
(#1315)
b4b0c04a is described below
commit b4b0c04a0b1ef7f6001b5a380e68a918bfe93f4f
Author: Minh Vu <[email protected]>
AuthorDate: Tue Oct 6 16:23:13 2026 +0200
perf(compute): use typed memo insertion for binary hashes (#1315)
## What does this change?
- `doAppendBinary` and `doAppendFixedSize` still called
`MemoTable.GetOrInsert` for every value.
- The memo is already a `TypedMemoTable[[]byte]`.
- Use `InsertOrGet` directly, like the numeric hash paths.
- Null handling is unchanged.
## Why
This removes the `[]byte` to `interface{}` call-site conversion from the
compute dictionary and unique kernels. It also makes the typed binary
memo path reachable from these hot loops.
## Benchmark
Command:
```text
go test -p 1 -vet=off ./arrow/compute -run '^$' -bench
'^BenchmarkDictionaryEncodeBinary$' -benchmem -benchtime=500ms -count=7
```
Apple M1 Pro, macOS arm64, Go 1.26.3. The numbers below are medians of 7
runs. Baseline uses `GetOrInsert` at both call sites. After uses
`TypedMemoTable[[]byte].InsertOrGet`.
| Case | Before | After | Change |
| --- | ---: | ---: | ---: |
| string, 65,536 values | 4,837,326 ns/op | 3,151,276 ns/op | 34.9%
faster |
| fixed-size binary 16, 65,536 values | 4,445,131 ns/op | 3,134,294
ns/op | 29.5% faster |
| string B/op | 3,444,557 | 1,871,270 | 45.7% fewer |
| fixed-size binary B/op | 3,444,128 | 1,870,749 | 45.7% fewer |
| string allocs/op | 131,150 | 65,613 | 50.0% fewer |
| fixed-size binary allocs/op | 131,146 | 65,609 | 50.0% fewer |
## Coverage
- Existing string and binary dictionary tests cover the variable-width
path.
- Added a fixed-size-binary dictionary test.
- Added string and 16-byte fixed-size-binary benchmarks.
- `go test -p 1 ./arrow/compute -count=1`
No public API changes.
---
arrow/compute/internal/kernels/vector_hash.go | 6 +-
arrow/compute/vector_hash_binary_bench_test.go | 103 ++++++++++++++++++++
arrow/compute/vector_hash_binary_test.go | 127 +++++++++++++++++++++++++
3 files changed, 234 insertions(+), 2 deletions(-)
diff --git a/arrow/compute/internal/kernels/vector_hash.go
b/arrow/compute/internal/kernels/vector_hash.go
index ecad7e98..6eacba05 100644
--- a/arrow/compute/internal/kernels/vector_hash.go
+++ b/arrow/compute/internal/kernels/vector_hash.go
@@ -295,12 +295,13 @@ func doAppendBinary[OffsetT int32 | int64](action Action,
memo hashing.MemoTable
offsets = exec.GetSpanOffsets[OffsetT](arr, 1)
data = arr.Buffers[2].Buf
shouldEncodeNulls = action.ShouldEncodeNulls()
+ typedMemo = memo.(hashing.TypedMemoTable[[]byte])
)
return bitutils.VisitBitBlocksShort(bitmap, arr.Offset, arr.Len,
func(pos int64) error {
v := data[offsets[pos]:offsets[pos+1]]
- idx, found, err := memo.GetOrInsert(v)
+ idx, found, err := typedMemo.InsertOrGet(v)
if err != nil {
return err
}
@@ -328,12 +329,13 @@ func doAppendFixedSize(action Action, memo
hashing.MemoTable, arr *exec.ArraySpa
sz := int64(arr.Type.(arrow.FixedWidthDataType).Bytes())
arrData := arr.Buffers[1].Buf[arr.Offset*sz:]
shouldEncodeNulls := action.ShouldEncodeNulls()
+ typedMemo := memo.(hashing.TypedMemoTable[[]byte])
return bitutils.VisitBitBlocksShort(arr.Buffers[0].Buf, arr.Offset,
arr.Len,
func(pos int64) error {
// fixed size type memo table we use a binary memo table
// so get the raw bytes
- idx, found, err := memo.GetOrInsert(arrData[pos*sz :
(pos+1)*sz])
+ idx, found, err := typedMemo.InsertOrGet(arrData[pos*sz
: (pos+1)*sz])
if err != nil {
return err
}
diff --git a/arrow/compute/vector_hash_binary_bench_test.go
b/arrow/compute/vector_hash_binary_bench_test.go
new file mode 100644
index 00000000..fbf68654
--- /dev/null
+++ b/arrow/compute/vector_hash_binary_bench_test.go
@@ -0,0 +1,103 @@
+// 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.
+
+//go:build go1.24
+
+package compute_test
+
+import (
+ "context"
+ "encoding/binary"
+ "fmt"
+ "testing"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/array"
+ "github.com/apache/arrow-go/v18/arrow/compute"
+ "github.com/apache/arrow-go/v18/arrow/memory"
+)
+
+func BenchmarkDictionaryEncodeBinary(b *testing.B) {
+ const (
+ nvalues = 1 << 16
+ nunique = 100
+ )
+
+ mem := memory.DefaultAllocator
+ ctx := compute.WithAllocator(context.Background(), mem)
+
+ b.Run("string", func(b *testing.B) {
+ values := make([]string, nvalues)
+ bytes := 0
+ for i := range values {
+ values[i] = fmt.Sprintf("value-%08d", i%nunique)
+ bytes += len(values[i])
+ }
+
+ builder := array.NewStringBuilder(mem)
+ builder.AppendValues(values, nil)
+ input := builder.NewStringArray()
+ builder.Release()
+ defer input.Release()
+
+ benchmarkDictionaryEncodeBinary(b, ctx, input, bytes)
+ })
+
+ b.Run("large-string", func(b *testing.B) {
+ values := make([]string, nvalues)
+ bytes := 0
+ for i := range values {
+ values[i] = fmt.Sprintf("value-%08d", i%nunique)
+ bytes += len(values[i])
+ }
+
+ builder := array.NewLargeStringBuilder(mem)
+ builder.AppendValues(values, nil)
+ input := builder.NewLargeStringArray()
+ builder.Release()
+ defer input.Release()
+
+ benchmarkDictionaryEncodeBinary(b, ctx, input, bytes)
+ })
+
+ b.Run("fixed-size-binary-16", func(b *testing.B) {
+ values := make([][]byte, nvalues)
+ for i := range values {
+ values[i] = make([]byte, 16)
+ binary.LittleEndian.PutUint32(values[i],
uint32(i%nunique))
+ }
+
+ builder := array.NewFixedSizeBinaryBuilder(mem,
&arrow.FixedSizeBinaryType{ByteWidth: 16})
+ builder.AppendValues(values, nil)
+ input := builder.NewFixedSizeBinaryArray()
+ builder.Release()
+ defer input.Release()
+
+ benchmarkDictionaryEncodeBinary(b, ctx, input, nvalues*16)
+ })
+}
+
+func benchmarkDictionaryEncodeBinary(b *testing.B, ctx context.Context, input
arrow.Array, bytes int) {
+ b.ReportAllocs()
+ b.SetBytes(int64(bytes))
+ for b.Loop() {
+ result, err := compute.DictionaryEncodeArray(ctx,
compute.DictionaryEncodeOptions{}, input)
+ if err != nil {
+ b.Fatal(err)
+ }
+ result.Release()
+ }
+}
diff --git a/arrow/compute/vector_hash_binary_test.go
b/arrow/compute/vector_hash_binary_test.go
new file mode 100644
index 00000000..0029d98d
--- /dev/null
+++ b/arrow/compute/vector_hash_binary_test.go
@@ -0,0 +1,127 @@
+// 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.
+
+//go:build go1.18
+
+package compute_test
+
+import (
+ "context"
+ "fmt"
+ "strings"
+ "testing"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/array"
+ "github.com/apache/arrow-go/v18/arrow/compute"
+ "github.com/apache/arrow-go/v18/arrow/memory"
+ "github.com/stretchr/testify/require"
+)
+
+func TestDictionaryEncodeFixedSizeBinary(t *testing.T) {
+ mem := memory.NewCheckedAllocator(memory.DefaultAllocator)
+ defer mem.AssertSize(t, 0)
+
+ values := [][]byte{
+ {0, 0, 0, 1},
+ {0, 0, 0, 2},
+ {0, 0, 0, 1},
+ {0, 0, 0, 3},
+ {0, 0, 0, 2},
+ {0, 0, 0, 3},
+ }
+ valid := []bool{true, true, true, false, true, true}
+
+ builder := array.NewFixedSizeBinaryBuilder(mem,
&arrow.FixedSizeBinaryType{ByteWidth: 4})
+ builder.AppendValues(values, valid)
+ input := builder.NewFixedSizeBinaryArray()
+ builder.Release()
+ defer input.Release()
+
+ ctx := compute.WithAllocator(context.Background(), mem)
+ result, err := compute.DictionaryEncodeArray(ctx,
compute.DictionaryEncodeOptions{}, input)
+ require.NoError(t, err)
+ defer result.Release()
+
+ encoded := result.(*array.Dictionary)
+ require.Equal(t, []int32{0, 1, 0, 0, 1, 2},
encoded.Indices().(*array.Int32).Int32Values())
+ require.Equal(t, 1, encoded.NullN())
+ require.Equal(t, 3, encoded.Dictionary().Len())
+
+ dict := encoded.Dictionary().(*array.FixedSizeBinary)
+ require.Equal(t, values[0], dict.Value(0))
+ require.Equal(t, values[1], dict.Value(1))
+ require.Equal(t, values[3], dict.Value(2))
+}
+
+func TestDictionaryEncodeBinarySlicedNullModes(t *testing.T) {
+ for _, dt := range []arrow.DataType{arrow.BinaryTypes.Binary,
arrow.BinaryTypes.LargeBinary, arrow.BinaryTypes.String,
arrow.BinaryTypes.LargeString, &arrow.FixedSizeBinaryType{ByteWidth: 4}} {
+ t.Run(dt.String(), func(t *testing.T) {
+ for _, mode := range
[]compute.NullEncodingBehavior{compute.NullEncodingMask,
compute.NullEncodingEncode} {
+ t.Run(fmt.Sprint(mode), func(t *testing.T) {
+ mem :=
memory.NewCheckedAllocator(memory.DefaultAllocator)
+ defer mem.AssertSize(t, 0)
+ inputJSON := `["skip", "aaaa", null,
"bbbb", "aaaa", null, "skip"]`
+ if dt.ID() == arrow.BINARY || dt.ID()
== arrow.LARGE_BINARY || dt.ID() == arrow.FIXED_SIZE_BINARY {
+ inputJSON = `["c2tpcA==",
"YWFhYQ==", null, "YmJiYg==", "YWFhYQ==", null, "c2tpcA=="]`
+ }
+ base, _, err := array.FromJSON(mem, dt,
strings.NewReader(inputJSON))
+ require.NoError(t, err)
+ defer base.Release()
+ input := array.NewSlice(base, 1, 6)
+ defer input.Release()
+ execCtx := compute.DefaultExecCtx()
+ execCtx.ChunkSize = 2
+ ctx :=
compute.SetExecCtx(compute.WithAllocator(context.Background(), mem), execCtx)
+ result, err :=
compute.DictionaryEncodeArray(ctx,
compute.DictionaryEncodeOptions{NullEncoding: mode}, input)
+ require.NoError(t, err)
+ defer result.Release()
+ encoded := result.(*array.Dictionary)
+ require.True(t, arrow.TypeEqual(dt,
encoded.Dictionary().DataType()))
+ wantJSON := `["aaaa", "bbbb"]`
+ if mode == compute.NullEncodingEncode {
+ wantJSON = `["aaaa", null,
"bbbb"]`
+ }
+ if dt.ID() == arrow.BINARY || dt.ID()
== arrow.LARGE_BINARY || dt.ID() == arrow.FIXED_SIZE_BINARY {
+ wantJSON = `["YWFhYQ==",
"YmJiYg=="]`
+ if mode ==
compute.NullEncodingEncode {
+ wantJSON =
`["YWFhYQ==", null, "YmJiYg=="]`
+ }
+ }
+ wantDictionary, _, err :=
array.FromJSON(mem, dt, strings.NewReader(wantJSON))
+ require.NoError(t, err)
+ defer wantDictionary.Release()
+ require.True(t,
array.Equal(wantDictionary, encoded.Dictionary()))
+
+ require.Equal(t, 5, encoded.Len())
+ require.Equal(t,
encoded.GetValueIndex(0), encoded.GetValueIndex(3))
+ require.NotEqual(t,
encoded.GetValueIndex(0), encoded.GetValueIndex(2))
+ if mode == compute.NullEncodingMask {
+ require.Equal(t, 2,
encoded.Dictionary().Len())
+ require.Equal(t, 2,
encoded.NullN())
+ require.True(t,
encoded.IsNull(1))
+ require.True(t,
encoded.IsNull(4))
+ } else {
+ require.Equal(t, 3,
encoded.Dictionary().Len())
+ require.Zero(t, encoded.NullN())
+ require.Equal(t,
encoded.GetValueIndex(1), encoded.GetValueIndex(4))
+ require.True(t,
encoded.Dictionary().IsNull(encoded.GetValueIndex(1)))
+ }
+ })
+ }
+ })
+ }
+}
