geoffreyclaude opened a new pull request, #12235: URL: https://github.com/apache/arrow-rs/pull/12235
Depends on #11771. **[Review only the performance changes](https://github.com/geoffreyclaude/arrow-rs/compare/665e9ddcde386d4bf3995bc5784e552aa8028fb7...0e23c0bb01b93cf71a492d0b2475640c09e6fd69).** This draft is built on #11771's correctness fix and benchmark commit. Until that PR merges and this branch is rebased, the upstream Files changed tab also includes the parent changes. #11771 can merge independently; this draft is for discussing the optimization's additional complexity. Latency measurements remain outstanding. # Which issue does this PR close? Follow-up to #11771 and its [performance review](https://github.com/apache/arrow-rs/pull/11771#discussion_r4560880150). No additional correctness issue is closed here. # Rationale for this change Correct Union ordering in #11771 requires finding logical nulls and handling descending child values. Its straightforward implementation materializes the parent Union's null bitmap, consults it during both length calculation and writing, and adds a validity byte to every non-null Union value. This PR reduces that work while preserving the ordering and null-decoding semantics established in #11771. # What changes are included in this PR? - Cache child logical-null masks with their encoded rows. Classify selected values during row-length preparation and record nulls in private row tags, so writing does not repeat that classification. - Track a single length for inputs whose children are all logically null or empty, and for null-free inputs whose children have equal fixed encoded widths. Other inputs retain per-row length calculation. This includes sparse inputs whose nulls appear only in inactive children. - Combine the Union validity and type tag into one byte. Non-null tags are `type_id + 1`, inverted for descending order; `0x00` and `0xFF` remain available for null placement. Update decoding and the format diagrams together. - Extend the portable benchmarks and add focused tests for equal-width children with inactive nulls, and all-selected-null dense values with repeated offsets and an empty unused child. Arrow type IDs are nonnegative. The private encoder uses `-1` to mark logical nulls, lazily copying tags on the first selected null; input arrays are never mutated. Every append constructs fresh encoders, prepares them once, then writes rows. Child logical-null masks preserve dictionary, run-end-encoded, and nested Union null semantics. The copied tag buffer uses one byte per row instead of a bit-packed parent null buffer. In return, non-null output saves one byte per Union level, and fixed-length paths can avoid the temporary per-row lengths vector. These instruction measurements do not establish peak-memory or cache improvements. # Are these changes tested? The added tests use the existing native-ordering and re-encoding helpers. They cover dense/sparse layouts, all sort options, sliced arrays, non-contiguous type IDs, inactive nulls, a selected null, and following string columns. The all-null test also leaves an unselected value valid to exercise the general path. Existing dictionary and nested Union regressions remain in place. The `row_format` benchmark now has 23 portable Union fixtures. It covers dense/sparse 2/4/8-field inputs, random nulls, inactive-only nulls, all physical values null, all selected values null with valid inactive values, surrounding string columns, small batches, unequal-width and Utf8 children, and descending order. The existing helper measures fresh/prepared conversion, decoding, and append. The benchmark-only commit **`b0abecb071603a8be417cf335713fdaeb5818a0a`** is the baseline for the optimization commit **`0e23c0bb01b93cf71a492d0b2475640c09e6fd69`**. Native Apple Silicon retired-instruction counts below compare these exact implementations using the same benchmark inputs, dependency lockfile, Rust 1.99.1 compiler and release-based profiling configuration. Percentages are changes from the correctness baseline; negative is fewer instructions. These are **instruction counts, not latency**. | Input (4,096 rows unless noted) | Fresh converter | Reused converter | |---|---:|---:| | Dense, 2 fields, no nulls | -32.8% | -33.9% | | Sparse, 4 fields, no nulls | -22.2% | -23.2% | | Sparse, 4 fields, 20% nulls | -15.0% | -15.6% | | Sparse, 4 fields, inactive nulls only | -14.6% | -15.0% | | Sparse between strings, 20% nulls | -9.0% | -9.1% | | Sparse descending, 20% nulls | -13.9% | -14.5% | | Sparse with Int64 child, 20% nulls | -10.8% | -11.3% | | Sparse with Utf8 child, 20% nulls | -7.8% | -8.0% | | Sparse, all selected null, valid inactive values | -1.5% | -1.6% | | 32 rows, sparse between strings, 20% nulls | -6.9% | -13.5% | | 1 row, sparse between strings, all null | -0.8% | -1.2% | Counts use the macOS `proc_pid_rusage` process instruction counter, including user and kernel instructions, with input construction outside the measured region. Each value is the median of 18 calibrated samples: two process launches in reversed implementation order, nine batches of 300 conversions, after 100 warmups. All 23 fixtures improved against #11771 in this run. The small one-row fresh-converter difference is too small and variable to motivate further specialization. Platform-specific counter instrumentation is kept outside the PR. The common-width path earns its additional branch: earlier controlled comparisons showed that enabling it used roughly 19.5% fewer instructions for a sparse four-field null-free conversion, 4.5% fewer with 20% nulls, and 9% fewer with inactive-only nulls at 4,096 rows. Surrounding strings reduce the percentage benefit but preserve it. There is no blanket claim of beating the old `main` implementation. Against the historical review snapshot `4c03e90286b2b176dd37cf08187a61c09b09acb7`, the final small-batch fixtures still use approximately 2.7–7.0% more instructions; the unequal-width/Utf8-child cases use 0.6–1.1% more. Descending nullable input uses about 4.5% more, while that old implementation does not correctly reverse child values. These remaining correctness costs are explicit; this draft adds no batch-size thresholds or special handling to chase them. Elapsed latency and other architectures still need evaluation. # Are there any significant user-facing changes? Union row bytes change again: non-null values lose the separate Union validity byte. The row format already documents that byte compatibility across versions is not guaranteed. Public signatures, comparison semantics, and decoded logical values are unchanged from #11771, including its canonical null-field selection and dictionary flattening. # AI usage disclosure Codex assisted with the implementation, benchmarks, tests, instruction-count investigation, adversarial review, and PR description. -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
