Improve routing for wares to perform better on large networks

[Martin Quinson]

Here are the valgrind profiling file that I spoke about in https://wl.widelands.org/forum/topic/1464/?page=1#post-10721

For the record, the AI logic is disabled from this study (through replaying a previous game), and the UI is disabled too (through SDL_VIDEODRIVER=dummy).

The result is that the routing computations (Transfere::next_step or Economy::find_best_supply) cost between 1/3 and 1/2 of all instructions during the replay. That may be related to the fact that it was a 512x512 board.

So I was wrong, the most urgent optimization target is not the future event set ;) I will investiguate further.

[Martin Quinson (mquinson)]

I send the callgrind file in a separate attempt because it's quite a large file, and because launchpad deconnected my first attempt (loosing the file analysis that I typed).

[SirVer (sirver)]

some thoughts on this: I investigated making the pathing inside an economy cheaper some years ago. Basically the problem widelands tries to solve here is "all pairs shortest path" in a ever changing sparse graph (~3*nodes == edges). I did not find great algorithms for that back then - or rather, the problem was too involved that I wanted to spend much time on.

Especially merging economies was pretty expensive in all algorithms I looked at. Also, memory cost could be an issue here.

find_best_supply is another issue I think, not sure if this has something to do with routing or if it is just because it is quadratic in nature - trying each supply against each request or so.

[SirVer (sirver)]

Also, this bug name is not really actionable. Split it into two bugs maybe?

[SirVer (sirver)]

Setting to incomplete for bug sweeping.

[Launchpad Janitor (janitor)]

[Expired for widelands because there has been no activity for 60 days.]

[SirVer (sirver)]

Still think this should be split, but I am out of time for today :/.

[Launchpad Janitor (janitor)]

[Expired for widelands because there has been no activity for 60 days.]

[TiborB (tiborb95)]

I think this is typical choice of accuracy vs speed (CPU utilization).
I can imagine speeding this up if we are able to tolerate some inefficiency. My idea is to use map distance between source and target building, because generally direct distance is in relation to on-road distance. But there are exemptions - impassable terrains and ship transport.

Be more specific - if a production site can be supplied from 50 providers, we can check just 20 nearest (by direct distance) and it should garantee at 95% that the provider would be the same as if we checked all 50 of them. And CPU time would be cut to maybe 10%, while the algorithm would still quarantee that provider + consumer will be paired.

What do you think?

[GunChleoc (gunchleoc)]

Migrated to https://github.com/widelands/widelands/issues/914