1

With the following code how many times would the min function actually be called

for (int i = 0; i < min(size, max_size); i++) {
   //Do something cool that does not involve changing the value of size or max size
}

Would the compiler notice that they could just calculate the minimum and register it or should I explicitly create a variable to hold the value before entering the loop? What kinds of languages would be able to optimize this?

As an extension if I were in an object oriented language with a similar loop except it looked more like this

for (int i = 0; i < object.coolFunc(); i++) {
   //Code that may change parameters and state of object but does not change the return value of coolFunc()
}

What would be optimized?

J.Doe
  • 1,502
  • 13
  • 47
  • 4
    It depends on the compiler and flags. It's possible it will be optimized, it's possible it won't. – François Andrieux Feb 28 '18 at 20:34
  • It's up to a specific compiler. But a conventional ones are very likely to optimize this. – Eugene Sh. Feb 28 '18 at 20:34
  • 3
    Give https://godbolt.org/ a try. It shows you the assembly produced by various compilers. – François Andrieux Feb 28 '18 at 20:35
  • I would not rely on it to be optimized. There are many factors that can affect it on one side and it is pretty easy to force compiler to call it only once on another. – Slava Feb 28 '18 at 20:37
  • Depends. But if you want that functionality why don't you just cache the return of your function yourself before the for loop? – mascoj Feb 28 '18 at 20:38
  • In the example `i < object.coolFunc()` how would the compiler know whether the same value is returned on each loop, or a different one? – Weather Vane Feb 28 '18 at 20:40
  • @WeatherVane Constant folding along with Link Time Optimization? – Eugene Sh. Feb 28 '18 at 20:42
  • You would need to rely on the compiler to assert that the value of the condition expression is not affected by the statements in the loop, ie that size and max_size does not change. If it cannot, then the compiler shouldn’t optimise as it will change the semantics of the program. – Love Tätting Feb 28 '18 at 20:45
  • see [Loop with a zero execution time](https://stackoverflow.com/q/26771692/1708801) – Shafik Yaghmour Feb 28 '18 at 20:46
  • 1
    @EugeneSh. Optimising is great with an excellent compiler like gcc, but suppose you are coding for an MCU, some cross-compilers supplied by the chip manufacturer have been flaky at best. Although the received wisdom on SO is that the compiler is better than me, I was taught not to write lazy code and not to let the compiler do the work for me. If the loop condition can obviously be done before the loop, it's a no-brainer. – Weather Vane Feb 28 '18 at 20:53
  • @WeatherVane I agree that where the "manual" optimization is obvious - better do it yourself. – Eugene Sh. Feb 28 '18 at 20:54
  • FYI, if you are discussing the C language, use the C tag. If you are discussing C++, use the C++ tag. Rarely, you need to use both tags. Reminder, C and C++ are distinct languages. – Thomas Matthews Feb 28 '18 at 21:13
  • As far as optimization goes, a lot depends on the signature and content of the function. For example, if a string doesn't change length inside the loop, the compiler can optimize the condition by calling the length function once instead of each iteration. If your comparison function is called on a mutable object then the compiler will have a more difficult time optimizing (if optimization is possible). – Thomas Matthews Feb 28 '18 at 21:15
  • This is not a duplicate of [condition check in for loop](https://stackoverflow.com/questions/25696857/condition-check-in-for-loop-in-c) because that question asks about computation inside the abstract C model, and its answer does not address optimization, whereas this question asks specifically about optimization, which is a question about compilers and opimization outside the model. – Eric Postpischil Mar 01 '18 at 00:12

1 Answers1

1

Any good compiler will optimize the controlling expression of a for loop by evaluating visibly invariant subexpressions in it just once, provided optimization is enabled. Here, “invariant” means the value of the subexpression does not change while the loop is executing. “Visibly” means the compiler can see that the expression is invariant. There are things that can interfere with this:

  • Suppose, inside the loop, some function is called and the address of size is passed as an argument. Since the function has the address of size, it could change the contents of size. Maybe the function does not do this, but the compiler might not be able to see the contents of the function. Its source code could be in another file. Or the function could be so complicated the compiler cannot analyze it. Then the compiler cannot see that size does not change.

  • min is not a standard C function, so your program must define it somewhere. As above, if the compiler does not know what min does or if it is too complicated for the compiler to analyze (not likely in this particular case, but in general), the compiler might not be able to see that it is a pure function.

Of course, the C standard does not guarantee this optimization. However, as you become experienced in programming, your knowledge of compilers and other tools should grow, and you will become familiar with what is expected of good tools, and you will also learn to beware of issues such as those above. For simple expressions, you can expect the compiler to optimize. But you need to remain alert to things that can interfere with optimization.

Eric Postpischil
  • 195,579
  • 13
  • 168
  • 312
  • The value's not changing is not sufficient for ["invariant"](https://en.wikipedia.org/wiki/Loop_invariant#Distinction_from_loop-invariant_code). As you mentioned below as the concept of pure function, the subexpression should have no side effect, or only have side effects that are equivalent between when the subexpression is inside the loop and when it is outside the loop. – xskxzr Mar 01 '18 at 03:49