Stolen from a hellsite user

@soatok wtf did you override "3" with?

@RueNahcMohr Compiler optimizations are black magic

@soatok @RueNahcMohr basically instead of dividing by 3 it multiplies by 1/3 using a fixed poirt number that has in this case 65 fractional bits

@soatok @RueNahcMohr i raccalculated one for 1/5 i think:

0xCCCC_CCCC_CCCC_CCCD with a right shift at the end of 66

calculated that by dividing 2^64 with 5, shifting it left by how many zero leading digits it has, then adding one

@RueNahcMohr @soatok wait no that doesn”t quite work hmmm

@soatok can that really be faster than a shift?surely there is an MMX instruction that does the divide and whatever the next instruction in the program is supposed to do too. :]

@RueNahcMohr @soatok A multiplication is always faster than a division. And thanks to the limited number range in a register, you can in many cases represent division via multiplication. But it doesn't always work.

@autinerd @soatok

Number to divide by? 3
precision? 64
Shift dividend right. Shift#1
Shift dividend right. Shift#2
Add dividend to accumulator (dividend /4.000000)
Shift dividend right. Shift#3
Shift dividend right. Shift#4
Add dividend to accumulator (dividend /16.000000)
Shift dividend right. Shift#5
Shift dividend right. Shift#6
Add dividend to accumulator (dividend /64.000000)
Shift dividend right. Shift#7
Shift dividend right. Shift#8
Add dividend to accumulator (dividend /256.000000)
Shift dividend right. Shift#9
Shift dividend right. Shift#10
Add dividend to accumulator (dividend /1024.000000)
Shift dividend right. Shift#11
Shift dividend right. Shift#12
Add dividend to accumulator (dividend /4096.000000)
Shift dividend right. Shift#13
Shift dividend right. Shift#14
Add dividend to accumulator (dividend /16384.000000)
Shift dividend right. Shift#15
Shift dividend right. Shift#16
Add dividend to accumulator (dividend /65536.000000)
Shift dividend right. Shift#17
Shift dividend right. Shift#18
Add dividend to accumulator (dividend /262144.000000)
Shift dividend right. Shift#19
Shift dividend right. Shift#20
Add dividend to accumulator (dividend /1048576.000000)
Shift dividend right. Shift#21
Shift dividend right. Shift#22
Add dividend to accumulator (dividend /4194304.000000)
Shift dividend right. Shift#23
Shift dividend right. Shift#24
Add dividend to accumulator (dividend /16777216.000000)
Shift dividend right. Shift#25
Add dividend to accumulator (dividend /33554432.000000)

well, thats not faster is it!

:P
:]

@RueNahcMohr @soatok ah sorry, now I see where you wanted to go 🙈 okay, if this is faster is a good question 😅

@autinerd @RueNahcMohr I mean it's basically the barrett reduction trick lol

@RueNahcMohr @autinerd @soatok most application processors can do an arbitrary multiply in 1-3 cycles, while a divide is much slower. and yeah it’s not faster than a shift, but you can’t represent a division by 3 as a shift

@soatok Compiler authors are about as close as we can get to having wizards, I'm entirely certain.

@theorangetheme Compiler devs are wizards

Then you have open sourcerors

And finally the furries: barkanists

@soatok Rust devs wish they could have a compiler like this (No really this seems like a valid optimization no clue why rustc uses a div instruction) (Okay I'm just stupid and can't use compiler flags to save my life)

@soatok this reminded me of one of my favourite compiler things

@fre @soatok furiously opening godbolt

@NaahraTheScaled @soatok but… it does? (with optimizations enabled/in release mode)

@HorayNarea @NaahraTheScaled I apprrciate the shitpost fact checking :3

@soatok @NaahraTheScaled i have even more facts: it's actually LLVM that doesn't do this specific optimization on -O0, so even clang emits a div unless you explicitly choose to optimize! :D

@soatok is it bad that I find the assembly completely reasonable? It's just a Barrett reduction.

@sophieschmieg laughs in constant-time code

@soatok integer division is very slow, so this is a reasonable thing to do for division by a constant.

@pyromuffin Yep. It's Barrett reduction :D

@autinerd @RueNahcMohr It's also good for avoiding side-channels:

https://blog.trailofbits.com/2025/11/14/how-we-avoided-side-channels-in-our-new-post-quantum-go-cryptography-libraries/

@sophieschmieg @soatok

@sophieschmieg @soatok thanks, was wondering what to search to learn what was going on here 😅

@sophieschmieg @soatok just to confirm my understanding, if I'm following along with https://www.nayuki.io/page/barrett-reduction-algorithm, for the div3 in the image we've got a=x (the argument to div3), b = ⅓, and n = 2^64 (because uint64_t)?

@Ongion @soatok yeah.

@soatok @sophieschmieg is there any ISA which guarantees constant-time division? unless I'm missing something, this transformation could only make things better

@whitequark @sophieschmieg Nope, Barrett reduction is good here

@soatok @whitequark yeah, this is the rare compiler w for constant time programming, that has saved some Kyber implementations.
Since multiplication and shifts are so much cheaper than integer division, this is more or less the standard behavior if the compiler knows the divisor. But of course, you can't rely on it. And theoretically, the compiler is allowed to take your manual Barrett code and replace it with idiv as well, if it sees so fit.

@whitequark @soatok @sophieschmieg

Ibex has a constant-time mode, which makes operations like divide take their worst-case time in all cases. Making divide variable time is more common on simpler pipelines. For out-of-order chips, knowing that each operation takes a fixed number of cycles makes scheduling simpler and, generally, scheduling and register allocation are more power, timing, and area constrained than functional units, so the tradeoff will be between some divides being faster or having more instructions in flight at a time. The latter is usually better.

Specialised ISAs such as OTBN do make constant-time guarantees for divide. Some DSPs do as well.

@david_chisnall @soatok @sophieschmieg yeah makes sense for DSPs, I meant 'general-purpose' ISA. interesting re: Ibex! I didn't realize this existed in shipping RV silicon

@soatok @autinerd @RueNahcMohr This trick's been around since the 1990s, possibly even longer. https://compilers.iecc.com/comparch/article/10-09-014 has some links to writeups

@zwol @soatok @autinerd

darn, 16 years later all the links are dead.

@RueNahcMohr @soatok @autinerd yikes, I've never seen dx.doi.org throw *that* error before

(i didn't try clicking any of the links earlier)

(i'll try to find the papers a little harder this evening)

@RueNahcMohr @soatok @autinerd One day the enshittification demons will come for Google Scholar, but that day is not yet.

https://www.acsel-lab.com/arithmetic/arith10/papers/ARITH10_Alverson.pdf

https://gmplib.org/~tege/divcnst-pldi94.pdf

And the Internet Archive does have the hackersdelight website from before it got turned into a ... French gossip newsmagazine? ... but the *website* doesn't really cover the subject. The book, though, does: https://bookshop.org/p/books/hacker-s-delight-henry-warren/67740eb69c0eb469?ean=9780321842688

@soatok @RueNahcMohr A long time ago in a simpler time, I was responsible for compiling my org’s copy of a common simulation program written in Fortran. I compiled with --02, and the build tests all failed.

Compiled with --O3 (a superset of O2 with unsafe optimizations) and suddenly everything was correct and the build tests all passed. I have a few users test with known-good benchmark values, and they are happy.

To this day I still have no idea what in the world was going on. It wasn’t even a weird compiler either, it was whatever the stable version of gfortran was at that time. Can confirm, compiler optimizations are black magic.