Does undefined behavior really help modern compile

Question

Aren't modern compilers smart enough to be able to generate a code that is fast and safe at the same time?

Look at the code below:

std::vector<int> a(100);
for (int i = 0; i < 50; i++)
    { a.at(i) = i; }
...

It's obvious that the out of range error will never happen here, and a smart compiler can generate the next code:

std::vector<int> a(100);
for (int i = 0; i < 50; i++)
    { a[i] = i; } // operator[] doesn't check for out of range
...

Now let's check this code:

std::vector<int> a(unknown_function());
for (int i = 0; i < 50; i++)
    { a.at(i) = i; }
...

It can be changed to such equivalent:

std::vector<int> a(unknown_function());
size_t __loop_limit = std::min(a.size(), 50);
for (int i = 0; i < __loop_limit; i++)
    { a[i] = i; }
if (50 > a.size())
    { throw std::out_of_range("oor"); }
...

Also, we know that the int type doesn't have side effects in its destructor and assignment operator. So we can translate the code to the next equivalent:

size_t __tmp = unknown_function();
if (50 > __tmp)
    { throw std::out_of_range("oor"); }
std::vector<int> a(__tmp);
for (int i = 0; i < 50; i++)
    { a[i] = i; }
...

(I'm not sure that such optimization is allowed by C++ standard, because it excludes memory allocation/deallocation steps, but let's think of C++-like language that allows this optimization.)

And, OK, this optimization is not as fast as the next code:

std::vector<int> a(unknown_function());
for (int i = 0; i < 50; i++)
    { a[i] = i; }

because there is an additional check if (50 > __tmp) which you really don't need if you are certainly sure that unknown_function never returns a value that is less than 50. But the performance improvement is not very high in this case.

Please note that my question is little different than this question: Is undefined behavior worth it? That question is: do advantages of performance improvements outweigh shortcomings of undefined behavior. It assumes that undefined behavior really helps to optimize a code. My question is: is it possible to achieve almost the same (maybe little less) level of optimization in a language without undefined behavior as in a language with undefined behavior.

The only case I can think of where undefined behavior can really help improve performance significantly is manual memory management. You never know if the address a pointer points to is not freed. Someone can have a copy of the pointer than call free on it. Your pointer still point to the same address. To avoid this undefined behavior you either have to use a garbage collector (which has its own disadvantages) or have to maintain a list of all pointers that point to the address, and when the address is freed you have to nullify all those pointers (and check them for null before accessing them).

Providing defined behavior for multi-threaded environment may probably cause performance costs too.

PS I am not sure that a defined behavior may be achieved in C-like language, but added it to the tags too.

Answer 1

For the first example it is NOT obvious it will go out of range, to the compiler; the at() function is a black box and may well add 200 to i before trying to access the vector array. That would be silly, but sometimes programmers are silly. It looks obvious because you're aware that template doesn't do that. If the at() is declared inline then a later peephole optimization stage may do that sort of bounds check skipping, but that's because the function is an opened box at that point so it has access to the vector bounds and that the loop only involves constants.

Answer 2

Your example is just an example. In your example, the performance gain of using operator[] instead of at may be small, but there are so many other cases where the performance gain brought by undefined behavior may be huge.

For example, just consider the following code

std::vector<int> a(100);
std::vector<int>::size_type index;
for (int i = 0; i != 100; ++i) {
    std::cin >> index;
    a.at(index) = i;
}

For this code, the compiler has to check the bound in each iteration, which may be a considerable cost.

Answer 3

My question is: is it possible to achieve almost the same (maybe little less) level of optimization in a language without undefined behavior as in a language with undefined behavior.

Yes, by using a type-safe language. Languages such as C and C++ need the concept of undefined behavior precisely because they are not type-safe (which basically means any pointer can point anywhere and anytime), and therefore in way to many cases, the compiler cannot statically prove that no violations of the language specification can occur in any execution of the program, even when that is actually the case. That's because of the hard limitations in pointer analysis. Without undefined behavior, the compiler has to insert too many dynamic checks, most of which are not really needed, but the compiler cannot figure that out.

Consider, for example, safe C# code where a function accepts a pointer to an object of some type (an array). Because of the way the language and the underlying virtual machine are designed, it's guaranteed that the pointer points to the object of the expected type. This is ensured statically. The code emitted by C# still requires bounds and types dynamic checks in certain cases, but compared to C/C++, the number of dynamic checks that would be required to implement fully defined behavior is tiny and typically affordable. Many C# programs can achieve the same as or slightly less than the performance of the corresponding C++ programs. Although that highly depends on how there are compiled.

The only case I can think of where undefined behavior can really help improve performance significantly is manual memory management.

That's not the only case as explained above.

Providing defined behavior for multi-threaded environment may probably cause performance costs too.

Not sure what you mean here. The memory models specified by the language define the behavior of multi-threaded programs. These models can range from very relaxed to very strict (see the C++ memory models for example).

Answer 4

In many cases, optimal code generation will require some constructs via which programmers can invite compilers to assume certain things, with unpredictable consequences if they turn out not to be true. Further, in some cases the most efficient way to perform a task would not be verifiable. If all arrays are marked with length, however, there would be no need to have a language treat out-of-bounds array accesses invoke UB [rather than trapping] if the language had a construct, e.g.

UNCHECKED_ASSUME(x < Arr.length);
Arr[x] += 23;

then it could check array bounds by default without losing the optimizations that would be available using unchecked accesses. To allow for the many cases where it would be necessary to ensure that a program would get shut down before doing anything "bad", but the exact timing of such shutdown wouldn't matter, a language could include a CHECKED_ASSUME assumption, such that given e.g.

CHECKED_ASSUME(x < Arr.length);
Arr[x] += 23;

a compiler would be allowed to fatally trap at any time it could determine that the code would be invoked with x>Arr.length or hit some other fatal trap first. If the above code were to appear within a loop, using a CHECKED_ASSUME rather than an ASSERT would invite a compiler to move the check out of the loop.

While maintainers of C compilers insist that unconstrained UB is necessary for optimization, that would not be true in a well-designed language outside of some narrow circumstances.