Styjun

Suppose I have a function double F(double x) and let's assume for the sake of this example that calls to F are costly.

Suppose I write a function f that calculates the square root of F:

double f(double x)
 return sqrt(F(x));

and in a third function sum I calculate the sum of f and F:

double sum(double x)
 return F(x) + f(x);

Since I want to minimise calls to F the above code is inefficient compared to e.g.

double sum_2(double x)
 double y = F(x);
 return y + sqrt(y);

But since I am lazy, or stupid, or want to make my code as clear as possible, I opted for the first definition instead.

Would a C/C++ compiler optimise my code anyway by realizing that the value of F(x) can be reused to calculate f(x), as it is done in sum_2?

Many thanks.

Would a C/C++ compiler optimise my code anyway by realizing that the value of F(x) can be reused to calculate f(x), as it is done in sum_2?

Maybe. Neither language requires such an optimization, and whether they allow it depends on details of the implementation of F(). Generally speaking, different compilers behave differently with respect to this sort of thing.

It is entirely plausible that a compiler would inline function f() into function sum(), which would give it the opportunity to recognize that there are two calls to F(x) contributing to the same result. In that case, if F() has no side effects then it is conceivable that the compiler would emit only a single call to F(), reusing the result.

Particular implementations may have extensions that can be employed to help the compiler come to such a conclusion. Without such an extension being applied to the problem, however, I rate it unlikely that a compiler would emit code that performs just one call to F() and reuses the result.

What you're describing is called memoization, a form of (usually) run-time caching. While it's possible for this to be implemented in compilers, it's most often not performed in C compilers.

C++ does have a clever workaround for this, using the STL, detailed at this blog post from a few years ago; there's also a slightly more recent SO answer here. It's worth noting that with this approach, the compiler isn't "smartly" inferring that a function's multiple identical results will be reused, but the effect is largely the same.

Some languages, like Haskell, do feature baked-in support for compile-time memoization, but the compiler architecture is fairly different from Clang or GCC/G++.

Many compilers use hints to figure out if a result of a previous function call may be reused. A classical example is:

for (int i=0; i < strlen(str); i++)

Without optimizing this, the complexity of this loop is at least O(n²), but after optimization it can be O(n).

The hints that gcc, clang, and many others can take are __attribute__((pure)) and __attribute__((const)) which are described here. For example, GNU strlen is declared as a pure function.

GCC can detect pure functions, and suggest the programmer which functions should be married pure. In fact, it does that automatically for the following simplistic example:

unsigned my_strlen(const char* str) 

 int i=0;
 while (str[i])
 ++i;
 return i;
 

unsigned word_len(const char *str)

 for (unsigned i=0 ; i < my_strlen(str); ++i) 
 if (str[i] == ' ')
 return i;
 
 return my_strlen(str);

You can see the compilation result for gcc with -O3 -fno-inline. It calls my_strlen(str) only once in the whole word_len function. Clang 7.0.0 does not seem to perform this optimization.

word_len:
 mov rcx, rdi
 call my_strlen ; <-- this is the only call (outside any loop)
 test eax, eax
 je .L7
 xor edx, edx
 cmp BYTE PTR [rcx], 32
 lea rdi, [rdi+1]
 jne .L11
 jmp .L19
.L12:
 add rdi, 1
 cmp BYTE PTR [rdi-1], 32
 je .L9
.L11:
 add edx, 1
 cmp eax, edx
 jne .L12
.L7:
 ret
.L19:
 xor edx, edx
.L9:
 mov eax, edx
 ret