Is there optimization for constant function return value inside a loop?

Question

My question is specifically about the gcc compiler.

Often, inside a loop, I have to use a value returned by a function that is constant during the whole loop.

I would like to know if it's better to prior store this constant return value inside a variable (let's imagine a long loop), or if a compiler like gcc is able to perform some optimizations to cache the constant value, because it would recognize it as constant threw the loop.

For example when I loop over chars in a string, I often write something like that:

bool find_something(string s, char something)
{
    size_t sz = s.size();
    for (size_t i = 0; i != sz; i++)
        if (s[i] == something) return true;
    return false;
}

but with a clever compiler, I could use the following (which is shorter and more clear):

bool find_something(string s, char something)
{
    for (size_t i = 0; i != s.size(); i++)
        if (s[i] == something) return true;
    return false;
}

then the compiler could detect that the code inside the loop doesn't perform any change on the string object, and then would build a code that would cache the value returned by s.size(), instead of making a (slower) function call for each iteration.

Is there such optimization with gcc?

This would typically be written something like `for (size_t i = 0, m = s.size(); i!=m; ++i)`. — David Schwartz, Aug 04 '15 at 21:17
This is called [Loop-Invariant Code Motion](https://en.wikipedia.org/wiki/Loop-invariant_code_motion). — Dan, Aug 04 '15 at 21:21
@Dan, not really duplicate : the best answer says: "It's memory references and function calls that may be more difficult. [about optimization]". But I would like to know more specifically about `gcc` — yolenoyer, Aug 04 '15 at 21:32
The standard library containers' `size` member functions get inlined anyways, so the function call you worry about does not exist in the first place. — Baum mit Augen, Aug 04 '15 at 21:49
@Baum-mit-augen Good to know this, tx; but the string::size() function was only a (bad) example for a wider question — yolenoyer, Aug 04 '15 at 21:51
@DavidSchwartz: I would use *for range*: `for (char c : s) {if (c == something) return true; } return false;)}` ;-) (so no constant inside or outside of the loop). — Jarod42, Aug 05 '15 at 01:09
@Jarod42 I would use `return s.find(something) != std::string::npos;` — Chris Drew, Aug 05 '15 at 02:30

Paul Groke · Accepted Answer · 2015-08-05T01:41:32.947

Generally there's nothing in your example that makes it impossible for the compiler to move the .size() computation before the loop. And in fact GCC 5.2.0 will produce exactly the same code for both implementations that you showed.

I would however strongly suggest against relying on optimizations like that (in really performance critical code) because a small change somewhere (GCCs optimizer, the implementation details of std::string, ...) could break GCCs ability to do this optimization.

However I don't see a point in writing the more verbose version in the usual 90% of code that's not really performance-critical.

Given a current C++ compiler though I would go for the even more concise:

bool find_something(std::string s, char something)
{
    for (ch : s)
        if (ch == something) return true;
    return false;
}

Which BTW also yields very similar machine code with GCC 5.2.0.

score 1 · Answer 2 · answered Aug 04 '15 at 21:16

1

The compiler has to know the object is not modified in a different thread. It can tell that the function won't change if the object doesn't change, but it can't tell that the object won't change from some other stimulus.

The compiler will unwind the call to the member with size if you include some form of whole-program optimization

answered Aug 04 '15 at 21:16

mksteve

12,614
3
28
50

3

The compiler can assume no other thread changes the string because unprotected concurrent writes with anything invokes UB. – Baum mit Augen Aug 04 '15 at 21:18
So I would have to tell the compiler I'm not using any disturbing thread, and then, there would be an optimization? (sorry if misunderstanding, i'm french) – yolenoyer Aug 04 '15 at 21:24
@yolenoyer No, you as the programmer must make sure no object is accessed while it is modified, ever. (Or use tools that do that for you.) The compiler may assume no other thread modifies an object without proper synchronization measures (as would be needed here). – Baum mit Augen Aug 04 '15 at 21:29

score 0 · Answer 3 · edited Jun 20 '20 at 09:12

It depends on whether or not the compiler can identify the function call as constant. Consider the following function that may reside in an external library which cannot be analyzed by the compiler.

int odd_size(string s) {
  static int a = 0;
  return a++;
}

This function will return distinct values regardless of the input parameter. The compiler can therfore not assume a constant return value even if the passed string object remains constant. No optimization will be applied.

On the other hand, if the compiler detects a constant function call, which may be the case in your example, it probably moves the constant expression out of the loop.

Older versions of gcc had an explicit option -floop-optimize which was responsible for that task. From the gcc-3.4.5 documentation:

-floop-optimize

Perform loop optimizations: move constant expressions out of loops, simplify exit test conditions and optionally do strength-reduction and loop unrolling as well.

Enabled at levels -O, -O2, -O3, -Os.

I cannot find this option in current versions of gcc, but I'm quite sure that they include this type of optimization as well.

Is there optimization for constant function return value inside a loop?

3 Answers3