Integer addition is not associative, or should we put constants to the right?

Explain
1

An example in the release notes on Operator Precedence with a lot of parentheses inspired me to check whether I know all the side effects of the defined order of operations.

One of the quirks of the integer overflow UB I had not realized before is that, since it is observed by the compiler operation-wise, this UB (and the transformations the compiler does because of it) is sensitive to the order in which arithmetic is performed. In particular, I would argue that, in the status quo, omitting parentheses in a chain of additions has implicit control flow.

Take a look at this example, keeping in mind that addition is left-associative. In the compare_good function, both a + b and c + d are evaluated first, so the compiler sees the guarantee that they fit into i32. In compare_bad, a - 10 and c - 10 are evaluated first, so there is no such guarantee, and removing -10 might cause an extra overflow on either side of the less operator. Even the explicit evaluation (and assertion) in compare_ugly cannot resurrect the optimization since dead code elimination stole this information way earlier.

Unfortunately, the compilers relying on SSO have to do operation-wise UB, and not make just the results of the whole associative operation UB on overflow. Nonetheless, the optimizations would be more consistent if only the final result were checked (or assumed). For now, we might want to just put our constants at the very right in arithmetic for better optimizations sometimes.

What do you think about this?

2

Firstly, Zig does not have a concept of “UB” in the way that C and C++ do. Zig has “illegal behavior”.

Secondly, you’ve misinterpreted what the Godbolt output is telling you. What you are actually seeing is that in the “compare_good” function, the compiler is able to see the optimization that x < y and x - 10 < y - 10 are the same comparison, if it ignores overflow, while it misses that optimization in the compare_bad function. Please note that “missing an optimization” is very different from the claim “integer addition is not associative”.

Of course, you are right to call out that the comparison x - 10 < y - 10 has an edge case where the computation underflows. The compiler is empowered to ignore this edge case because 1) you wrote + and - and not one of Zig’s other operators like +| or +%, and 2) you compiled in -Ofast, which turns underflow/overflow checks into assumptions that the compiler may use to optimize.

2 Likes
3

I’m not fond of having having more than 2-3 variables in a line.

Much better

Now that the red mist has cleared…

Can’t say I’m too surprised. Optimising compilers are a bit of a dark art, best not rely on them too much. Thankfully it’s only a few instructions, so you’re not losing too much. If my program is running slowly, there are much better places to start than trying to enable micro-optimisations at this level.

I guess it could elide a function call in some circumstances, assuming the function (1) computed a value and (2) had no side effects. I’d be hard pressed to think of an example, though. One that wasn’t just bad code in some other way.

While I was rewriting the code in godbolt, I found some instances of the same code compiling into different instructions when I changed the name of the function, or it’s position in the file.

Example

This compiles into

        lea     eax, [rdi + rsi - 10]
        lea     ecx, [rdx + rcx - 10]
        cmp     eax, ecx
        setl    al
        ret

but this compiles into

        lea     eax, [rdi + rsi]
        add     eax, -10
        add     ecx, edx
        add     ecx, -10
        cmp     eax, ecx
        setl    al
        ret

Maybe it’s able to optimise more when compiling alongside other, similar functions… and then it keeps the result in the cache… I can only speculate.

“Unchecked Illegal Behaviour” has identical semantics to C’s “the behavior is undefined”.

Different name, same pit of angry venomous snakes.

4

That is true but note that the list of unchecked illegal behaviour is much smaller than the one of undefined behavior. At least for safe release modes.

AFAIK it’s just @fieldParentPtr, return of pointer to the call frame and wrong assembly clobbers.

That is much better than other languages. And I think one could find a way to make them safety checked swell.

5

Agreed, it is much better, especially in debug or safe mode.

My point is more around wording; Zig has ‘undefined behaviour’ in all but name, and saying it doesn’t will only confuse people.

There is also the existing literature on the topic of undefined behaviour, and the weird and wacky behaviour it can cause. It can help encourage people to stay in safe modes.

6

ah, i guess i should have been more explicit: I called it out bc the mention of “UB” and odd conclusions made by the post had me suspecting we caught the tail end of an LLM folie à deux, but i didn’t say as much :slight_smile: