C++ using precalculated limiters in for loops

Question

In scripting languages like PHP having a for loop like this would be a very bad idea:

string s("ABCDEFG");
int i;
for( i = 0; i < s.length(); i ++ )
{
   cout << s[ i ];
}

This is an example, i'm not building a program like this. (For the guys that feel like they have to tell me why this piece of code <insert bad thing about it here>)

If this C++ example was translated to a similar PHP script the lenght of the string would be calculated every loop cycle. That would cause an enormous perfomance loss in realistic scripts.

I thought the same would apply to C++ programs but when I take a look at tutorials, several open-source libraries and other pieces of code I see that the limiter for the loop isn't precalculated.

• Should I precalculate the lenght of the string s?
• Why isn't the limiter always precalculated? (seen this in tutorials and examples)
• Is there some sort of optimization done by the compiler?

Answer 1

It's all relative.

PHP is interpreted, but if s.length drops into a compiled part of the PHP interpreter, it will not be slow. But even if it is slow, what about the time spent in s[i], and what about the time spent in cout <<?

It's really easy to focus on loop overhead while getting swamped with other stuff.

Like if you wrote this in C++, and cout were writing to the console, do you know what would dominate? cout would, far and away, because that innocent-looking << operator invokes a huge pile of library code and system routines.

Answer 2

You should learn to justify simpler code. Try to convince yourself that sooner or later you will replace string::length implementation to more optimized one. (Even though your project will most likely miss all deadlines, and optimizing string::length will be the least of your problems.) This kind of thinking will help you focus on things that really matter, even though it's not always easy...

Answer 3

It depends on how the string is implemented.

On null terminated strings you have to calculate the size on every iteration.

std::string is a container and the size should be returned in O(1) time,
it depends (again) on the implementation.

Answer 4

The optimizer may indeed be able to optimize the call to length away if he's able to determine that its value won't change - nevertheless, you're on the safe side if you precalculate it (in many cases, however, optimization won't be possible because it's not clear to the compiler whether the condition variable could possible be changed during the loop).

In many cases, it just doesn't matter because the loop in question is not performance-relevant. Using the classic for(int i=0; i < somewhat(); ++i) is both less work to type and easier to read than for(int i=0,end=somewhat(); i < end; ++i.

Note that the C++ compiler will usually inline small functions, such as length (which would usually retrieve a precalculated length from the string object). Interpreted scripting languages usually need a dictionary lookup for a function call, so for C++ the relative overhad of the redundant check once per loop iteration is probably much smaller.

Answer 5

You're correct, s.length() will normally be evaluated on every loop iteration. You're better off writing:

size_t len = s.length();
for (size_t i = 0; i < len; ++i) {
   ...
}

Instead of the above. That said, for a loop with only a few iterations, it doesn't really matter how often the call to length() will be made.

Answer 6

I don't know about php but I can tell what c++ does. Consider:

std::string s("Rajendra");
for (unsigned int i = 0; i < s.length(); i++)
{
    std::cout << s[i] << std::endl;
}

If you go for looking up definition of length() (right click on length() and click on "Go To Definition") OR if you are using Visual Assist X then placing the cursor on length() and press Alt+G, you will find following:

size_type __CLR_OR_THIS_CALL length() const
    {   // return length of sequence
    return (_Mysize);
    }

Where _Mysize is of type int, which clearly reveals that length of the string is pre-calculated and only stored value is being returned each call to length().

However,IMPO (in my personal opinion), this coding style is bad and should be best avoided. I would prefer following:

std::string s("Rajendra");
int len = s.length();
for (unsigned int i = 0; i < len; i++)
{
    std::cout << s[i] << std::endl;
}

This way, you will save the overhead of calling length() function equal to length of the string number of times, which saves pushing and popping of stack frame. This can be very expensive when your string is large.
Hope that helps.

Answer 7

1. Probably.
2. For readability.
3. Sometimes. It depends on how good it is at detecting that the length will not change inside the loop.

Answer 8

Short answer, because there are situations where you want it called each time.

someone else's explanation: http://bytes.com/topic/c/answers/212351-loop-condition-evaluation

Answer 9

Well - as this is a very common scenario, most compilers will precalculate the value. Especially when looping through arrays and very common types - string might be one of them.

In addition, introducing an additional variable might destroy some other loop optimizations - it really depends on the compiler you use and might change from version to version.
Thus in some scenarious, the "optimization" could backfire.

If the code is non real "hot-spot" where every tick of performance does matter, you should write it as you did: No "manual" precalculation.

Readability is also very important when writing code!
Optimizations should be done very carefully and only after intensive profiling!

Answer 10

std::string.length() returns fixed variable, that stores in container. It is already precalculated

Answer 11

You could precalculate the length of the string only if you KNOW the string won't ever change inside the loop.

I don't know why it is done this way in tutorials. A few guesses:
1) To get you in the habit so you don't get hosed when you are changing the value of the string inside the loop.
2) Because it is easier to understand.

Yes, the optimizer will try to improve this, if it can determine if the string won't change

Answer 12

The compiler may be able to save the result of the call and optimize away all of the extra function calls, but it may not. However, the cost of the function call will be quite low since all it has to do is return an int. On top of that, there's a good chance that it will be inlined, removing the cost of the function call altogether.

However, if you really care, you should profile your code and see whether precalculating the value makes it any faster. But it wouldn't hurt to just choose to precalculate it anyway. It won't cost you anything. Odds are, in most cases though, it doesn't matter. There are some containers - like list - where size() might not be an O(1) operation, and then precalculating would be a really good idea, but for most it probably doesn't matter much - especially if the contents of your loop are enough to overwhelm the cost of such an efficient function call. For std::string, it should be O(1), and will probably be optimized away, but you'd have to test to be sure - and of course things like the optimization level that you compile at could change the results.

It's safer to precalculate but often not necessary.

Answer 13

In this particular case, std::string.length() is usually (but not necessarily) a constant-time operation and usually pretty efficient.

For the general case, the loop termination condition can be any expression, not just a comparison of the loop index variable (indeed, C/C++ does not recognize any particular index, just an initializer expression, a loop test expression and a loop counter expression (which just is executed every time through). The C/C++ for loop is basically syntactic sugar for a do/while compound statement.

Answer 14

std::sting::length() returns a precalculated value. Other stl containers recalculate their size every time you call the method size() e.g

• std::list::size() recalculates the size and
• std::vector::size() returns a precalculated value

It depends on how the internal storage of the container is implemented. std::vector is an array with capacity 2^n and std::list is an linked list.

Answer 15

Just for information, on my computer, g++ 4.4.2, with -O3, with the given piece of code, the function std::string::length() const is called 8 times.

I agree it's precalculated and the function is very likely to be inlined. Still very interesting to know when you are using your own functions/class.

Answer 16

If your program performs a lot of operations on strings all the time like copying strings ( with memcpy ) then it makes sense to cache the length of the string.

A good example of this I have seen in opensource code is redis.

In sds.h ( Simple Dynamic Strings ) look at sdshdr structure:

struct sdshdr {
    long len;
    long free;
    char buf[];
}; 

As you can see it caches the length ( in len field ) of the character array buf and also the free space available ( in free field ) after the null character.

So the total memory allocated to buf is

len + free

This saves a realloc in case the buf needs to be modified and it fits in the space already available.