Will a C/C++ compiler optimise code by reusing a recently calculated function result?

Question

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.

Which compiler? So long as the code produces the same result (and side-effects), the compiler can do what it pleases. — Weather Vane, Mar 28 '19 at 21:14
I'm not an expert on such things, but it seems to me it may depend on how `F()` is defined. Does it have side effects? Can it be inlined? — Fred Larson, Mar 28 '19 at 21:18
If you would like to know how compilers see your code, take a look at [Compiler Explorer](https://godbolt.org). [This](https://godbolt.org/z/6h9Idk) shows that `F` is called two times anyway. — ForceBru, Mar 28 '19 at 21:20
Aside from the interesting academic question of "will it be optimised?", may I suggest you don't write code that relies on the optimisation. If I'm doing code review, and I see an expensive function that looks like it's called more than necessary, that's a huge code smell. I don't want to think about the details of the compiler optimisations, I want to see code that is clear and clearly performant. Remember too, the person reviewing your code may be you in 6 months time. — JMAA, Mar 28 '19 at 21:24
write for readability. Only when you measured you can know if it is worth to compromise for efficiency, but to measure you need a running program first ;) — 463035818_is_not_an_ai, Mar 28 '19 at 21:26
Calling F only once is only valid if F is pure (no side effects), which the compiler cannot guess in this case since the definition of F is not visible. You can use the not-so-portable `__attribute__((pure))` to indicate this property. — Marc Glisse, Mar 28 '19 at 21:38

score 8 · Answer 1 · answered Mar 28 '19 at 21:27

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.

Re “I rate it unlikely…”: Apple LLVM 10.0.0 with clang-1000.11.45.5 optimizes `sum` to have a single call to `F` if it can see a definition of `F` it recognizes as pure. Even with a non-pure function (I used `++y; return sin(x) * log(x);`, where `y` was an external `int`), it generated code to evaluate the pure part once and the impure part (as if) twice. — Eric Postpischil, Mar 28 '19 at 23:16
@EricPostpischil, my estimation of likelihood is based on several things, among them a wild guess about how likely `F()`, whose evaluation is specified to be costly, is to in fact be pure or to be inlined. Your choice for an example `F()` is well outside the envelope of functions I have in mind, though I grant that costliness is a relative characteristic. — John Bollinger, Mar 29 '19 at 12:03

0xdd · Answer 2 · 2019-03-28T21:36:18.293

2

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++.

edited Mar 28 '19 at 21:36

answered Mar 28 '19 at 21:27

0xdd

311
3
15

2

The question does not describe memoization. Memoization is one technique that could speed up computation, possibly in the circumstances described in the question, but the question asks about reusing previously calculated results in general, not memoization. It is much more likely that a compiler might recognize that, in `sum`, `F(x)` is calculated both directly and within the call to `f(x)` and hence might generate code to evaluate `F(x)` only once and reuse the result. – Eric Postpischil Mar 28 '19 at 23:04
@EricPostpischil this is a good point; do you know any compilers that currently do this? – 0xdd Mar 29 '19 at 12:46
Do what, recognize that `F(x)` is evaluated twice? As noted in my comment on [John Bollinger’s answer](https://stackoverflow.com/a/55407087/298225), Clang does, and I expect other good quality compilers do too. – Eric Postpischil Mar 29 '19 at 14:04

Michael Veksler · Answer 3 · 2019-03-29T21:27:50.160

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

Will a C/C++ compiler optimise code by reusing a recently calculated function result?

3 Answers3