Benchmark map hashing separately from map normalization for native shuffle

[viirya]

What is the problem the feature request solves?

The nested-key shuffle benchmark merged in #5788 measures planning, scanning, key construction, shuffle and sink consumption together. It does not establish whether the cost of larger map keys comes from hashing, map normalization, or other execution overhead.

For struct<map<string,int>,int> with 2–50 entries in reversed input order and 201 partitions, the reported run measured 2,449 ms for Comet native shuffle versus 2,107 ms for Comet JVM shuffle (JVM/native = 0.86x). The singleton control favored native, so its result cannot be generalized to larger maps. Differences between forward and reversed cases in that sequential run do not by themselves establish sorting as the bottleneck.

This follows andygrove's review suggestion to isolate the hash kernel before deciding whether it needs optimization.

Describe the potential solution

Extend the existing Criterion benchmarks in native/spark-expr/benches/hash.rs and native/spark-expr/benches/map_sort.rs with matched inputs:

• Use the PR's map<string,int> keys, including the enclosing struct<map<string,int>,int> hash key. Retain a singleton control and cover variable 2–10 and 2–50 entries per row.
• Use distinct keys with aligned values, in forward and reversed input order, preserving the same key/value pairs. Reproduce the PR's key generation and cardinality distribution so string ordering is comparable.
• Measure hashing only with create_murmur3_hashes over pre-normalized data, normalization only with spark_map_sort, and normalization followed by hashing over the same logical maps. Spark 4.x introduces map normalization through InsertMapSortInRepartitionExpressions.
• Construct input batches outside the timed region. Use consistent batch sizes and hash seed 42, consume the outputs, and make hash-buffer initialization/allocation costs explicit so they are not mistaken for kernel cost.
• Check outside timing that forward and reversed inputs produce equivalent normalized maps and identical final partition-key hashes. Raw map hashes need not be order-independent without normalization.

Report matched results with Criterion uncertainty estimates, row/entry throughput, build commit, dependency versions and hardware. Explain whether hashing or normalization dominates these native microbenchmarks, and whether that identifies an optimization target in hash_funcs/utils.rs, spark_map_sort, or warrants further end-to-end profiling. Native kernel measurements alone will not explain every difference from the JVM shuffle baseline.

Additional context

• bench: measure nested types as native shuffle hash partitioning keys #5788 / Benchmark nested types as native shuffle hash partitioning keys #5787 provide the end-to-end benchmark and results.
• The cited run used Spark 4.1.3 on an Apple M4 Max, with the disclosed local Arrow 59.2.0 lockfile workaround. Future results should identify their dependency versions rather than mix measurement cohorts.
• Existing hash coverage includes fixed-size map cases; existing map-sort coverage uses different cardinalities. The missing piece is a matched decomposition for the shapes above.
• Hashing array<struct<..>> is dominated by per-element slicing and dispatch #5777 and perf: batch the nested-element list hash for flat struct elements #5778 concern recursive array-of-struct hashing; this issue tracks map hashing versus normalization.

This is measurement work to guide any subsequent optimization. It does not propose changing the default of spark.comet.shuffle.native.partitioning.hash.nested.enabled.

[viirya]

I'm working on this.