Speed up GameObjectManager::get_singleton_by_type

[mstoeckl]

This mitigates a major cause of lag for me -- calls to Sector::get_camera() were very slow on levels with many objects, because each call ended up scanning through the full list of objects. Sector::get_camera() gets called a lot, by every BadGuy::is_offscreen() and many times in ParticleSystem::draw(). The fix is to look up the singleton objects using (ultimately) the m_objects_by_type_index map.

(SuperTux still has a bunch of other performance issues of this type; GameObjectManager::get_object_count and GameObjectManager::get_objects_by_type are other functions that are called too often and will search the full object list instead of using m_objects_by_type_index or an equivalent. Long term, I'd also recommend replacing m_objects_by_type_index with a vector indexed by an integer type ids.)

[tobbi]

@mstoeckl Can / will you attempt the other speed improvements in subsequent pull requests?

[mstoeckl]

Can / will you attempt the other speed improvements in subsequent pull requests?

I'm thinking about how to do this properly at the moment. There are a few directions that I think are feasible, which have different development/maintenance/performance tradeoffs:

1. Register all intermediate classes, like WalkingBadguy/BadGuy/MovingSprite/MovingObject to the GameObjectManager::.m_get_objects_by_type_index array; this directly solves the problem of "make get_object_count()/get_objects_by_type()" run faster. (I've implemented this in https://github.com/mstoeckl/supertux/tree/class-indexing, and can confirm that it makes the "40 crushers + 2000 coins" scenario run quickly. The cost is that it indexes all intermediate classes, even though some of these aren't searched for; fortunately the indexing is cheap.) Easy but tedious initial work, an extra method to implement for classes deriving GameObjects, some small overhead when adding/removing GameObjects.
2. Spatial index of all GameObjects, which would add a method like get_all_objects_in_rect() that makes it possible to efficiently look for all nearby objects. A lot of initial work, unknown maintenance costs depending on solution, introduces some additional cost when moving GameObjects.
3. Specialized indexes and counters for each use; e.g, spatial index (or just plain list) for Bricks, Portables, BadGuys, Rocks, Totems, plain list of YetiStalactites, counters for Levels, SecretAreaTriggers, Badguys, Bullets, LevelTiles. This would make GameObjectManager somewhat less generic. (A lot of work (but can be incremental), need to explicitly add index to GameObjectManager for each use, best performance.)

As writing a good spatial index may be difficult, and I don't think levels are complicated enough for this to be necessary, I currently plan to investigate option 3, and then make a PR for either 1 or 3. (Most likely option 1, since I don't want to increase development costs before Worlds 3 and 4 are complete.) Edit: went with option 1.

[mstoeckl]

I've opened https://github.com/SuperTux/supertux/pull/2991, which as a side effect of speeding up get_objects_by_type makes get_singleton_by_type much faster, rendering this PR unnecessary (assuming of course, that #2991 proves an acceptable solution).

[mstoeckl]

Closing, this PR has been superseded.