Iteration optimization question

[vendik]

Currently it seems that EntitiyManager::entities_with_components and EntitiyManager::each methods iterate over all entities and check their masks for a match. This could be improved by taking advantage of the fact that different component families are kept in separate, contiguous memory blocks.

First of all we would need to store the entity id inside the ComponentHelper, this way we can quickly discover the parent entity of any component. Then once one of the above mentioned methods gets called we could iterate the memory block that corresponds to the family of the first component passed into the method and check each of it's parent entities for a mask match.

Then whenever the user calls EntitiyManager::entities_with_components orEntitiyManager::each they should order the components so that the most seldom used component is passed in first.

F.e let's say we have 10000 entities, all of which have a Positioncomponent. Of those entities only 100 have a LinearMovementcomponent. When we call entities.entities_with_components(LinearMovement, Position) we would iterate the memory block that stores the LinearMovement components, which is only 100 entries, instead of all 10000 entries.

This would of course increase the memory footprint, as every component instance needs to store it's parent entity's id.

What are your thoughts on this kind of change?

[alecthomas]

Take a look at #68, as well as the compile time branch. The latter allows custom storage backends, and implements several.

Another option is to have Systems register their interest, and the entity manager maintains vectors for each one.

[vendik]

The compile time branch is quite a lot behind master, is it missing any major features or bugfixes?

[alecthomas]

It is a reimplementation, so it's not "behind" in the sense you mean. But it also deliberately does not implement generic events or systems, so it is lacking features from master.

[vendik]

Thanks for the info! I'll use compile time branch with a custom storage and add a custom iterator.

[alecthomas]

Excellent! If you can send a pull request with your custom storage backend I'd love to integrate it.