Opened 11 years ago

Closed 7 years ago

Last modified 7 years ago

#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 Imarok)

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)

percent-explored.patch (7.3 KB ) - added by scroogie 11 years ago.

Download all attachments as: .zip

Change History (20)

comment:1 by scroogie, 11 years ago

Keywords: performance added

comment:2 by historic_bruno, 11 years ago

Summary: Cache GetPercentMapExplored[PATCH] Cache GetPercentMapExplored

comment:3 by historic_bruno, 11 years ago

Milestone: BacklogAlpha 14

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%.

comment:4 by scroogie, 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 scroogie, 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 scroogie, 11 years ago

Attachment: percent-explored.patch added

comment:6 by tuan kuranes, 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 scroogie, 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 scroogie, 11 years ago

Btw, during the work on the patch I asked myself two questions.

  1. 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).
  1. 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 alpha123, 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 scroogie, 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 scroogie, 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:12 by ben, 11 years ago

Owner: set to ben
Resolution: fixed
Status: newclosed

In 13576:

Optimizes GetPercentMapExplored by caching explored vertices per player, patch by scroogie, fixes #2012

comment:13 by historic_bruno, 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:14 by sanderd17, 11 years ago

Last edited 11 years ago by sanderd17 (previous) (diff)

comment:15 by Imarok, 7 years ago

Cc: Itms wraitii added
Description: modified (diff)
Resolution: fixed
Status: closedreopened

Caching is broken (see #4598) I guess it's either broken since its implementation or since r16751.

comment:16 by Imarok, 7 years ago

Priority: Nice to HaveShould Have

comment:17 by Imarok, 7 years ago

Milestone: Alpha 14Alpha 22

comment:18 by Imarok, 7 years ago

Milestone: Alpha 22Alpha 14
Priority: Should HaveNice to Have
Resolution: fixed
Status: reopenedclosed

reverse opening of the ticket. This issue should be discussed on #4598.

comment:19 by elexis, 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

Note: See TracTickets for help on using tickets.