[P] Optimized TileLoop_Road boosts performance for huge maps

[PhilSophus]

Recently I started the Cindini scenario and was quite astonished that just after start it was already causing a CPU load of 80% on an AMD64 2.5Ghz core.

So, I did some profiling and found out that TileLoop_Road was consuming 30% of the CPU cycles. Further investigation revealed that this was caused by finding the closest town for non-town-owned roads by looping over all towns (around 500 for the mentioned scenario). On the other hand the field in the map array used for the town for town-owned roads was just unused for other roads. And towns only move seldom

So, that is what the patch does: For non-town-owned roads it stores the closest town in m2 therefore avoiding the costly calculation. This reduces the time used by TileLoop_Road from 30% to 2% for the above mentioned scenario (this is no typo).

Of course, such big improvement will usually only happen in maps, where lots of roads are not in a town and there is a big number of towns. This is usually only the case for huge pre-built scenarios (I know at least two that have this problem).

Note: This patch no longer bumps the savegame format.

[CommanderZ]

This would better go directly into flyspray. No need for player feedback, it needs dev attention only.

I mean...good job

[PhilSophus]

No need for player feedback

I need you as cheap testers

Unfortunately, I either have time to play or to code, seldom both and sometimes none of it

[SmatZ]

Thanks for your effort. However, there are things I found when reading the patch:

crash after building road in SE when there is no town
savegame bump is not needed
use "threshold == UINT_MAX" instead of "threshold == (uint)-1" (similiar problem at more places)
you should use existing CheckSavegameVersion()
UpdateRoadTilesTown() name is a bit weird
"if (_game_mode == GM_EDITOR)" in town_cmd.cpp - is it needed?
change in ClosestTownFromTile() - is it needed? won't it cause strange behaviour when treshold == 99999999 ?

I didn't really play-test it... I think this is enough for now

[PhilSophus]

crash after building road in SE when there is no town

Okay, will be fixed.

savegame bump is not needed

But how do you know you need to calculate the closest town then? I'm also not sure if it has bad side-effects if a game saved by this patch is loaded in a non-patched version (the town index may be non-zero for non-town-owned roads now). So, are you sure, it's not needed?

use "threshold == UINT_MAX" instead of "threshold == (uint)-1" (similiar problem at more places)

I also thought, this looked strange, but only re-used existing code. I can change it, though. UINT_MAX looks a lot better

you should use existing CheckSavegameVersion()

The existing one is strange, why does it exist for a non-existing savegame version?

UpdateRoadTilesTown() name is a bit weird

I guess my C++ compiler wouldn't be that happy about UpdateRoadTile'sTown

"if (_game_mode == GM_EDITOR)" in town_cmd.cpp - is it needed?

When founding towns after building roads (which can only happen in scenario editor), the closest town of a road tile may change and needs to be recalculated.

change in ClosestTownFromTile() - is it needed? won't it cause strange behaviour when treshold == 99999999?

Of course, this must be changed, as otherwise the expensive call to CalcClosestTownFromTile would still happen.
However, if that check for the threshold is not there, the land info on road tile will always report the road to have the local authority of the closest town. Hmm, I just notice, I shouldn't call CalcClosestTownFromTile in that case, either, but just check, whether the closest town is in range.

Thank you for taking the time to comment.


I'll do the changes tomorrow, as nothing is worse than coding when dog-tired So, guys don't build roads before founding a town until then


Edit: I also considered a caching approach, i.e. not converting on loading the game, but checking the town for validity on access and calculate if needed. Would that be better? The problem about this is, that town index zero is stored for non-town-owned roads at the moment and this is a valid town index, isn't it?

[DaleStan]

UpdateRoadTilesTown() name is a bit weird

I guess my C++ compiler wouldn't be that happy about UpdateRoadTile'sTown

UpdateTownForRoadTile? UpdateRoadTileTown?

Edit: I also considered a caching approach, i.e. not converting on loading the game, but checking the town for validity on access and calculate if needed. Would that be better? The problem about this is, that town index zero is stored for non-town-owned roads at the moment and this is a valid town index, isn't it?

I'd try changing all zeros to INVALID_TOWN or whatever it is at load-time.

[PhilSophus]

I attached a new version of the patch to the first post. It includes:

• Fix crash when building roads in scenario editor when no town exists
• Don't call CalcClosestTownFromTile when a threshold is passed to ClosestTownFromTile but check the threshold directly
• Fix codestyle issues mentioned by SmatZ
• Includes FS#2351 (Replace (uint)-1 by UINT_MAX)

UpdateTownForRoadTile? UpdateRoadTileTown?

Thanks, I used UpdateTownForRoadTile.

Edit: I also considered a caching approach, i.e. not converting on loading the game, but checking the town for validity on access and calculate if needed. Would that be better? The problem about this is, that town index zero is stored for non-town-owned roads at the moment and this is a valid town index, isn't it?

I'd try changing all zeros to INVALID_TOWN or whatever it is at load-time.

Well, the real question is, whether a caching approach would be the right thing to do here. As the room is there is in the savegame (i.e. otherwise unused) I think it is better to just save the closest town from now on (savegames are slightly bigger due to worse compressibility) and just convert older games and forget that it has ever been different in the rest of the code. The delay when loading huge games or starting huge scenarios that need to be converted is noticeable, though.

[Hirundo]

you should use existing CheckSavegameVersion()

The existing one is strange, why does it exist for a non-existing savegame version?

In r14348, this code was added to fix a problem with signs having the colour of invalid player. What it does is fixing this for all signs in savegames made with version 102 and lower. This is done unnecessarily for savegames made between r14348 and the next savegame bump, but it won't hurt anyone.

So effectively it's a small amount of unneeded work in exchange for avoiding a savegame bump, a good trade-off in my opinion. The same approach could be used for this patch, so the savegame version can stay at 102.

[PhilSophus]

New update:

• Savegame bump removed
• FS#2351 is in trunk so remove it from the patch (how I love MQ )

I guess, it is ready to be submitted to flyspray.

Edit: FS#2354

Edit: In trunk