ISceneNode::removeChild() is slow

[Desour]

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 the Game::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

	virtual bool removeChild(ISceneNode* child)
	{
	ISceneNodeList::iterator it = Children.begin();
	for (; it != Children.end(); ++it)
	if ((*it) == child)
	{
	(*it)->Parent = 0;
	(*it)->drop();
	Children.erase(it);
	return true;
	}
	return false;
	}

This needs to be fixed for better particle performance.

[SmallJoker]

The sorted std::set might perform better for lookups (binary search?). Or perhaps std::vector if the compiler is smart enough to parallelize the lookup code in std::find (e.g. by using SIMD).

Or move particles spawned by a particle spawner into a root ISceneNode's to shorten the child lookups.

[appgurueu]

The sorted std::set might perform better for loopkups (binary search?). Or perhaps std::vector if the compiler is smart enough to parallelize the lookup code in std::find (e.g. by using SIMD).

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.

[SmallJoker]

@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 std::list cannot be parallelized well due to the nature of pointer chains.

[appgurueu]

How would you seamlessly update those iterators when one child is removed?

That shouldn't be necessary, a doubly linked list doesn't invalidate iterators.

Storing iterators is in general bad practice as they may get outdated.

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.

If not now, someone will surely forget to update them in a future change.

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.

[Desour]

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 OnAnimate and OnRegisterSceneNode, which currently take about 1/8 client step cpu time that they mostly spend on iterating.