#2012 closed enhancement (fixed)
[PATCH] Cache GetPercentMapExplored
Reported by: | scroogie | Owned by: | ben |
---|---|---|---|
Priority: | Nice to Have | Milestone: | Alpha 14 |
Component: | Core engine | Keywords: | patch performance |
Cc: | Itms, wraitii | Patch: |
Description (last modified by )
In a callgrind run I've seen that CCmpRangeManager::GetPercentMapExplored showed up as an expensive function (callgrind showed 6.56 self). Its apparently called quite often for statistics gathering. The patch changes the implementation to cache the value instead of recomputing it every time, as that includes traversing all tiles of the map. Also the original implementation traverses all tiles for playerId==0, which is not required, as it will always be 0. This gave me a slightly measurable speedup in replays of full games. Its of course only faster if the function is actually called that often, of which I didn't know if its on purpose or not. Should it only be called at the end of a game? Anyway, in case it stays like this, here is a patch.
Attachments (1)
Change History (20)
comment:1 by , 11 years ago
Keywords: | performance added |
---|
comment:2 by , 11 years ago
Summary: | Cache GetPercentMapExplored → [PATCH] Cache GetPercentMapExplored |
---|
comment:3 by , 11 years ago
Milestone: | Backlog → Alpha 14 |
---|
comment:4 by , 11 years ago
Oh thats interesting, so apparently the los-state is touched from somewhere else. After deserialization its reset by a full traversal, so its clear that its correct then. I'll try to find the problem.
comment:5 by , 11 years ago
Ok, found the culprit. I forgot the terrain influence, which explores the map in your influence area without line-of-sight. The easy fix is to update the exploredCount in UpdateTerritoriesLos(), which I attached as a patch now. But I'm thinking about maybe changing that part, as it seems unnecessary to iterate the whole map there everytime. Once explored tiles will never be set to unexplored, so it would be enough to do that once the influence changes.
by , 11 years ago
Attachment: | percent-explored.patch added |
---|
comment:6 by , 11 years ago
Just as a note, cannot beat your solution, much better not being called,
But I've noted that "hand inlining" LosIsOffWorld in two version, one for circle world, one for square world, does remove a lot of branching inside those huge loop, therefore making it way faster, and even disappear from profiler hot spots.
That give something like:
inline LosIsOffSquareWorld(...) { } ... inline LosIsOfCircleWorld(...) { } ... ... ... getPercentMapExplored(...) if (m_LosCircular) { for (ssize_t j = 0; j < m_TerrainVerticesPerSide; ++j) { for (ssize_t i = 0; i < m_TerrainVerticesPerSide; ++i) { if (LosIsOffCircularWorld()) { } } } } else //square map { for (ssize_t j = 0; j < m_TerrainVerticesPerSide; ++j) { for (ssize_t i = 0; i < m_TerrainVerticesPerSide; ++i) { if (LosIsOffSquareWorld()) { } } } }
There may surely be other code using LosIsOffWorld() inside huge loop that can be optimized like that.
comment:7 by , 11 years ago
Ah yes, nice idea. But after the patch, its only used in ResetDerivedData (called only after deserialization, so should be irrelevant) and LosAddStripHelper(). The last one uses only a horizontal iteration at the same height, though, so the bounds calculation can simply be moved out of the loop. Will do that once I find time (probably weekend).
comment:8 by , 11 years ago
Btw, during the work on the patch I asked myself two questions.
- Why doesn't the game use POV templates like described in the article the system is based on? (instead of calculating the circle around units everytime, save the rasterisation offsets).
- Is it correct that the influence area explores tiles for the player? I.e. building a CC explores all area around it, but without actually seeing in these areas (its explored but fogged)?
comment:9 by , 11 years ago
I have tested this and it works fine (no behavioral change) but I haven't really seen much of a perf improvement, either. How would you suggest measuring the performance gain of this?
comment:10 by , 11 years ago
Well, I proposed the change because GetPercentMapExplored was very high on the list when the game was profiled with valgrind. I used a commands.txt of a full game 1on1 and ran the replay mode in valgrind.
In this post (by coincidence) you can also see that it can be quite expensive (actually the second highest on his list, as it is called from JS): http://www.wildfiregames.com/forum/index.php?showtopic=17289&st=80#entry271371
With the patch I could also actually measure a difference in the time the replay takes.
comment:11 by , 11 years ago
Ah, and by the way, the function was called 31152 times in this game. I think this shows that its not such a good idea to traverse the whole map every time.
comment:13 by , 11 years ago
Keywords: | review removed |
---|
Thanks for the patch. Using Very Sleepy on Windows, I was able to confirm GetPercentMapExplored
was taking ~7% of total execution time on only a two player map! After the patch, it was no longer visible in the profiler.
comment:15 by , 7 years ago
Cc: | added |
---|---|
Description: | modified (diff) |
Resolution: | fixed |
Status: | closed → reopened |
comment:16 by , 7 years ago
Priority: | Nice to Have → Should Have |
---|
comment:17 by , 7 years ago
Milestone: | Alpha 14 → Alpha 22 |
---|
comment:18 by , 7 years ago
Milestone: | Alpha 22 → Alpha 14 |
---|---|
Priority: | Should Have → Nice to Have |
Resolution: | → fixed |
Status: | reopened → closed |
reverse opening of the ticket. This issue should be discussed on #4598.
comment:19 by , 7 years ago
In r19790:
Fix a map exploration OOS on rejoin when starting with territory at the map boundaries.
rP9951 forgot to add a LosIsOffWorld check in ExploreTerritories (aka UpdateTerritoriesLos) and thus marked tiles outside of the world as explored. rP13576 transformed the bug into a non-simulation desynchronization, causing rejoined players to see a different score,
as they excluded off-world tiles when filling the cache in ResetDerivedData upon rejoin.
rP19517 transformed the bug into an actual simulation OOS by serializing that map exploration percentage based on that cache.
Also tiles at the map border in square maps are not rendered as expected, so this commit hides refs #4267.
Differential Revision: https://code.wildfiregames.com/D630 Fixes #4598 Proofread by: Itms Tested By: Imarok
You're right, we currently only use it on the summary screen, but all the statistics get passed to the AIs and it's possible they'll want to know that one too, or we may add an in-game stats screen. So caching seems a reasonable thing to do.
There's a bug in the patch though: without the patch, start Acropolis 1 with no AI, then exit and check the exploration percentages (5%). Saving and reloading gives the same result. Now with your patch load the same map and exit, it will be only 3%. But after saving and reloading, it jumps to 5%.