You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "fallintoplace (via GitHub)" <gi...@apache.org> on 2026/10/06 10:09:41 UTC
[PR] perf(arrow): skip sorting metadata with matching keys [arrow-go]
fallintoplace opened a new pull request, #1361:
URL: https://github.com/apache/arrow-go/pull/1361
**What**
- Skip sorting when metadata keys are in the same order.
**Why**
- Avoid two index slice allocations. This also helps field and schema equality.
| Matching keys | Before | After | Allocs before / after |
| --- | ---: | ---: | ---: |
| 8 entries | 142.8 ns | 35.8 ns | 2 / 0 |
| 128 entries | 1.873 µs | 0.601 µs | 2 / 0 |
| 16 fields, 32 entries per field | 7.733 µs | 2.691 µs | 32 / 0 |
Apple M1 Pro, Go 1.26.3, `GOMAXPROCS=1`. Medians from 10 samples per revision at 500 ms, in ABBA order. Base: `c1c8ed0a`.
Reversed and late-swap controls showed no significant change. The 128-entry middle-swap control was 7.4% slower due to the extra key scan.
**Implementation**
- Return early for empty metadata.
- Check the last key before scanning keys, then compare values directly if keys match.
- Keep the sorted comparison for different key orders.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow): reduce metadata sorting overhead [arrow-go]
Posted by "zeroshade (via GitHub)" <gi...@apache.org>.
zeroshade commented on code in PR #1361:
URL: https://github.com/apache/arrow-go/pull/1361#discussion_r4199812812
##########
arrow/metadata_equal_benchmark_test.go:
##########
@@ -0,0 +1,171 @@
+// 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 arrow
+
+import (
+ "fmt"
+ "slices"
+ "strings"
+ "testing"
+)
+
+var metadataEqualBenchmarkResult bool
+
+func metadataEqualityBenchmarkPair(size int, pattern string) (Metadata, Metadata) {
+ keys, values := make([]string, size), make([]string, size)
+ for i := range keys {
+ keys[i] = fmt.Sprintf("key_%04d", i)
+ values[i] = fmt.Sprintf("value_%04d", i)
+ }
+ left := NewMetadata(keys, values)
+ right := left.clone()
+ if strings.HasPrefix(pattern, "duplicate-") {
+ for i := range left.keys {
+ left.keys[i] = fmt.Sprintf("key_%04d", i/2)
+ left.values[i] = fmt.Sprintf("value_%04d", i/2)
+ right.keys[i], right.values[i] = left.keys[i], left.values[i]
+ }
+ pattern = strings.TrimPrefix(pattern, "duplicate-")
+ }
+ if pattern == "middle-swap-reversed" {
+ slices.Reverse(left.keys)
+ slices.Reverse(left.values)
+ slices.Reverse(right.keys)
+ slices.Reverse(right.values)
+ pattern = "middle-swap"
+ }
+ switch pattern {
+ case "matching-reversed":
+ slices.Reverse(left.keys)
+ slices.Reverse(left.values)
+ slices.Reverse(right.keys)
+ slices.Reverse(right.values)
+ case "different-value":
+ right.values[size-1] = "different"
+ case "matching-distinct-strings":
+ for i := range right.keys {
+ right.keys[i] = strings.Clone(right.keys[i])
+ right.values[i] = strings.Clone(right.values[i])
+ }
+ case "different-key":
+ right.keys[size/2] = "different"
+ case "reversed":
+ slices.Reverse(right.keys)
+ slices.Reverse(right.values)
+ case "late-swap", "middle-swap", "penultimate-swap":
+ pos := size - 2
+ if pattern == "middle-swap" {
+ pos = size/2 - 1
+ } else if pattern == "penultimate-swap" {
+ pos = size - 3
+ }
+ right.keys[pos], right.keys[pos+1] = right.keys[pos+1], right.keys[pos]
+ right.values[pos], right.values[pos+1] = right.values[pos+1], right.values[pos]
+ }
+ return left, right
+}
+
+func BenchmarkMetadataEqual(b *testing.B) {
+ for _, size := range []int{0, 1, 8, 11, 12, 13, 16, 17, 32, 33, 128, 129, 256, 257, 1024, 2047, 2048, 2049} {
Review Comment:
Nit: sizes ≥13 all run the unchanged path, so a couple of controls are enough. `for b.Loop()` here and below.
##########
arrow/metadata_equal_benchmark_test.go:
##########
@@ -0,0 +1,171 @@
+// 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 arrow
+
+import (
+ "fmt"
+ "slices"
+ "strings"
+ "testing"
+)
+
+var metadataEqualBenchmarkResult bool
+
+func metadataEqualityBenchmarkPair(size int, pattern string) (Metadata, Metadata) {
+ keys, values := make([]string, size), make([]string, size)
+ for i := range keys {
+ keys[i] = fmt.Sprintf("key_%04d", i)
+ values[i] = fmt.Sprintf("value_%04d", i)
+ }
+ left := NewMetadata(keys, values)
+ right := left.clone()
+ if strings.HasPrefix(pattern, "duplicate-") {
+ for i := range left.keys {
+ left.keys[i] = fmt.Sprintf("key_%04d", i/2)
+ left.values[i] = fmt.Sprintf("value_%04d", i/2)
+ right.keys[i], right.values[i] = left.keys[i], left.values[i]
+ }
+ pattern = strings.TrimPrefix(pattern, "duplicate-")
+ }
+ if pattern == "middle-swap-reversed" {
+ slices.Reverse(left.keys)
+ slices.Reverse(left.values)
+ slices.Reverse(right.keys)
+ slices.Reverse(right.values)
+ pattern = "middle-swap"
+ }
+ switch pattern {
+ case "matching-reversed":
+ slices.Reverse(left.keys)
+ slices.Reverse(left.values)
+ slices.Reverse(right.keys)
+ slices.Reverse(right.values)
+ case "different-value":
+ right.values[size-1] = "different"
+ case "matching-distinct-strings":
+ for i := range right.keys {
+ right.keys[i] = strings.Clone(right.keys[i])
+ right.values[i] = strings.Clone(right.values[i])
+ }
+ case "different-key":
+ right.keys[size/2] = "different"
+ case "reversed":
+ slices.Reverse(right.keys)
+ slices.Reverse(right.values)
+ case "late-swap", "middle-swap", "penultimate-swap":
+ pos := size - 2
+ if pattern == "middle-swap" {
+ pos = size/2 - 1
+ } else if pattern == "penultimate-swap" {
+ pos = size - 3
+ }
+ right.keys[pos], right.keys[pos+1] = right.keys[pos+1], right.keys[pos]
+ right.values[pos], right.values[pos+1] = right.values[pos+1], right.values[pos]
+ }
+ return left, right
+}
+
+func BenchmarkMetadataEqual(b *testing.B) {
+ for _, size := range []int{0, 1, 8, 11, 12, 13, 16, 17, 32, 33, 128, 129, 256, 257, 1024, 2047, 2048, 2049} {
+ for _, pattern := range []string{"matching", "matching-reversed", "matching-distinct-strings", "different-value", "reversed", "late-swap", "middle-swap", "penultimate-swap", "middle-swap-reversed", "different-key"} {
+ if size == 0 && pattern != "matching" || size == 1 && pattern != "matching" && pattern != "matching-distinct-strings" && pattern != "different-value" && pattern != "different-key" {
+ continue
+ }
+ b.Run(fmt.Sprintf("size=%d/%s", size, pattern), func(b *testing.B) {
+ left, right := metadataEqualityBenchmarkPair(size, pattern)
+ if got := left.Equal(right); got != (pattern != "different-value" && pattern != "different-key") {
+ b.Fatalf("unexpected equality: %v", got)
+ }
+ b.ReportAllocs()
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ metadataEqualBenchmarkResult = left.Equal(right)
+ }
+ })
+ }
+ }
+}
+
+func BenchmarkMetadataEqualDuplicateKeys(b *testing.B) {
+ for _, size := range []int{8, 12, 13, 32, 128, 129, 257, 1024, 2049} {
+ for _, pattern := range []string{"matching", "reversed", "middle-swap"} {
+ b.Run(fmt.Sprintf("size=%d/%s", size, pattern), func(b *testing.B) {
+ left, right := metadataEqualityBenchmarkPair(size, "duplicate-"+pattern)
+ if !left.Equal(right) {
+ b.Fatal("metadata should be equal")
+ }
+ b.ReportAllocs()
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ metadataEqualBenchmarkResult = left.Equal(right)
+ }
+ })
+ }
+ }
+}
+
+func BenchmarkMetadataEqualFreshGoroutine(b *testing.B) {
Review Comment:
Nit: this mostly measures goroutine startup; consider dropping it.
##########
arrow/schema.go:
##########
@@ -139,6 +170,9 @@ func (md Metadata) Equal(rhs Metadata) bool {
if md.Len() != rhs.Len() {
return false
}
+ if md.Len() <= 12 {
Review Comment:
Nit: name this threshold and reuse it for the `[12]int` storage in `smallMetadataEqual`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow): reduce metadata sorting overhead [arrow-go]
Posted by "zeroshade (via GitHub)" <gi...@apache.org>.
zeroshade merged PR #1361:
URL: https://github.com/apache/arrow-go/pull/1361
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org