CODEWITHSUNDEEP
c++compiler-optimization
Indoordinosaur
Indoordinosaur

Reputation: 127

Can compiler optimization elminate a function repeatedly called in a for-loop's conditional?

I was reading about hash functions (i'm an intermediate CS student) and came across this:

int hash (const string & key, int tableSize) {
    int hasVal = 0;

    for (int i = 0; i < key.length(); i++)
        hashVal = 37 * hashVal + key[i];

    .....
    return hashVal;
}

I was looking at this code and noticed that it would be faster if in the for-loop instead of calling key.length() each time we instead did this:

int n = key.length();
for (int i = 0; i < n; i++)

My question is, since this is such an obvious way to slightly improve performance does the compiler automatically do this for us? I don't yet know much about compilers but I was curious as to the answer of this question. When writing code to use less operations people have often pointed out that the things that I do are often already done for me by the compiler so I'm wasting my time but doing things such as inline functions. I care about this because I am programming a game where physics processing needs to be efficient so that things don't feel clunky.

Upvotes: 5

Views: 1959

Answers (4)

Mats Petersson
Mats Petersson

Reputation: 129314

Short answer: It can sometimes...

Long answer:

If the compiler can determine that key.length() is a "constant" value based on the loop itself, then it will be able to optimise out the call. This in turn depends on the definition of the class used (in this case string, which we can expect is "well written"). It also relies on the compiler understanding that the loop isn't altering the key in a way that alters key.length().

Key elements for this to ever work is that the function is inline (or is a template function, inline is required to allow it to be included multiple times in different compile units - or available within the same source file) and the source code is in a header file included by the compile unit.

And of course, there is no requirement in the C++ standard that the compiler does this. It is perfectly within the standard compliance to call the function every time.

Upvotes: 3

Tristan Brindle
Tristan Brindle

Reputation: 16824

It's only safe to move key.length() out of the loop if it's a pure function -- that is, one that has no side effects. If the compiler can detect that this is so, then I'd say it's likely it would perform the optimisation.

Unfortunately, unlike Fortran, C++ has no standard way to mark something as pure. If the function is inline (or inline-able), then the compiler has the definition and can probably work it out for itself, or at least eliminate the function call.

Marking the member function as const guarantees that it won't affect the current instance, but there's no reason in principle that key.length() couldn't change some global variable, so I doubt this in itself would be sufficient.

(There are various compiler specific ways of declaring a function pure -- like __attribute__((pure)) in GCC and compatible compilers (Clang, Intel). Perhaps experiment with these and see whether they make any difference?)

Upvotes: 2

luk32
luk32

Reputation: 16070

There are two places where optimization will kick in.

  1. Smarter compilers will introspect short functions to see if they have impact on the if clause. Probably most compilers will inline the call, making it an equivalent to what you wrote.

  2. On cpu level branch prediction would also make it (substantially) faster compared to more "random" if. One of the top question on SO shows nice hardcore example of this.

EDIT: I assumed earlier that declaring method length() const will be enough. But it is too weak. Method can still throw random stuff out with out changing the state of object. However I am 100% sure, that decent compilers do introspect functions and methods like I described.

Upvotes: 0

Oliver Matthews
Oliver Matthews

Reputation: 7813

It's a very compiler dependent answer. The only way to be certain is to generate the assembler and have a poke at what it creates (I'd recommend learning how to do that with your compiler and trying it anyway, it's very instructive*).

It's not that obvious of an optimization - the compiler can perform that optimization, but only if it is sure that .length() won't change - i.e. no other threads have access to the data and it is able to determine that nothing inside the loop will alter .length() The latter is easy to check since it is a const string, but the former less so. Having said that, I'd expect the compiler to assume it was const everywhere at moderate levels of optimization.

*pun intentional; sorry.

Upvotes: 0

Related Questions