mbutrovich commented on PR #9683: URL: https://github.com/apache/arrow-rs/pull/9683#issuecomment-6808863683
I picked this back up and reworked the kernel ([a12caca...7d38647](https://github.com/apache/arrow-rs/compare/a12caca2534723779ec8261838f842a7beea292d...7d386474fb7fd8f275039d581285b2b15bb64eb1)). It skips the bytes that every row shares, copies the next 12 bytes of each row into a `u128` next to the row's index, radix sorts those, and compares the rest of a row only to break ties. It no longer uses `unsafe`. a12caca has the same algorithm as the PR before this work (d9018f5), after the API changes to return `Result<UInt32Array, ArrowError>` and drop the `Row` helpers. Against `lexsort_to_indices`, counting cases that are faster or slower in both the default and aligned runs, radix sort went from 24 faster and 31 slower on the Xeon to 44 and 19, and from 37 and 19 to 50 and 14 on Neoverse-V2 (a12caca: [Xeon](https://github.com/apache/arrow-rs/pull/9683#issuecomment-6757338133), [Neoverse-V2](https://github.com/apache/arrow-rs/pull/9683#issuecomment-6757323355). 7d38647: [Xeon](https://github.com/apache/arrow-rs/pull/9683#issuecomment-6802931753), [Neoverse-V2](https://github.com/apache/arrow-rs/pull/9683#issuecomment-6802916442)). The 7d38647 runs have 6 more cases, two keys whose rows tie past 8 bytes after the shared prefix, at 4K, 32K, and 1M rows. The PR description has the full numbers. The key grew from 8 to 12 bytes in the last commit, so that an `(INT, BIGINT)` join key with small `BIGINT` values, or three low-cardinality columns, no longer ties past the key. Against the 8-byte key on the same cases (0207ad1), the join key at 1M rows is 4.14x to 4.27x faster on Neoverse-V2 and 1.91x to 1.94x on the Xeon, and the median over all 64 cases is 0.98x to 1.00x (Neoverse-V2: [default](https://github.com/apache/arrow-rs/pull/9683#issuecomment-6802117009), [aligned](https://github.com/apache/arrow-rs/pull/9683#issuecomment-6802705531). Xeon: [default](https://github.com/apache/arrow-rs/pull/9683#issuecomment-6802764499), [aligned](https://github.com/apache/arrow-rs/pull/9683#issuecomment-6802767213)). <img width="1600" height="1892" alt="radix-key12-bot" src="https://github.com/user-attachments/assets/68d66cf9-37b5-4b68-aa19-1648bc207d9d"; /> -- 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]
