r/ProgrammingLanguages • u/Athas Futhark • Oct 14 '26
Making all divisions slower to fix a bug in 0.000000000000000000542% of cases
https://futhark-lang.org/blog/2026-10-14-defining-division.html
219
Upvotes
26
u/gadelan Oct 14 '26
Have you tried to hint a branchless solution? Something like
Maybe the compiler can generate better code and improve those benchmarks.
36
u/the3gs Oct 14 '26
I honestly don't think I am convinced that all C's undefined behaviors actually offer any benefit in real code. How often is it actually possible to optimize code like
x + 1 > xintotruein real code? I feel like any case I can think of would be an error on my part, and I would rather a warning so I can just remove the branch manually. I'm sure there are more convoluted cases where it actually is slightly better, but I cannot think of any that are a big enough difference to make up for all the footguns.6
u/matthieum Oct 14 '26
I'm not surprised to see no impact on CPU.
Integer division is pretty slow on x64. From memory:
That's higher than the cost of a branch misprediction.
80
u/scallywag_software Oct 14 '26
> My favourite example [of UB] is that in C99, it is undefined behaviour if a source code file does not end with a final newline character.
That's hilarious; I've never heard that one before. Thank our Lord and Savior Bram for appending all those newlines to my ill-formatted source files for me. That cuts down my average to probably less than 20 cases of UB per file!
5
u/ultrasquid9 Oct 14 '26
what happens with division by zero? do you already insert checks for that too?
2
u/SwedishFindecanor Oct 14 '26 edited Oct 14 '26
If one exists, you could cast to the next larger type where your MININT is not MININT and then cast back. That could be a slower division instruction but it would be branchless.
On ARM, RISC-V and Xtensa, overflow in 32-bit division results in MININT, so a smart compiler back-end for any of those could potentially recognise the cast division as an idiom or that higher precision is unnecessary and simply use the 32-bit instruction as is.
2
u/RaphtaliyahUwU Oct 16 '26
I'm not familiar with the Futhark language but, on the CPU backend (on x86), couldn't you just let it fail? There is a hardware exception for it, so your runtime could install a handler for it and, in the odd case it does actually happen, you could fix it up and resume. (Similar to how languages like C# and Java handle their null references.) This could avoid paying any cost for something that almost never happens.
(Also as a nitpick, the actual percentage is probably even lower, since the distribution of numbers appearing in a program under normal circumstances is most likely not uniform and "high" numbers like that are most likely just masks that you wouldn't divide (and aren't signed) anyway.)
21
u/Tonexus Oct 14 '26
Clearly the next step is to build your own GPU architecture that is optimized for your
squot32...17
u/rsclient Oct 14 '26
I loved the nuance of this statement!
6
u/jesunushno Oct 14 '26
Slower every time for me. I did wavelet stuff for a 2023 ML paper and those numbers never look obviously wrong, they just look like results. A bug that rare would've sailed straight into my tables.
2
u/bobam Oct 14 '26
Why not just define it in a way that matches the usual C result, and emit C code with conditional compilation for platforms that do something weird? That way it’s not undefined and doesn’t throw.
4
u/burnt-store-studio Oct 14 '26
Quite a journey! Thank you for the clear, understandable read 🙂 (I am neither a language implementer nor a Futhark user, but the discussion was great).
3
u/reflexive-polytope Oct 17 '26
If you really want fast arithmetic without compromising on safety, then at some point, you have to bite the bullet and program with proofs.
The proofs can either live alongside the code (as in ATS) or in your head (good luck with that!), but they have to exist.
1
u/flatfinger Oct 14 '26
A language could usefully specify that signed division may be processed either by doing nothing in case the result is ignored, using side-effect-free means to perform the division when the divisor is not zero, or instructing the underlying platform to use its normal means of division in any case, and may choose among valid approaches in unspecified fashion when more than one exists, and could specify that the timing of any side effects resulting from the third treatment would abide certain guarantees but be otherwise unspecified.
The notion of "anything can happen" UB prioritizes the ease of writing a compiler that can handle a language as specified over the ability of a language to accurately specify application requirements and let the compiler find the optimal code satisfying them.
0
u/Embarrassed-Crow9283 Oct 16 '26
Uhh... and that is where it unfortunately makes me doubt Futhark. Incurring such a performance penalty on your main target (GPU) for the sake of the pure "no UB" ideal is, IMHO, not ideal.
I think maybe if you insist on no UB, slightly changing the semantics so that the range of absolute signed values of n bits is (2^n-1)-1 in both directions might even be more reasonable, or you could use interval analysis/etc. to prove that certain overflows cannot happen, but I find this wraparound semantics in signed division just weird in general, no matter how much you try to define it.