land lord win condition is slow as molasse

[SirVer]

Likely reason is the looping over many fields necessary to count the condition. Tree gnome could also do to get a little faster. One possible solution is to implement a Map:foreach() function that calls one function for each field on the map. Or maybe there are other ways to make things quicker.

[Nasenbaer (nasenbaer)]

it is true, that wood gnome is quite slow. However when using wood gnome condition, the game runs smoothly, while it lags during calculation in land lord. Basically wood gnome does more calculations than the land lord calculation... I tested it several times with different maps...

[SirVer (sirver)]

I just did some actual messurments. On the big sun of fire map with all tribes, territorial lords _calc_points function takes .19 secs for one calculation; wood gnome takes .17 secs.

Not so much of a difference. Is this the margin you see as well or are your differences greater?

My branch which prints the profiling information can be found here:
lp:~sirver/widelands/win_condition_profiling

[SirVer (sirver)]

Need some timing information from others. Nasenbaer, you reported this; please check your timings.

[Nasenbaer (nasenbaer)]

sorry have not found the time until now.

First of all I noticed, that calculation times vary each time (map ancient sun of fire - 8 AIs, first 5 minutes):

Wood gnome: 0,17-0,26 sec (not connected to the game time - 0,17 was printed after ~ 5 minutes followed by 0,25 the next try)
Land lord: 0,21-0,39 sec (same as in wood gnome)

so:

1. calculation time takes longer over here (perhaps slower processor + other running programs in background + debug build? )
2. calculation of land lord takes ~ 1.5 times longer than the wood gnome calculation, although it seems to me, that the wood gnome calculation is the same as the land lord calculation + additional check whether an object is at the searched position and if yes, whether that object is a tree. Or am I missing something here?

[Nasenbaer (nasenbaer)]

unassigned myself, as I really do not have a clue, whatv is going on there. Or takes the handling (writing and reading) of lua arrays that much more time than in c++?

[SirVer (sirver)]

It is interpreted, so yes, loops are very expensive. I fear though that the pushing of the new field each step (which needs a new L_Field, delete old_field) is the really expensive part in the loop. The map::foreach could fix this in a cheaply manner. I'll investigate.

[SirVer (sirver)]

Some ramblings incoming, they contain some valuable information for the aspiring Widelands Lua hacker.

1)I have no idea why the timing changes so strongly. Theoretically, os.clock should return CPU time. Maybe we run into some memory timing issues here...

2) in interpreted languages, local variable access is usually very fast while property access is very slow (as it cannot be cached, because the languages could be dynamic and the value could be changed). So I reached a nice speedup from 100% to 75% by just replacing:

_landsizes[f.owners[1].number] = _landsizes[f.owners[1].number] + 1

through
local n = f.owners[1].number
_landsizes[n] = _landsizes[n] + 1

this is faster because accessing f.owners is quite expensive and we do it twice in the first code. down to 0.15s per calculation. Still pretty slow.

3) Another very slow function is the .owners field as it has to do a lot of calculations, and constructs a new lua table at each access. I added a new property L_Field.owner that only returns nil or the current owner. Speed is now at 0.02, that is 10% of original. For release builds, it is even faster. That is still not as fast as Lua can go, but it is as fast as it gets at the moment

4) The iteration over the map had no impact at all for speed. I wasted time implementing the map:foreach functionality because I thought it could be the culprit. Silly me should not have ignored the first rule of optimization: profile first!

All these changes are in trunk r5552.

[Nasenbaer (nasenbaer)]

Thanks a lot for tracking this down SirVer :)!!!

[SirVer (sirver)]

Released in build16-rc1