ISceneNode::removeChild() is slow #274
Comments
The sorted Or move particles spawned by a particle spawner into a root ISceneNode's to shorten the child lookups. |
I don't think we need any sorting here. An unordered set would work, but is unnecessary. We have a doubly linked list and that allows O(1) removal - we just need the ISceneNode to store an iterator to its position in the list. |
@appgurueu How would you seamlessly update those iterators when one child is removed? Storing iterators is in general bad practice as they may get outdated. If not now, someone will surely forget to update them in a future change. I think what slows down the code right now is that doubly-linked lists like |
That shouldn't be necessary, a doubly linked list doesn't invalidate iterators.
Doubly linked lists are special. Pretty much the only reason to use them is if you will be storing iterators to do element removal somewhere within the list in O(1) time.
I would have liked to believe that this would be well isolated to the addChild and removeChild methods, but ASan seems to be proving me wrong. |
If in the future we want to replace the containers again or so, please note that iterating through also needs to be fast, because of functions like |
I've profiled Wuzzy's shadow forest game, which has many enemies that shoot with particles on you, and causes 4fps or so on my machine, even on low view range. I've used
RelWithDebInfo
. Here's a screenshot of theGame::run()
part:Here's the implementation of
ISceneNode::removeChild()
, it iterates through all scene node childs:irrlicht/include/ISceneNode.h
Lines 290 to 303 in fb4ee6a
This needs to be fixed for better particle performance.
The text was updated successfully, but these errors were encountered: