mightsleep commented on PR #11467: URL: https://github.com/apache/arrow-rs/pull/11467#issuecomment-6415901897
> > What do you mean by the faster split for `u32`? > It's two tricks. For about ln2 (69%) of divisors the rounded-up multiplier is exact without the add, so it's just `mulhi(a, n) >> p` (the "cooperative" case from Hacker's Delight). For the rest you round the multiplier down and bump the dividend instead, `mulhi(a, n.saturating_add(1)) >> p`, which is a classic from ridiculous_fish https://ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html. Both stay a plain mulhi in u32 lanes. On Zen 5 it was about 1.25-1.7x over the PR, but it means a third variant, which is where the semver comment came from. I don't think `u32` has much left after that. `u64`/`i64` is the more interesting part: folding the high bits through `2^k mod d` avoids the 64-bit mulhi, and with AVX-512 IFMA that's around 3x over the PR here. But it's roughly on parity without AVX-512, and arrow doesn't do runtime dispatch, so it wouldn't help most builds anyway (sadge). Just mentioning it because I think it's cool. Gist with map inc. -- 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]
