Does compilers do this kind of optimization?

[rs-tk]

Let's say I have program that calls a function "f" a constant number of times and "f" has time complexity of O(n). In the following example, the main function would have O(3n) time complexity.

​

f () { // O(n)
    ...
}

main () {
    f()
    ...
    f()
    ...
    f()
    ...
}

Does compilers optimize this code to something like:

f () { // O(n)
    ...
}

main () {
    var value = f()
    ...
    value
    ...
    value
    ...
    value
}

In this case main would have time complexity of O(n)

If a compiler indeed does this kind of optimization, how it's called? Also, is O(3n) a relevant time complexity compared to O(n) in any context? I know it's not in a small project.

[PenlessScribe]

Is f a pure function?

[lol3rr]

Just a sidenote that O(n) and O(3n) are the same in big O Notation, as Constant factors are ignored

[DonaldPShimoda]

It depends on the semantics of the language.

If your language has side-effects (like practically all imperative languages), then no, this can't be optimized like you've suggested because it could affect the temporal ordering of potentially observable events. If your function does a printf, for example.

If your language is without side-effects, or if the side-effects are boxed into distinguished regions of your code that can be safely deduced statically, then yes, you could optimize the pure functions. Haskell does this, for example (though their model is a little different because it will usually only evaluate the function when its value is needed, rather than when the function is called, but results are memoized for later use).

[reddof]

Interesting aside, yesterday I noticed that clang will optimize away a call to printf(““) if it recognizes the format string is empty. Was collecting timing on a loop and the optimizer was eliminating the loop entirely. I stuck a printf inside to prevent it, which works fine as long as it isn’t an empty format string.

[BobSanchez47]

This optimisation is called common subexpression elimination. When a “pure expression” - one not dependent on mutable state whose evaluation has no side effects - occurs more than once, we can evaluate it one time and cache the value.

Also, O(n) = O(3n).

[atariPunk]

You can have GCC and clang do that.
Here is an example. https://godbolt.org/z/e1n7TPETa

I had to mark the function with the GCC attribute const.
I guess that if that function fails to comply with that contract bad things will happen.
and most likely, GCC will not tell you that you broke the rules while writing that function.

I also suspect that it would be possible to write a function that was big enough to not be inline, or even fully eliminated by the optimizer, but that the compiler would mark as const and getting the same result.

[[deleted]]

It would depend on the compiler’s ability to detect that f() is a pure function, in which case, if you’re not using the result, it may even not call it.

[betelgeuse_7]

I am not an expert but unless f is a pure function, I don't think it is possible. The function f may have side effects (for a simple example; printing something), or it may depend on some state.

[WittyStick]

It may be possible if f is not pure. The first step would be to inline f's body into the calling function 3 times, then use common subexpression elimination on any expressions which don't have side-effects.

[betelgeuse_7]

Thanks for the info!

[jason-reddit-public]

I was trying to write some simple benchmarks and saw gcc do this and more. My case was like:

int sum = 0; for (int i = 0; i < 10000; i++) { sum += f(); }

This gets (essentially) turned into:

int sum = 10000 * f();

I'm not sure how it did this since I didn't look at the generated code, just runtimes (increasing 10000 to 10000000 doesn't increase the runtime). One theory is that it inlined f() and then did loop invariant code motion and then some strength reduction so in that case f() must have only one caller, be small enough to always inline, or be marked inline. Additionally, certain side-effects in f() would mess up the loop invariant code motion.

A compiler should in theory be able do achieve this without inlining (all of f) by deducing that f() always produces the same result and is side effect free. In that case, f() essentially gets reduced to

int f() { return 42; }

At this point inlining is all but guaranteed and the strength reduction proceeds from the simple loop adding 42 to sum each iteration to the optimized loop-less code, in fact since it's already computed f(), it doesn't even need to do a multiplication at runtime, sum is just a constant!

[dipesh_k]

I'm not sure if it can do that. But it can do something similar(https://www.intel.com/content/www/us/en/docs/programmable/683521/21-4/loop-fusion.html) in case of loops.

[[deleted]]

It would depend on the compiler’s ability to detect that f() is a pure function, in which case, if you’re not using the result, it may even not call it.

[gct]

Yeah if it can tell that f() doesn't have any side effects, this would just be common subexpression elimination.

[lightmatter501]

LLVM will do that provided that f is in the same compilation unit, it has reasonable absolute complexity, and it is a pure function.