end() Iterator performance hit

[squisher]

Hi,

While I was profiling my program I noticed a LOT of time was spent creating and destroying "end" iterators. Looking at the Irrlicht source, I saw that all the iterator loops were being written like this:

source/Irrlicht/CGUITreeView.cpp:224

Code: Select all

for( itThis = Parent->Childs.begin(); itThis != Parent->Childs.end(); itThis++ )

This was causing a non-trivial performance hit. It would be more efficient written like so:

Code: Select all

for( itThis = Parent->Childs.begin(), itEnd = Parent->Childs.end(); itThis != itEnd; ++itThis )

Here are all the places it would need to be changed:

Code: Select all

source/Irrlicht/CBoneSceneNode.cpp:73:          for (; ait != Animators.end(); ++ait)
source/Irrlicht/CBoneSceneNode.cpp:81:          for (; it != Children.end(); ++it)
source/Irrlicht/CBoneSceneNode.cpp:92:  for (; it != Node->getChildren().end(); ++it)
source/Irrlicht/CCameraSceneNode.cpp:115:       for (; ait != Animators.end(); ++ait)
source/Irrlicht/CColladaFileLoader.cpp:783:                                     for (; it != node->getChildren().end(); it = node->getChildren().begin())
source/Irrlicht/CGUIEnvironment.cpp:870:        for (; it != node->getChildren().end(); ++it)
source/Irrlicht/CGUIModalScreen.cpp:61:    for (; it != Children.end(); ++it)
source/Irrlicht/CGUIModalScreen.cpp:141:                for (; it != Children.end(); ++it)
source/Irrlicht/CGUIToolBar.cpp:38:             for (; it != children.end(); ++it)
source/Irrlicht/CGUITreeView.cpp:69:    for( it = Childs.begin(); it != Childs.end(); it++ )
source/Irrlicht/CGUITreeView.cpp:136:   for( itOther = Childs.begin(); itOther != Childs.end(); itOther++ )
source/Irrlicht/CGUITreeView.cpp:170:   for( itOther = Childs.begin(); itOther != Childs.end(); itOther++ )
source/Irrlicht/CGUITreeView.cpp:224:           for( itThis = Parent->Childs.begin(); itThis != Parent->Childs.end(); itThis++ )
source/Irrlicht/CGUITreeView.cpp:247:           for( itThis = Parent->Childs.begin(); itThis != Parent->Childs.end(); itThis++ )
source/Irrlicht/CGUITreeView.cpp:294:   for( itChild = Childs.begin(); itChild != Childs.end(); itChild++ )
source/Irrlicht/CGUITreeView.cpp:314:   for( itChild = Childs.begin(); itChild != Childs.end(); itChild++ )
source/Irrlicht/CGUITreeView.cpp:339:   for( itChild = Childs.begin(); itChild != Childs.end(); itChild++ )
source/Irrlicht/CIrrDeviceWin32.cpp:55: for (; it!= EnvMap.end(); ++it)
source/Irrlicht/CIrrDeviceWin32.cpp:66: for (; it!= EnvMap.end(); ++it)
source/Irrlicht/CIrrDeviceWin32.cpp:432:        for (; it!= EnvMap.end(); ++it)
source/Irrlicht/CIrrDeviceWinCE.cpp:61: for (; it!= EnvMap.end(); ++it)
source/Irrlicht/CIrrDeviceWinCE.cpp:71: for (; it!= EnvMap.end(); ++it)
source/Irrlicht/CIrrDeviceWinCE.cpp:457:        for (; it!= EnvMap.end(); ++it)
source/Irrlicht/CParticleSystemSceneNode.cpp:440:       for (; ait != AffectorList.end(); ++ait)
source/Irrlicht/CParticleSystemSceneNode.cpp:565:       for (core::list<IParticleAffector*>::ConstIterator it = AffectorList.begin();
                it != AffectorList.end(); ++it)
source/Irrlicht/CSceneCollisionManager.cpp:81:  for (; it != children.end(); ++it)
source/Irrlicht/CSceneCollisionManager.cpp:271: for (; it != children.end(); ++it)
source/Irrlicht/CSceneManager.cpp:1825: for (; it!=list.end(); ++it)
source/Irrlicht/CSceneManager.cpp:1849: for (; it!=list.end(); ++it)
source/Irrlicht/CSceneManager.cpp:1873: for (; it!=list.end(); ++it)
source/Irrlicht/CSceneManager.cpp:1895: for (; it!=list.end(); ++it)
source/Irrlicht/CSceneManager.cpp:2403:         for (; it != node->getAnimators().end(); ++it)
source/Irrlicht/CSceneManager.cpp:2443: for (; it != node->getChildren().end(); ++it)
include/IGUIElement.h:55:               for (; it != Children.end(); ++it)
include/IGUIElement.h:333:              for (; it != Children.end(); ++it)
include/IGUIElement.h:407:              for (; it != Children.end(); ++it)
include/IGUIElement.h:432:                      for (; it != Children.end(); ++it)
include/IGUIElement.h:444:                      for (; it != Children.end(); ++it)
include/IGUIElement.h:641:              for (; it != Children.end(); ++it)
include/IGUIElement.h:675:              for (; it != Children.end(); ++it)
include/ISceneNode.h:64:                        for (; ait != Animators.end(); ++ait)
include/ISceneNode.h:91:                                for (; it != Children.end(); ++it)
include/ISceneNode.h:126:                               for (; it != Children.end(); ++it)
include/ISceneNode.h:295:                       for (; it != Children.end(); ++it)
include/ISceneNode.h:316:                       for (; it != Children.end(); ++it)
include/ISceneNode.h:363:                       for (; it != Animators.end(); ++it)
include/ISceneNode.h:381:                       for (; it != Animators.end(); ++it)
include/ISceneNode.h:761:                       for (; it != toCopyFrom->Children.end(); ++it)
include/ISceneNode.h:767:                       for (; ait != toCopyFrom->Animators.end(); ++ait)
include/ISceneNode.h:785:                       for (; it != Children.end(); ++it)

[Ulf]

I second that

[hybrid]

Which compiler and optimization level did you choose? This kind of code should be optimized away unless the end iterator creation is too complex.

[CuteAlien]

Hm, I usually also write loops as done in Irrlicht. But I'm also not sure without testing if the compiler really can optimize this away. He could inline the end(), but he might not figure out that end doesn't change throughout the loop.

[hybrid]

Yes, but there would be not much more to do than a simple copy. No expensive construction and deconstruction. So the overhead would be non-existent. The dereference and comparison needs to be done anyway.

[squisher]

Ah, you're right. I didn't even think about the optimizer, that does indeed eliminate that particular performance hit in Release builds. It is still making my program annoyingly slow when I am debugging it though.

Incidentally the profiler I use is Very Sleepy. It only seems to work on un-optimized code, but it gets caught up on things like the end() iterator issue instead of showing me real bottlenecks.

[Revan1985]

To increment a bit the performance, i se always a declaration of the Iterator::end in a line before the loop...

it is usefull, not always, but some times it helps...

iterators are not efficent in call many times a method [like iterator::end() in a for] . . .