C ++ using predefined constraints for loops

Question

In scripting languages ​​like PHP having such a for loop, 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 am not creating such a program. (For guys who feel they need to tell me why this piece of code and paste the bad thing here))

If this C ++ example was translated into a similar PHP script, the length of the string will be calculated every loop of the cycle. This will cause a huge performance loss in realistic scenarios.

I thought the same thing applies to C ++ programs, but when I look at the tutorials, a few open source libraries, and other pieces of code, I see that the limiter for the loop is not calculated in advance.

• Should I pre-calculate the string length s ?
• Why is the limiter not always calculated? (see this in the manuals and examples).
• Is there any kind of optimization performed by the compiler?

Answer 1

All this is relative.

PHP is interpreted, but if s.length falls into the 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 is actually very easy to focus on overhead loops when they load with other things.

As if you wrote it in C ++ and cout wrote to the console, do you know what will dominate? cout will be far and far, because this innocently looking operator << calls a huge pile of library code and system routines.

Answer 2

You must learn to justify simpler code. Try to convince yourself that sooner or later you will replace the string :: length implementation with a more optimized one. (Despite the fact that your project is likely to miss all deadlines, and string :: length optimization will be the least of your problems.) Such thinking will help you focus on things that really matter, although this is not always easy .. .

Answer 3

It depends on how string is implemented.

In null terminating strings, you must calculate the size at each iteration.

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

Answer 4

The optimizer will indeed be able to optimize the call to length if it can determine that its value will not change - however, you are safe if you calculate it beforehand (in many cases, however, optimization will not be possible, since it is not clear to the compiler whether change the condition variable during the cycle).

In many cases, this simply does not matter, because the cycle in question is not related to performance. Using the classic for(int i=0; i < somewhat(); ++i) and less work to type and read more than for(int i=0,end=somewhat(); i < end; ++i .

Note that the C ++ compiler usually includes small functions such as length (which usually extracts a pre-calculated length from a string object). Interpreted scripting languages ​​usually need to find a dictionary to call a function, so for C ++, the relative excess of redundant check once per iteration of the loop is probably much less.

Answer 5

I do not know about php , but I can say 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 are looking for the definition of length() (right-click on length() and select "Go to definition") OR, if you are using Visual Assist X, then place the cursor on length() and press Alt+G , you will find the following:

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

Where _Mysize is of type int , which clearly shows that the length of the string is precomputed and only the stored value is returned to each call to length() .

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

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

Thus, you will save overhead when calling the function length() equal to the length of the string number of times, which saves clicking and popping up the stack frame. It can be very expensive when your string is large.
Hope this helps.

Answer 6

• Maybe.
• For ease of reading.
• Sometimes. It depends on how well he discovers that the length will not change inside the loop.

Answer 7

You're right, s.length() usually evaluated at each iteration of the loop. You better write:

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

Instead of the above. However, for a loop with multiple iterations, it does not matter how often the length () call will be executed.

Answer 8

The short answer is because there are situations when you want it to be called every time.

another explanation: http://bytes.com/topic/c/answers/212351-loop-condition-evaluation

Answer 9

Well, since this is a very common scenario, most compilers will pre-compute the value. Especially when going through arrays and very common types - a string can be one of them.

In addition, the introduction of an additional variable can lead to the destruction of some other loop optimizations - it really depends on the compiler you are using and can change from version to version.

Thus, in some scenarios, "optimization" can have unpleasant consequences.

If the code is not a real "hot spot" where every performance tick matters, you should write it the same way you do: No "manual" preliminary calculation.

Reading is also very important when writing code!
Optimization should be carried out very carefully and only after intensive profiling!

Answer 10

std::string.length() returns a fixed variable that is stored in the container. It is already pre-calculated

Answer 11

You can pre-calculate the length of a string only if you are KNOW , the string will not change inside the loop.

I do not know why this is done in textbooks. A few hunches:
1) To get used to you so that you do not fall when you change the value of a string inside a loop.
2) Because it is easier to understand.

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

Answer 12

The compiler can save the result of the call and optimize all additional function calls, but it may not be. However, the cost of calling the function will be quite low, since all you need to do is return an int. In addition, there is a good chance that it will be built in, completely removing the cost of calling the function.

However, if you really do not care, you should profile your code and see if its preliminary calculation speeds up. But that would not hurt just to choose to pre-calculate it. It will not cost you anything. Most likely, in most cases this does not matter. There are several containers - like a list - where size () might not be an O (1) operation, and then preliminary costing 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 suppress the cost of such an effective function call. For std :: string, it should be O (1) and will probably be optimized, but you will need to check to be sure - and, of course, things like the level of optimization you are compiling could change the results.

It’s safer to pre-calculate, but often not necessary.

Answer 13

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

In general, a termination condition can be any expression, and not just a comparison of the index variable of the cycle (indeed, C / C ++ does not recognize any specific index, just an initializer expression, a loop test expression and loop counter expression (which is executed only each times). The C / C ++ for do/while is basically syntactic sugar for the do/while compound statement.

Answer 14

std::sting::length() returns the previously calculated value. Other stl containers recalculate their size each time you call the size() method, for example,

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

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

Answer 15

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

I agree that it is pre-calculated, and the function is likely to be built-in. It is also very interesting to know when you use your own functions / class.

Answer 16

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

I saw a good example of this in open source code: redis .

In sds.h (Simple Dynamic Strings), see the sdshdr structure:

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

As you can see, it caches the length (in the len field) of the buf character array, as well as the available free space (in free >) after the null character.

So the shared memory allocated for buf is

 len + free 

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