CODEWITHSUNDEEP
c++coptimizationcomplexity-theory
Wander Nauta
Wander Nauta

Reputation: 19615

Do C & C++ compilers optimize comparisons with function calls?

Do C and C++ compilers generally optimize comparisons with functions?

For example, this page suggests that the size function on std::lists in C++ can have a linear complexity O(N) in some standard library implementations (which makes sense for a linked list).

But in that case, if myList is a huge list, what would something like this do?

    if (myList.size() < 5) return 1;
    else return 2;

Would the size() function find and count all N list members, or would it be optimized to short circuit after finding 5 members?

Upvotes: 19

Views: 970

Answers (4)

phkahler
phkahler

Reputation: 5767

NO You are asking if the compiler can make a function behave differently depending on how its results are used. This could only potentially be done for inline functions where the caller and the function will be compiled together at the same time. It seems quite a stretch for anything beyond that.

Upvotes: 2

Jon
Jon

Reputation: 437336

Theoretically the possibility exists if size() was inlined, but to perform the optimization the compiler would have to

  1. Detect that you are testing specifically a "less than" condition
  2. Prove that the loop (assume one exists for the purposes of this discussion) results in a variable increasing monotonically
  3. Prove that there are no observable side effects from the loop body

That's a big bunch of things to count on IMHO, and it includes features which are not "obviously useful" in other contexts as well. Keep in mind that compiler vendors have limited resources so there has to be really good justification for implementing these prerequisites and having the compiler bring all the parts together to optimize this case.

Seeing as even if this is a perf issue for someone the problem can be easily solved in code, I don't feel that there would be such justification. So no, generally you should not expect cases like this to be optimized.

Upvotes: 15

mah
mah

Reputation: 39807

The myList.size() function itself has no way to be compiled for the purpose you're using it for, so it will determine the entire size. In order to get the optimization you're suggesting, you would need a dedicated predicate function instead of the general size(), something like bool sizeLessThan(int);.

Upvotes: 2

Luchian Grigore
Luchian Grigore

Reputation: 258568

Actually, in C++11, std::list is optimized and size() is returned in constant time.

For C++03, size() indeed operates in linear time, as it needs to count the elements each time.

Would the size() function find and count all N list members, or would it be optimized to short circuit after finding 5 members?

Never seen this sort of optimization happening in practice. While it's certainly legal, I doubt there's any compiler that actually implements something like this.

Upvotes: 11

Related Questions