[New release] Simutrans-Experimental 2.7

[jamespetts]

This one is just a minor update with some optimisations kindly suggested by Knightly, as well as merging the latest trunk updates into the code:

CHANGE: Optimised the route searching algorithm for greater speed, as suggested by Knightly.

I should be very grateful for any feedback, not just on the optimisations, but on Simutrans-Experimental and the play experience generally. Thank you for your interest, and in particular to Knightly for his thorough testing and detailed and careful suggestions about code optimisation.

[knightly]

Hi James,

Regarding this part of code :

Code Select Expand


if (previous_connexion != NULL
        && (previous_best_line.is_bound() && previous_best_line == current_connexion->best_line)
        || (previous_best_convoy.is_bound() && previous_best_convoy == current_connexion->best_convoy))
{
    continue;
}


I think the condition can be simplified to
( previous_best_line == current_connexion->best_line && previous_best_convoy == current_connexion->best_convoy )

The key points are, all null quickstone pointers have an internal entry value of 0, and that operator == is overloaded to compare only the equality of the entry values of 2 quickstone pointers.

(previous_connexion != NULL) can be dropped because, in case where there is no previous connexion, both previous_best_line and previous_best_convoy must be null quickstone pointers, and as long as the current_connexion has a defined (i.e. non-null) best_line or best_convoy, the whole expression will fail, and the remaining portion of the iteration will not be skipped.

previous_best_line.is_bound() and previous_best_convoy.is_bound() can be dropped because :
1) in case where one connexion has a defined best_line and the other connexion has a defined best_convoy, the defined best_line and the defined best_convoy are compared to a null pointer respectively and must evaluate to false, thus the remaining portion of the iteration will not be skipped.
2) in case where both connexions have a defined best_line, comparison between 2 null best_convoy pointers is always true, thus the whole expression depends on whether the 2 best_line pointers are the same
3) similar logic as in (2) can be applied to cases where both connexions have a defined best_convoy

Edit :

I have spot another problem :

Code Select Expand


  const uint32 total_halts = alle_haltestellen.get_count();
  const sint32 max_transfers = welt->get_einstellungen()->get_max_transfers();
  const uint32 max_depth = total_halts * max_transfers;
  const uint32 max_iterations = max_depth <= 65535 ? max_depth : 65535;


So, max_iterations is recalculated every time calculate_paths() is called. It is fine if the previous search has completed. But if you are to resume a previously uncompleted search, and if the total number of halts has increased since the last search, max_iterations will contain a number larger than the size of the previously created path_nodes, and there will be the risk of accessing memory beyond the boundary of path_nodes.

Thus, you need to check if previous search is complete [ open_list.empty() ]; if not, set max_iterations to current size of path_nodes.



While there should be room for improving and optimizing the route searching routines, it is an inherent limitation of the Dijkstra's Algorithm that, when the paths are marked stale, and a route from a certain halt to an unreachable destination is searched, the search will take a long time because it searches and creates all available paths and it will continue until either the open_list becomes empty or max_iterations is reached. That is probably the main reason why sometimes the game freezes.

I really like the idea that your implementation allows resumable search as well as search on demand. But search on demand may not always be able to spread the load of searching evenly across the time horizon, as in the case of searching for unreachable destinations.

The only partial solution I can think of is to make more use of resumable search -- you may regularly initiate route search in each step [ possibly called from halt.step() if rerouting of goods will not perform in that step ] provided that the paths are currently stale, but controlling the number of iterations performed in each of such calls. These calls do not have a defined target, but will perform as many iterations as specified before returning halfway through the search. In this way, when an unreachable destination is searched, the extra search time needed will likely be reduced. As I have said, it is just a partial solution, if an unreachable destination is searched immediately after the paths are marked stale, game freezing is still inevitable.

I am not sure if that will work, but there is a need to eliminate, or at least reduce, the game freezing problem.



