r/ProgrammingLanguages • u/Athas Futhark • 1d ago
Making all divisions slower to fix a bug in 0.000000000000000000542% of cases
https://futhark-lang.org/blog/2026-10-14-defining-division.html32
u/the3gs 1d ago
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 > x into true in 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.
22
u/Athas Futhark 1d ago edited 1d ago
I know for sure that if you take standard loopy code and replace all the loop counters and index arithmetic with unsigned integers, then performance decreases. I know that because we had to put a lot of effort into making sure that the index arithmetic generated by the Futhark compiler is done with signed numbers, despite using unsigned numbers for arithmetic that comes from user code. I did not look closely into exactly what happens, but if I had to guess, I expect it may be related to unrolling or vectorising loads. E.g., if you load
x[i],x[i+1],x[i+2],x[i+3], then the compiler may assume that these are physically adjacent, and not some overflow edge case.11
u/xeow 1d ago
This whole talk is amazing, but especially this part is relevant:
2
2
u/EggplantExtra4946 17h ago
That's an idiotic lesson.
Signed integers are not magic, if you force the compiler to wrap with -fwrapv it will also produce the longer code with int32_t.
You can get the compiler to generate the short code by replacing uint32_t by either uint64_t or size_t and it will do so because that's the correct semantics, not because it is making things up.
14
u/lookmeat 1d ago
It's not about offering benefit, it's about admitting a reality. In C there's three solutions. One in unspecified, which is "it doesn't matter" and can be whatever an implementation finds reasonable and it can even switch it halfway. Implementation Defined means that the implementation needs to specify an answer, but each one gets to choose theirs.
All of this matters for the purpose of optimizing because the goal is to preserve behavior. UB is meant to be the "lets admit that weird things can happen here" and that programmers do.
How often is it actually possible to optimize code like x + 1 > x into true in real code?
I mean that's setting up a strawman. You write a lot of
x++and you can do checks on it, or even more a lot of code just assumes that the above is true. Whenever you writefor(int i = 0; i < target; ++i)you are almost always assuming the above. If we unroll the loop it assumes the above almost certainly. Maybe your code doesn't, but the optimizer does expect that its true.It's not that you can't standardize this down, but it comes at a performance hit, which is what this article was all about. Int most code that we write, we can guarantee we won't hit the edge case.
6
u/the3gs 23h ago
I wouldn't say I was "setting up a strawman" as I mostly used the
x+1>xexample because it was mentioned in the article.Would you mind offering more detail on where the loop unrolling assumes it? I'm struggling to think of the requirements of loop unrolling being added, as I am not very experienced in implementing optimizations.
5
u/lookmeat 21h ago
I was "setting up a strawman"
I understand that it wasn't your intent, but it deserved to be called out:
How often is it actually possible to optimize code like x + 1 > x into true in real code? I feel like any case I can think of would be an error on my part
You basically are stating that this scenario only happens when you explicitly write the conditional, which is not how this often is found. That's the strawman, it may have been unintentional, but the fallacy is there. Compilers need to answer the question above not because the programmer explicitly wrote the code.
Would you mind offering more detail on where the loop unrolling assumes it?
Take, for example, vectorization. I see something like this:
char arr[ARR_LEN]; fill_in_string(&arr); for(int i = 0; i < ARR_LEN; i++) { arr[i] += 5; }Now say that I want to optimize the loop and unroll it so I can vectorize it:
char arr[ARR_LEN]; fill_in_string(&arr); uint8_t all5[8] = [5, 5, 5, 5, 5, 5, 5, 5] for(int64_t *i = &arr; i < &arr + ARR_LEN - 8; i++) { *i = _mm_add_pi8(*i, all5); }Now the code above is a bit sloppy (I feel pretty confident it wouldn't compile), but I hope that the goal here is to understand what I want to do. Instead of modifying 1 byte at the time, I'd like to modify 8 bytes at the time using really fast 64-bit registers.
Now I want an optimizer to do this, but I need to be 100% that I have not broken the code by changing it. What things other than the code above should be true in order for the above kind of transformation to work? Lets list it:
arrneeds to be offset correctly in memory for the speed up to be worth it, something on 64-bits.ARR_LENneeds to be a multiple of 8.- Also for all
iabove it should be thati < i++I mean it should be clear why if there's an overflow the behavior changes. But then this makes it really hard to do a lot of very reasonable optimizations. Inevitably you hit gnarly variants of the Halting-Problem which means you just can't know. That is what if instead of
i++I havefoo(&i)?So we declare this undefined behavior. We say: if you programmer do this thing your code isn't guaranteed to work in any way you expect it to. Then we can just assume that the third point is always true. We can trust that a programmer can write code that they can answer confidently that UB doesn't happen, and if they can't know if that is true or not, this tells the programmer they have no idea if their code works or not at all. Best of all, if a programmer knows, they don't need to encode it in a way that the compiler understands (which is its own problem) instead they just let the compiler work. Basically the UB is the way of the C standard saying "we are going to trust the programmer here".
I chose an example using vectorization because this is a common thing, but I can also think of various scenarios where the compiler may realize it can unroll a loop into a loop that does 4 steps, but that presumes that the memory addresses we are looping through are contiguous, which implies we need to be certain that
x < x + 1.2
u/SLiV9 Penne 10h ago
Inevitably you hit gnarly variants of the Halting-Problem which means you just can't know. That is what if instead of i++ I have foo(&i)?
Not OP but I think that's a little unfair. If it's not i++ but foo(&i) then there is no UB / no assumption that foo(&i) > i, and gcc and clang aren't be able to autovectorize.
One in unspecified, which is "it doesn't matter" and can be whatever an implementation finds reasonable and it can even switch it halfway. Implementation Defined means that the implementation needs to specify an answer, but each one gets to choose theirs.
If it was unspecified behavior, compilers would be able to transform the for loop you showed by prepending it with
assert i < MAXINT - arraylength(arr)
In fact that is what you need to do in Rust to get llvm to autovectorize the loop. In 1990 this kind of optimization (in general cases) was way beyond the scope compilers, but in 2026 a compiler could do this if the language had ample unspecified-but-not-undefined behavior (so not C and not Rust)
1
u/flatfinger 21h ago
There's another solution, which is what the language used to do be understood as doing: treat an implementation's job not as executing programs, but rather as translating programs into a sequence of imperatives for the execution environment. In some cases, compilers for platforms that process certain imperatives strangely may be required to wrap them in logic to mimic the behavior of more conventional implementations, and in others compilers would be allowed to expose any underlying strangeness to the programmer.
Suppose that some platform used a 16-bit short and 32-bit int, and its only multiply instruction would multiply two 32-bit singed numbers and trap on overflow A compiler given
uint1=(unsigned)ushort1*(unsigned)ushort2;would be required to do something likeuint1=ushort1*(ushort2 & 0xFF) + ((unsigned)(ushort1*(ushort2>>8))<<8);but a compiler givenuint1=ushort1*ushort2;could simply tell the execution environment to apply its normal way of multiplying two int values to ushort1 and ushort2, with whatever consequences would result.3
u/lookmeat 21h ago
There's another solution, which is what the language used to do be understood as doing: treat an implementation's job not as executing programs, but rather as translating programs into a sequence of imperatives for the execution environment.
That is not the solution, that is the problem!
Java avoids UB by creating an actual interpreter, the JVM, and targeting that specifically.
C instead translates to machine code. The problem is that we don't know which machine, and defining the assembly for each machine means compilers can't evolve. C is the king in its space people kept making better compilers on a pace other languages couldn't match.
So rather than defining the implementation, C just defines what the machine should do. But again, without knowing which machine we can't be 100% what that implication would have on it. So what we do is we define an abstract concept of a machine, the C VM, and then we define how it behaves when running the assembly generated by the compiler, all other machines should behave as the VM does.
And this enables a lot of power. Because a machine that works iterating through an array, or one that applies MMU vector operations on it can both still do the same thing, an optimizer can change the assembly in ways that are still identical in behavior. This is how optimizations work.
Except that it's hard to define the VM in a way that is convenient. Sometimes machines work very different from one another, and then this makes it hard. We can say that machines can do whatever they want in these case, but sometimes this makes it impossible to know how your code will work, not just in your machine but after optimizations. So instead sometimes we say "let the platform decide what the answer should be here" and then optimizers can stick to that answer and developers can reason within their platform. But sometimes that's impossible, it requires breaking things, or defining things, or making some code just really bad always, and the point of C is that programmers should have a choice.
So instead we say to programmers: if you do this thing, it will shoot you. We allow
while(true) {}but programmers should be aware that their program will freeze and never exit. So we say "the programmer should ensure their program never does something dumb, and we can assume that's always the case or do whatever we want otherwise".Suppose that some platform used a 16-bit short and 32-bit int, and
This is mostly how it works. The compiler assumes tries to just generate the assembly. But this means that certain behavior will just do "the wrong thing", what that wrong thing is depends not just on your platform, but optimizations and quirks and what not. So it was just called "Undefined Behavior". What happens when you multiply
255*255and both areushort? Who knows, the compiler can do whatever it wants, maybe it saturates at255, maybe it rolls over (btw in your machine, even if default behavior is saturation, because it's upgrading the 16-bit shorts to 32 bits, if you downgrade back it it'd be a rollover).UB is just way that the compiler says:
with whatever consequences would result.
0
u/flatfinger 20h ago
C was designed to allow programs to take advantage of machine-specific features but run interchangeably on implementations whose target platforms shared those features.
Except that it's hard to define the VM in a way that is convenient.
Not really. One could write a language specification which would be practical for most platforms, and would eliminate all but two forms of language-level UB:
Any action which would cause the target environment to behave in a manner contrary to an implementation's documented requirements.
Any action which would disturb the contents of storage that an implementation has reserved from the environment, and that does not have defined C language semantics.
Everything else would be at worst an Unspecified choice from among a small number of possibilities including "Use one of the platform's native means of doing X, if it has one", or "Trap via documented means, if a means is documented".
An implementation's choice of if and how it decides to store automatic-duration objects whose address is not observed would not be considered observable, and nor would its choice of how to use storage which it has reserved for arbitrary use from the environment but which does not form part of any live object or allocation with an observable address.
There are many interchangeable ways one could define an intermediate language such that a universal compiler could translate a source file into intermediate language without having to know anything about the target except for some parameters related to integer sizes and alignment, storage layouts, etc., and regardless of the intermediate language any translation of the intermediate language which treats its imperatives as independent, and doesn't go out of its way to be weird, would have semantics compatible with any other, even when processing machine-specific code.
C was designed to be usable as a form of portable high-level assembler; and the world has a need for such a language. The charter for the C Standards Committee used to acknowledge that, even though the Committee refused to have the Standard do so, until finally the Committee finally decided to formally abandon the purposes for which C had been invented.
4
u/ccapitalK 14h ago
I think can think of a relatively trivial example of UB helping optimise real world programs. Say you have the structs foo and bar, of types Foo pointer and Bar pointer respectively. You have a lot of branches in your function that reads a specific value from foo, and set other variables based on that value. One code path sets a value inside bar conditioned on that value from foo.
Without strict aliasing being UB, any compiler trying to emit correct code would need to handle the case where foo and bar reference overlapping ranges, since it's possible that a user could pass in pointer values where the value in foo overlaps the modified value in bar, meaning that the value would need to be reloaded into the register. If you don't forbid this, you would need to add extra loads or runtime checks on every such access to detect this, since pointer overlap can't be checked statically in C.
1
u/gadelan 1d ago
In this case is unavoidable. For instance, the x86 ISA family traps in integer division overflow.
Overflow is indicated with the #DE (divide error) exception rather than with the CF flag.
It's not just we want some properties like `x + 1 > x`. It's the CPU misbehaving.
1
u/celestabesta 1d ago
For one, cases like that might be possible in more generic code. Thats much less likely in C but much more likely in C++.
Second, cases of possible UB might not matter on their own. A single variable that experiences multiple arithmetic operations could however allow the compiler to narrow its possible values down much more, which can allow it to do slightly more optimised arithmetic later. There are tricks where compilers can turn division or multiplications into weird combinations of addition, subtraction, and bitshifts. Those might be easier to do if the compiler can know the value might never be less than 7 or greater than 9274 or something.
1
u/tstanisl 1d ago
In code, rarely. But inequalities like this one happen a lot during analysis of loops and aliasing.
1
u/needleful 23h ago
I assume it's used as an intermediate step in constant folding, where some condition is eventually optimized down to
(number definitely greater than x) > x, and it would be a speed boost to optimize it away, since the overflow would be rare and probably a bug.1
u/PandaWonder01 14h ago
This is a minimal reproducible example. But the fact is, that many, many larger statements can boil down to an expression similar to x+1>x. After many optimization passes, it may get down to something like that expression. As a compiler, you can either choose to force the check every time, slowing down a vast majority of programs(doing that check may prevent further optimizations!), or just say "integer overflow does not have defined behavior", and leave it there.
0
u/SelfDistinction 22h ago
Surprisingly often. After all, every optimisation we have ever done is a variant of replacing X+1>X with true.
8
u/rsclient 20h ago
I loved the nuance of this statement!
Futhark is a principled language, and therefore producing undefined behaviour is unacceptable. (I realise the hypocrisy of this puritan declaration whilst leaving in the bug for ten years.) Further, on x86 this kind of division will actually signal a CPU exception, crashing the program, so this is not merely a violation of the sanctity of the C specification.
3
u/ultrasquid9 1d ago
what happens with division by zero? do you already insert checks for that too?
3
u/Athas Futhark 1d ago
Yes, that is handled with a dynamic safety check before the division operation is even performed. The design for that is discussed here.
3
u/matthieum 23h ago
I'm not surprised to see no impact on CPU.
Integer division is pretty slow on x64. From memory:
- 32 bits: up to ~30 cycles.
- 64 bits: up to ~90 cycles.
That's higher than the cost of a branch misprediction.
3
u/scallywag_software 23h ago
Huh .. I was highly sus on this claim because FP divide is so much faster. Your memory is correct. TIL
2
u/Athas Futhark 23h ago
Division and multiplication is fairly easy in floating point because of the exponent-based representation.
3
u/Consistent_Bee3478 21h ago
Well one should assume floaty maths on accounts of being inherently “approximated” would win out to algebraically accurate integer maths as far as instructions needed after a few bits of length have been reached. Especially on something like what used to be called a maths co processor. Or well cuda or whatever. Whole things supposed to only do floaty approximations in parallel, and qsv and the likes are in every CPU as well. So on virtually any modern hardware you got parts that exist solely for rapid parallel fp stuff while integer maths is part of the more general instruction set. So when you try to do longer than 16 bit or so int maths it’s getting to be multiple instructions
2
u/Athas Futhark 23h ago
Based on CUDA's instruction throughput table, integer division is not even a single instruction, but "but up to 20" (unspecified which).
2
u/CatIsFluffy 9h ago
These results are correct for Skylake-era (2015~2019) Intel CPUs. Modern Intel CPUs are much faster (11-16 cycles for 32-bit division and 16-19 for 64 on P-cores, up to ~50% more for E-cores).
1
1
u/amarao_san 22h ago
Only non-pipelined. If operation is in pipeline, it's about 2 ticks.
2
u/CatIsFluffy 8h ago
AFAIK the only CPU cores that can process either of those kinds of division every other cycle are Apple's big cores. No CPU uops.info tracks is able to do integer divisions faster than once every 4 cycles (or every 5 if you don't count 8-bit division).
3
u/amarao_san 8h ago
I have an old ryzen 5900, I don't remember, at home.
I played with it (at the moment of purchase it was a shiny new beast with 4+GHz CPUs), and one of my benchmarks is relation rendering (you grab an equation and render it by probing value at each pixel of the screen, draw black dot if it's 0).
When I played with it, I found, that it's faster to re-calculate function for each pixel, than to check if pixel is already black. This 'if' caused branch misdirect, and doing pipelined 'same formula for each pixel in array' is faster, than skipping most of it. It was 2 ticks per division, pipelined (so, 500ps per division, 12 billions per second on 6 cores).
... But it was float division.
My bad. I never tested for ints (because I assumed ints are faster than floats).
1
u/matthieum 6m ago
I don't think there's any good reason for int division to be slower than float -- I mean, apart from float mantissa being shorter, bit-wise.
My understanding has always been that divisions are common operations on floats, and therefore hardware has been optimized to handle float divisions fast (with more silicon), whereas integer divisions are not very common, and therefore (until recently, apparently) it just wasn't a big focus for hardware so they got the slow path.
3
u/burnt-store-studio 22h ago
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/jesunushno 23h ago
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.
1
u/SwedishFindecanor 22h ago edited 21h ago
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.
1
u/Athas Futhark 21h ago
For 8-bit and 16-bit integers, this is likely a good idea, because these are likely not implemented in hardware anyway. For 32-bit, I'm less sure, as 64-bit integer arithmetic is significantly slower than 32-bit integers on some hardware, and division is generally the slowest integer operation.
1
u/flatfinger 20h ago
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.
51
u/scallywag_software 23h ago
> 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!