Observation Regarding Performance

[knightly]

James,

If you try to load a large save game (e.g. Colin's) using centralized path searching system and make sure that the system has finished searching (see Status in Display Menu), then fast-forward the game, you will see that game speed as designated by T fluctuates and can go down rather low (less than 10 from time to time).

Since this is not caused by connexion rebuilding or path searching related activities, I suspect certain feature(s) takes too long to run. I think to track it down, profiling is needed. Alternatively, since you should be familiar with your own code, do you have any idea what code triggers this?

Knightly

[jamespetts]

Knightly,

thank you for the feedback - it is most helpful :-) I did have a go at profiling once, but I could not for the life of me work out how to get it set up. It required the use of MinGW, which I had previously been unable to set up, and the documentation was very scarce. I suspect that setting up profiling in Linux with Valgrind would be a great deal easier, but I do not use Linux on the computer on which I develop Simutrans-Experimental. Do you have profiling set up at your end for the path searching system?

As to what it might be, the first thing that springs to mind is passenger generation: the step_passagiere() method in Simutrans-Experimental is much changed from that in Simutrans-Standard, and adds a great many additional features necessary for the extra economic depth. It is one of the more computationally demanding elements of the game, so additions to that method can add a substantial amount of overhead. The additional destinations feature in particular means that much of the code (including retrieving paths from where they are stored, which might itself be non-trivial given that the hashtable seems to iterate through a linked list in order to return the value for a key) has to be run up to four times as often (depending on the number of additional destinations generated) as in Simutrans-Standard. There is not anything else in the code like the original path search, however, that is triggered periodically and is very heavy (at least, nothing that I have added for Simutrans-Experimental): the step_passagiere() method runs more or less constantly. If you have the AI enabled, it might be that the AI players are thinking of building something.

Two things to check, however:  (1) is that sort of reduction present in Simutrans-Standard in any event? Some of Colin's maps are very large, and even Simutrans-Standard might be slow; and (2) do you have other applications running in the background? I find that the fast forward counter speed is often heavily affected by having background applications running at the same time.

[gerw]

I suspect that setting up profiling in Linux with Valgrind would be a great deal easier, but I do not use Linux on the computer on which I develop Simutrans-Experimental. Do you have profiling set up at your end for the path searching system?

Profiling with Linux is fairly easy:
1. edit config.default to set up profiling (PROFILE = 1)
2. make clean && make
3. start simutrans and quit after a while (maybe 2 or 3 months in fast forward)
4. you find a gmon.prof (if I remember correctly) in ~/simutrans
5. use "gprof executable gmon.prof > output" to generate the profile

I hope this helps.

[knightly]

I did have a go at profiling once, but I could not for the life of me work out how to get it set up. It required the use of MinGW, which I had previously been unable to set up, and the documentation was very scarce.

Thanks Gerd for the instructions. Unfortunately, I don't have Linux. If only someone familiar with MinGW can write a more detailed instruction on how to set up MinGW for compiling and profiling Simutrans.

As to what it might be, the first thing that springs to mind is passenger generation: the step_passagiere() method in Simutrans-Experimental is much changed from that in Simutrans-Standard, and adds a great many additional features necessary for the extra economic depth. It is one of the more computationally demanding elements of the game, so additions to that method can add a substantial amount of overhead.

Is there any chance to simplify stadt_t::step_passagiere() or make it more efficient?

The additional destinations feature in particular means that much of the code (including retrieving paths from where they are stored, which might itself be non-trivial given that the hashtable seems to iterate through a linked list in order to return the value for a key) has to be run up to four times as often (depending on the number of additional destinations generated) as in Simutrans-Standard.

One of my optimisations of the centralised path searching system is to improve the complexity of path retrieval from ( 2 x lg n ) to a constant time of ( 2 ). Since I was using the centralised path searching system while testing Colin's save game, path retrieval should not be the cause of the problem.

There is not anything else in the code like the original path search, however, that is triggered periodically and is very heavy (at least, nothing that I have added for Simutrans-Experimental): the step_passagiere() method runs more or less constantly. If you have the AI enabled, it might be that the AI players are thinking of building something.

Colin's save game doesn't have any AI enabled.

Two things to check, however:  (1) is that sort of reduction present in Simutrans-Standard in any event? Some of Colin's maps are very large, and even Simutrans-Standard might be slow; and (2) do you have other applications running in the background? I find that the fast forward counter speed is often heavily affected by having background applications running at the same time.

I run Colin's save game again with all other applications closed (except file explorer) but this problem still occurs. I suggest you to try it yourself with my latest commits. I can't compare in Simutrans Standard, as Colin's save game is a ST EXP save game.

Instead, I compared using Yoshi's save game, closing all background applications except file explorer : with Simutrans Standards, T is around 9~11 most of the time; with Simutrans Experimental after centralised search has completed, T is around 2~4 most of the time, occasionally goes up to 5~8 briefly. Although it seems that the problem of reduced speed doesn't occur, nevertheless something ought to be done -- ST STD's speed is 2-3 times faster than ST EXP even when ST EXP has path searching completed.

[jamespetts]

Knightly,

thank you for your reply (will reply to your PM when I have a little more time this evening). I am not sure whether stadt_t::step_passagiere() could be made significantly more efficient - most of the extra overhead comes from extra function, especially the alternative destinations code. I cannot currently think of any obvious ways of making it more efficient. I do not even know that it is stadt_t::step_passagiere() that is causing the reduced performance: that is just an educated guess.

Performance is generally acceptable, even if not as good as Simutrans-Standard; my priority at present is preparing a fully compatible pakset (Pak128.Britain-Experimental) to enable the full range of features to be tested/taken advantage of, so this is not something on which I shall be spending a great deal of time at this juncture.

Of course, if you (or anyone else) can find easy ways to optimise the speed, then I can certainly look into those, or if you (or anyone else) puts any optimising improvements that do not detract from function on Github, then I shall gladly incorporate them, but, aside from bug fixes, my focus at present is on a compatible pakset.

Thank you for all your work relating to this :-)