mbutrovich commented on PR #26191: URL: https://github.com/apache/datafusion/pull/26191#issuecomment-6648710943
I've been looking at architecture-specific opportunities in the codebase, and came across this recent PR. I just wanted to add my analysis, even though this already merged. > Both use `std::array::from_fn::<LANES>` to gather + hash into a temporary array, then store the whole batch, keeps the independent hash chains in flight so the pipeline isn't serialized on store-to-load deps. @Rich-T-kid I read the generated code on both sides after this merged, and I have a different hypothesis for where the gain comes from. As I read the aarch64 code from before this PR, the [old loops](https://github.com/apache/datafusion/blob/1c49b7f6d38a6c38ff0763855814db2ef5d4a352/datafusion/common/src/hash_utils.rs#L324-L332) weren't serialized. The fresh loop never loaded from `hashes_buffer`, and LLVM had already unrolled it 4x into four independent hash chains. In the rehash loop, row `i` reads and writes only `hashes_buffer[i]`, so no dependence carries through memory from one iteration to the next. What I think changed is how LLVM vectorized the rehash loop. `foldhash::fast` hashes an `i64` with one [`folded_multiply`](https://github.com/orlp/foldhash/blob/8f878c636fda9c9e93384824ea45e06d03f009f5/src/fast.rs#L114-L121), a 64x64 to 128-bit multiply, and NEON has no vector form of it. Before this PR, LLVM still vectorized the rehash loop two rows at a time, so each lane moved from a vector register to a general register and back: ```asm ldr q1, [x12], #16 ; 2 values ldr q2, [x11] ; 2 previous hashes eor3.16b v1, v1, v2, v0 ; value ^ prev ^ constant mov.d x14, v1[1] ; lane 1 to GPR fmov x15, d1 ; lane 0 to GPR mul x16, x14, x10 umulh x14, x14, x10 mul x17, x15, x10 umulh x15, x15, x10 eor x15, x15, x17 fmov d1, x15 ; lane 0 back to NEON eor x14, x14, x16 fmov d2, x14 ; lane 1 back to NEON mov.d v1[1], v2[0] str q1, [x11], #16 ``` The `as_chunks` version isn't vectorized, so all eight lanes stay in general registers and the transfers are gone. The bot numbers fit that. The `multiple` cases hash the same column three times, which is one fresh pass and two rehash passes. If I split the [final run](https://github.com/apache/datafusion/pull/26191#issuecomment-6316935993) that way, a fresh pass went from 4.6 to 3.8 us and a rehash pass from 6.2 to 4.0 us. Before this PR a rehash pass cost 35% more than a fresh one. Now they cost about the same, which matches a rehash row now being a fresh row plus one load and one `eor`. The listing doesn't explain the fresh path to me. It went from 4x to 16x unrolled, which cuts the instructions per row by about 5% (5.5 to 5.25) and keeps the same two multiplies per row. On x86_64 at the default target CPU, LLVM vectorizes both old loops two rows at a time with `pextrq`, `movq`, and `punpcklqdq` round trips. The new version keeps that pattern and unrolls it. So I'd expect the rehash gain not to carry over to x86, and the bot runs were all on Neoverse-V2. Should we change the comment on [`hash_prim_fresh_dense`](https://github.com/apache/datafusion/blob/600420daf7d9142bac0cab7eeb8ec624c247e79b/datafusion/common/src/hash_utils.rs#L343-L345) so it doesn't cite store-to-load dependencies? The fresh path never loads from the hash buffer, so the next person tuning `LANES` would start from the wrong model. -- 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]
