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

Question

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.

Answer 1

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.

Answer 2

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?)