BTW, is it possible to have individual options to switch on/off (not customize) each non-core ST EXP feature? Revenue and routing system is core, but weight limit and private cars is not. Some players may only want to play with a subset of ST EXP features, so it would be nice if there is an easy way for them to manipulate. Besides, it is easier to test and debug if we can disable certain features which interfere with testing results (e.g. processing speed) or make bugs harder to detect (because you don't know which feature is responsible for the bug/problem). Especially, city roads now have a low weight limit, and many vehicles are "crawling", causing serious overcrowding at the halts.

[jamespetts]

Knightly,

thank you very much for your further suggestions. I have implemented the two initial suggestions (the simpler version of the via test without the bounds checking, and calculating max_iterations only where necessary). I cannot notice a difference in the speed (fast forwarding and looking at the numbers that show how much that things can be speeded up), but, as you point out elsewhere, it might take profiling to spot the difference where it is relatively subtle.

I am not sure about spreading the calculation effort by partly re-calculating each step: I don't think that that can be done. The reason for that is that, once recalculation starts, the closed list has to be cleared, or else checking for whether something is in the closed list will not work. Once the closed list is cleared, every attempted routing from that halt will have to recalculate its path in any event, since the closed list is (deliberately, in order to minimise memory usage and processing time) identical to the cached list of paths. I had considered another technique for spreading the load, which was making the paths of different halts stale at different times, but that might cause problems with inconsistent routes. Suppose that, in January, the best route from A to C was via B, making the path A>B>C. Then suppose that, in February, a direct service between A and B that, in January, had been so slow as to be slower than changing at B, became a great deal faster due to the player's improvement of the rail or road network. If B was to recalculate its paths, but A was not, B might well (if it was significantly closer to A than C) determine that the fastest way of getting to C is to go back via A, and take the newly fast service from there. If A did not recalculate its paths at the same time, then passengers from A going to C would, at A, be given the next transfer of B, but at B, be given the next transfer of A, creating an infinite loop until the paths of A were recalculated. That might happen indirectly with a large circuit as well as directly with an immediate switch-back.

Finally, as to the ability to customise Simutrans-Experimental features, see here for the feature overview to get an idea as to what features can and cannot be altered with changed simuconf.tab settings. In many cases, certain customisation options are equivalent to switching the features off either completely or partly. I will in due course be publishing a Simutrans-Experimental specific set of configuration files and help texts, the configuration files giving detailed information on all the possible settings. As to weight limits, it is not currently possible to customise them, but that is planned for the next version (to allow either no enforcement of weight limits, the current enforcement of weight limits by reduced speed limit, or strict enforcement of weight limits by preventing routing, as you had requested).

[knightly]

I cannot notice a difference in the speed (fast forwarding and looking at the numbers that show how much that things can be speeded up), but, as you point out elsewhere, it might take profiling to spot the difference where it is relatively subtle.

Hey, you are a bit impatient here : First of all, only my first suggestion is an optimisation (albeit minor), while the second one is merely a bug-fix. And remember, many minor optimizations can turn out to be significant when combined together.

I don't think that that can be done. The reason for that is that, once recalculation starts, the closed list has to be cleared, or else checking for whether something is in the closed list will not work. Once the closed list is cleared, every attempted routing from that halt will have to recalculate its path in any event, since the closed list is (deliberately, in order to minimise memory usage and processing time) identical to the cached list of paths.

I guess you have overlooked the condition of initiating such regular, incremental route searching -- they are initiated only when the paths are marked stale, in which case the cached paths have to be abandoned and recalculated anyway. It's just that we try to rebuild the paths as soon as they are stale, and do it step by step, than to wait until a new path is demanded. This can increase the chance of a getting a freshly calculated path without initiating search at the time of request.

I had considered another technique for spreading the load, which was making the paths of different halts stale at different times, but that might cause problems with inconsistent routes.

You are right. Connexions are local and changes can be controlled and limited to what is necessary. But paths are senstive to any change in the global transport network, and any change (however minor it seems to be) to the transport network would require recalculation of all paths in all halts. IMHO, the only sensible way to limit path recalculation is by confining to affected ware type -- this is exactly the approach of gerw's patch regarding the change of routing. Actually, I think it is a good idea to incorporate gerw's patch and adapt it in ST EXP (of course, gerw's route searching and path caching need not be applied) if permission is granted. His patch can reduce connexion recalculations to the minimum, as well as limit rerouting to affected ware types only.

I will in due course be publishing a Simutrans-Experimental specific set of configuration files and help texts, the configuration files giving detailed information on all the possible settings.

Sorry but, can you state clearly in simuconf.tab, which part(s) of the file contain ST EXP specific settings, when you publish your new version? Many thanks!

As to weight limits, it is not currently possible to customise them, but that is planned for the next version (to allow either no enforcement of weight limits, the current enforcement of weight limits by reduced speed limit, or strict enforcement of weight limits by preventing routing, as you had requested).

Thank you very much for your efforts. I will wait for your good news

[jamespetts]

Knightly,

thank you for your reply :-) I didn't mean to sound impatient - I was just relating the results of what I was able to observe so far. You are right, of course, that a series of differences that are non-observable in themselves without profiling can combine together to make a difference that is noticeable.

I see the point about only doing it incrementally when the paths are stale; however, I doubt that that would make a great deal of difference. As can be seen by the drops in performance, with larger networks (with smaller networks it doesn't matter much anyway because the load is minimal), most of the paths are requested most of the time: only a few actual seconds (or one or two game days) after the beginning of the month, the performance is back to what it was just before the end of the month, indicating that most paths that are likely to be requested are requested all the time. The incremental technique called only when the paths are stale, therefore, would not help a great deal, because the normal calling of paths would have all the routes recalculated very soon without the incremental system having done very much. Note that most of my testing is performed on the "Ferndale" saved game, in which everything is connected to everything else with, at most, three or four transfers, and therefore, there are no unreachable destination stops.  As to calculating routes by ware type, that is done already: see the uint8 category variable passed to calculate_paths(uint8 category).

As to simuconf.tab - it will be fully documented, and will make clear what does what. Thank you again for all of your feedback :-)

[knightly]

I didn't mean to sound impatient

Please don't take it so seriously

The incremental technique called only when the paths are stale, therefore, would not help a great deal, because the normal calling of paths would have all the routes recalculated very soon without the incremental system having done very much.

If that's the case, then incremental approach really can't help much. :-\ BTW, why don't you make the paths stale every month, instead of every other month? The convoy and halt statistics are calculated monthly, so it will be more consistent to recalculate path monthly.

As to calculating routes by ware type, that is done already: see the uint8 category variable passed to calculate_paths(uint8 category).

I am not talking about calculating path for a single ware type. What I mean is, when there are changes to halts (e.g. new ware category enabled), lines (e.g. adding/removing stops in schedule) and convoys (e.g. a passenger wagon is added to originally goods-only train), if it is determined that only certain type(s) of goods need recalculation of paths, then processing time could be saved.



Just interested to know :

Code Select Expand


  quickstone_hashtable_tpl<haltestelle_t, connexion*> *connexions;
  quickstone_hashtable_tpl<haltestelle_t, path> *paths;


why connexions is a hashtable with *pointer* to connexion as data, while paths is a hashtable with path *object* as data? Is there any particular reason why one uses pointer and the other uses object?

[mwoodburn81]

James:   minor feature request.

Would it be possible to put the minor experimental version number (2.7 instead of just 2)  in the splash screen and/or window title bar.

I got a cron job that downloads the latest Linux binary, and I would like to be able verify which version it downloaded.

Thanks

~Michael.

[jamespetts]

Hmm - it should give the minor version on the title bar. It certainly does in Windows. I know that I've had difficulties putting it on the splash screen - I'll have a go and see whether I can make the splash screen one work, and see if I can get the minor version to show in the title bar in Linux as well as Windows (which is not terribly easy, since I don't use Linux for development, but I'll have a go!).

Edit: I have found a workaround to the problem that should be available from the next version (3.0) onwards. Thank you for pointing out the issue :-)