[sillycross]

> Amazingly, we find that the GCC compilers is able to compile Travis’ is_empty C++ function to constant-time code.

It's actually an interesting example where undefined behavior allowed compiler optimization:

(1) dereferencing an invalid pointer is UD

(2) signed integer overflow is UD.

This allows the compiler to assume that the program never crashes and the counter never overflows. The loop is then optimized out knowing that it is read-only thus has no side-effects.

[Noughmad]

> It's actually an interesting example where undefined behavior allowed compiler optimization

That is literally reason why any behavior is considered undefined. So that the compiler can skip checks to produce better optimized code.

[saagarjha]

Actually, many instances of undefined behavior are born out of a desire for portability. Some processors will fault on both of those and the standard wants to be inclusive of those behaviors. Compilers happen to be able to use the definition of undefined behavior to also optimize code, but the concept is born out of practicality.

[secondcoming]

And so you get an optimal, but broken, program. This helps nobody.

[ehvatum]

It helps everyone whose input does not cause undefined behavior.

[leetcrew]

in most cases a program that invokes undefined behavior is already broken; it's just a question of how catastrophic the failure will be.

[joosters]

Maybe I'm splitting hairs, but it's not specifically the presence of 'undefined behavior' that allows the compiler optimization. Instead, it's the language specification. The C spec says that integers cannot be relied upon to overflow. The result of this is that compilers are then free to assume that the program they are compiling has NO undefined behavior in it, and so the optimization is possible.

EDIT: To make it clearer, you could imagine an alternate version of C that aborted the program if an integer overflowed. Then there would be no undefined behavior at all - but the optimization is still possible. It's not the UB that helps us here, it's the language spec telling us what behavior is reliable and what is not.

[IshKebab]

> To make it clearer, you could imagine an alternate version of C that aborted the program if an integer overflowed. Then there would be no undefined behavior at all - but the optimization is still possible.

The optimisation wouldn't be possible in that case because then the program wouldn't abort when the integer overflowed. It would break the defined behaviour that overflow=abort.

[caf]

This is correct. In the motivating example, it would have to scan the entire list of pointers to see whether it finds a NULL link before it overflows the size counter or not.

[joosters]

Ah, you're completely right, the compiler couldn't hid or assume away the aborts as they would now be part of the spec.

[minitech]

> Then there would be no undefined behavior at all - but the optimization is still possible.

But then an optimization could change the defined behavior of aborting to not aborting, which is essentially what undefined behavior means and really bad if you don’t treat it exactly like undefined behavior.

[adrian_b]

You need not imagine an alternate version of C, such a version of C is provided by any decent C compiler.

For example, with gcc you can use either the option "-ftrapv" or the better option "-fsanitize=undefined -fsanitize-undefined-trap-on-error" and the program will abort on integer overflows (with the second option it will also abort for many other error conditions, e.g. access out of bounds).

[bregma]

> You need not imagine an alternate version of C, such a version of C is provided by any decent C compiler.

Classic misunderstanding of undefined behaviour. In this case it's still undefined behaviour, but the vendor has said "this is what my compiler will do with this particular undefined behaviour under these circumstances". Vendors are allowed to do anything they want when code containing undefined behaviour is submitted to their compiler, including doing something you might consider sane.

[adrian_b]

I agree that leaving such important behavior as undefined is a failure for a programming language standard, because the standard fails to guarantee that a program will do the right things independently of what compiler has been used and with what compiler options.

Nevertheless, in such cases it is the responsibility of the programmer to either write programs in which it is guaranteed that events for which the program behavior is undefined will never happen or to choose compiler options to handle such events.

If the programmers do their job right, then the compiler is free to optimize like when the undefined cases do not exist.

Unlike the case with integer overflow, there are cases where the programming language standards correctly leave some behavior as undefined, e.g. the order of evaluation for function arguments. For that kind of undefined behavior the programmer must take care to write only programs whose effects do not depend on it.

Data dependent events like integer overflow cannot always be avoided, so compilers must have options to generate exceptions when they happen.

[tialaramex]

> Data dependent events like integer overflow cannot always be avoided, so compilers must have options to generate exceptions when they happen.

This is a language choice. A better language can ensure that "data dependent events like integer overflow" are in fact avoided entirely. C and C++ chose not to do this.

I'm certain you'll disregard evidence from any languages that don't have similar performance characteristics to C or C++, so let's focus on two that do.

In Rust, the arithmetic operations that can result in overflow are supplied in typically four varieties. Checked operations, which produce an Option that is either Some(answer) or None if they would overflow, Overflow operations which produce a pair (answer,overflow?) where the boolean overflow? tells us whether an overflow occurred, Saturating operations, which produce an answer that's either correct or, if it overflows, saturated at the boundary crossed and finally Wrapping operations, which produce the answer with a wrapping number line.

In WUFFS the programmer is responsible for ensuring that their arithmetic operations cannot overflow. If you try to add two arbitrary 16-bit integers together in WUFFS the compiler will complain that it can't see why this is safe as they might overflow. Only once the programmer has excluded this case (e.g. if either integer is larger than 999 or smaller than -999 the function reports this as an error and doesn't add them together) can they add the integers together, since now there can't be an overflow.

[umanwizard]

The behavior is defined, but by the compiler documentation, not the language standard. Different documents can define different things.

[joosters]

Saying 'this is what I will do when an int can't hold the assigned value' is defining the behavior, ergo it is no longer undefined!

Vendors are allowed to do anything they want when code containing undefined behaviour is submitted to their compiler

Yes, and his compiler is saying that it will trap these events. Are you suggesting that the compiler will secretly ignore this setting and then go on to do all kinds of insane things?

[bregma]

> Saying 'this is what I will do when an int can't hold the assigned value' is defining the behavior, ergo it is no longer undefined!

Defining the behaviour of a particular compiler under specific circumstances does not equate to defining the behaviour of the C language.

[joosters]

You are reading words that nobody wrote. No-one claimed that they were redefining the ‘C spec’ by passing flags to their compiler - the standards board’s job is still safe!

[joosters]

Sure, but I understand why the C spec does not define this - because not all processors can trap these events, at all times and in all situations, without added costs. And C is very much of the opinion that it doesn't want added costs - but it lets you pick and choose what you want, hence the compiler options.

I don't think there's an obvious 'good' and 'bad' choice here.

[admax88qqq]

I think the "good" choice is to remove undefined behaviour and accept that C will be slighlty slower on esoteric hardware.

[saagarjha]

This will make C much slower on your hardware, too.

[em3rgent0rdr]

I suppose it is a safe assumption that the counter will never overlow if memory space is not large enough to possibly hold the maximum positive integer number of data structs. Though if say was using a smaller int for size than what the hypothetical size that virtual memory could handle, such as a short int in a 32-bit memory system, then that assumption may not be true. But on a 64-bit linux system which only allows up to 128 TiB of virtual address space for individual processes, a 64-bit signed int could be as large as 2^63, which would be larger than the hypothetical maximum size that a 128 TiB virtual memory could reference, so the assumption that the size counter could never overflow would be safe.