divyankshah commented on PR #5235: URL: https://github.com/apache/datafusion-comet/pull/5235#issuecomment-5176230997
> First pass, focused on the two items that need to change. I have not gone through test coverage or the docs yet, so expect a second round. > > Nice find on the root cause, and the diagnosis matches what I see in Spark's `SQLOrderingUtil`. > > **1. The normalization is inside the per-row loop, and it is quadratic.** > > In `arrays_overlap.rs:431` the comparator is built per row, so `normalize_negative_zero` runs once per row per side. `probe` is `left.value(i)`, and arrow-rs's `GenericListArray::slice` only narrows the offsets and null buffer, it leaves `values` pointing at the entire child buffer. So `list.values()` in the `DataType::List` branch hands back every float in the column, and each row copies all of them. > > I checked out the branch and added a nested benchmark to compare against `apache/main`: > > benchmark main this PR > `array<array<double>>` 1024 rows x 4 inner x 8 floats 192.8 us 223.8 ms > `array<array<double>>` 4096 rows x 4 inner x 8 floats 760.9 us 3.574 s > `array<array<int>>` 4096 rows x 4 inner x 8 ints 753.0 us 980.3 us > 4x the rows gives 16x the time, which confirms the shape. The int32 row also regresses 30% despite having no float leaves at all, from the unconditional `ListArray::new` rebuild. > > Could you hoist the normalization above the row loop, normalizing `left` and `right` once and slicing per row from the normalized arrays? A cheap recursive `DataType` check to skip types with no float leaf would take care of the int32 case. `array_position`'s `position_fallback` only normalizes once per call so it is fine on the loop question, but it would still benefit from the type gate. Since this touches the same lines as the comparator hoisting in #5194, rebasing on that first as you suggested is probably the easier path. > > **2. `normalize_float` already exists, and using it also fixes NaN.** > > There is a `normalize_float` at `native/spark-expr/src/math_funcs/internal/normalize_nan.rs:110`, and `hll_plus_plus.rs:126` applies it to Float32/Float64 leaves with `unary()`, which is close to what the leaf arms here do. Reusing it drops the duplicate logic and lets you use `unary()`, which works on the values buffer and preserves the null buffer. > > It also closes a second mismatch in the same code path. Spark's `SQLOrderingUtil.compareDoubles` is `if (x == y) 0 else java.lang.Double.compare(x, y)`, and `Double.compare` goes through `doubleToLongBits`, which collapses every NaN payload including the sign bit. Arrow's comparator uses `total_cmp`, which sorts `-NaN` below `-Infinity`. On this branch: > > ``` > [[-NaN]] overlaps [[NaN]] => false (Spark returns true) > ``` > > `normalize_float` canonicalizes NaN as well as signed zero, so it fixes this for free. Worth noting because the new comment on `test_nested_float_total_order` says NaN matches itself and matches Spark, which currently only holds for canonical positive NaN. > > One process note: `gh pr checks` reports no checks on this branch yet, so nothing has been validated by CI. I will get the workflow approved. Hi @andygrove, Thanks for the thorough review and feedback, this was really helpful. Both points addressed in the latest commit: 1) Hoisted normalization above the row loop in arrays_overlap.rs, so it runs once per column instead of rebuilding the whole float buffer on every row. Also gated it behind a has_float_leaf check so non-float types (like your int32 case) skip it entirely. Re-ran your benchmark shape locally: 1024 rows went from 223.8ms to ~650µs, 4096 rows from 3.574s to 1.9ms. 2) Switched to the existing normalize_float (from normalize_nan.rs, already used in hll_plus_plus.rs) instead of the hand-rolled version, so NaN payloads get canonicalized too. Added a test for [[-NaN]] vs [[NaN]]. The array_position's fallback also got the type gate, though it didn't have the per-row issue since it already normalized once per call. Please let me know if anything needs to be adjusted. -- 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] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
