# std::list very slow

## Recommended Posts

suliman    1652
Hi I run this chunk of loop 40 times per tick and it reduce my fps from 400 to 100 which is bizarre. This empty loop has bigger inpact on fps that all of my drawing and calculating together! For ecxample i fill the screen with my tile-based terrain. The loop has 40 objects and all 40 runs goes through all these so its 1600 passes through this empty loop. But it should still be pretty fast since it doesnt do anything inside the loop right? Whats the deal here?
// the list declaration
std::list <army *> armyList;

//the loop excecuted 40 times per tick
std::list<army *>::iterator myIt;
for ( myIt = www->armyList.begin(); myIt != www->armyList.end(); myIt++ ){
army * f=*myIt;

//1600 passes here

}



##### Share on other sites
SimonForsman    7642
Are you using a debug build ?

##### Share on other sites
suliman    1652
yes i was :)

in release the same loop changes fps from 400 to 390!

How come just this loop is so extremely slow in debug while other things seem to not have any big difference at all?

##### Share on other sites
Trenki    345
In debug builds the compiler will insert a lot of code for checking validity of iterators and stuff. It will also skip optimizing the code which can reduce performance drastically.
Another thing to point out it that you should use ++myIt in the for loop instead of the post increment because this should be faster as well. And depending on your usage pattern a simple vector might be even faster. Provided that you don't require insertion/deletion in the middle of the container. When the order of the elements in the list is not important using a vector is an option.

##### Share on other sites
Mushu    1396
Quote:
 Original post by TrenkiAnd depending on your usage pattern a simple vector might be even faster. Provided that you don't require insertion/deletion in the middle of the container. When the order of the elements in the list is not important using a vector is an option.

Also, provided you don't need to maintain references to the data in the container while changing the contents of the container. Adding/removing elements from a vector invalidates all iterators/pointers into that vector (because the vector may realloc the memory used by those elements), whereas this limitation doesn't exist with lists.

##### Share on other sites
Ezbez    1164
Lessons to be learned from this:
1. Never profile in Debug. It's all lies.
2. 400fps = 2.5ms for each frame. 100fps = 10ms for each frame. Therefore this loop is using ~7.5ms. This is a more useful way to think about what is going on. You didn't see a 300fps drop, you saw a 7.5ms/frame increase. The difference being that regardless of what fps you were getting before, you will always see a 7.5ms/frame increase, while you will not always see a 300fps drop. (eg: if you started at 100fps then added that loop, you might jump down to 17.5ms/f, or 57fps. That's a 43fps drop, not 300).

And FYI, 390 fps is 2.56ms/frame, so that's now a 0.01ms change from before. Much better! :D

Now I just hope I didn't bork any of my maths there.

##### Share on other sites
suliman    1652
thanks!

//slowerfor ( myIt = www->armyList.begin(); myIt != www->armyList.end(); myIt++ ){}//fasterfor ( myIt = www->armyList.begin(); myIt != www->armyList.end()){myIt++;}

Is that what you mean?

##### Share on other sites
Trenki    345
Quote:
 Original post by sulimanthanks!//slowerfor ( myIt = www->armyList.begin(); myIt != www->armyList.end(); myIt++ ){}//fasterfor ( myIt = www->armyList.begin(); myIt != www->armyList.end()){myIt++;}Is that what you mean?

No, this is what I mean:

//faster (note ++myIt)
for ( myIt = www->armyList.begin(); myIt != www->armyList.end(); ++myIt ){
}

This is supposed since it does not require a copy of the iterator to be created internally.