The International Simutrans Forum

Simutrans Extended => Simutrans-Extended bug reports => Simutrans-Extended development => Simutrans-Extended closed bug reports => Topic started by: DrSuperGood on September 10, 2018, 01:22:58 AM

Title: Bug: Changing a passenger line schedule deletes all air passenger routing info.
Post by: DrSuperGood on September 10, 2018, 01:22:58 AM
Fairly simple one that will probably be notoriously hard to track down...

Under some conditions some passenger links between stops will not be created making it function as if no passenger link exists between the stops despite there being a fully functional passenger line. The conditions to cause this either involve save/load cycling or modifying unrelated lines involving one of the stops. Symptoms are basically that the link will sometimes appear and other times not.

On the server I am frequently observing this with my aircraft routes. For example...
"(1731) Line" : Yerington International <-> Cagbury International Airport
This is a premium passenger service running high speed aircraft connecting a remote island chain with the main land. That has been operating for several months. In both airports under Details there should be a passenger link with each other reflecting that passengers can route via the premium air service. However at the time of writing this post no such link is listed for either airport.

This is not the only passenger air line that seems effected by this. It also happens sporadically for others.

It appears to be limited to passengers only. Mail is correctly listed and appears to function reliably.

EDIT:
This is a lot worse than first thought. Changing the schedule for any passenger line will delete all routing information from all airports, including those for lines of other players. This makes operating passenger aircraft lines reliably impossible as seldom will passengers even try to use the lines.

To recreate...
The results will not happen if paused, but one can change the schedule while paused and they will happen once unpaused.

Save/load cycling rebuilds the air line passenger routing information. This is likely why this bug has gone undetected for weeks since this happens fairly frequently on the server.
Title: Re: Bug: Changing a passenger line schedule deletes all air passenger routing info.
Post by: jamespetts on September 10, 2018, 07:27:05 PM
I am currently investigating this. What appears to happen is that the connexion information is lost when the path explorer is first set to run, but is eventually restored when the path explorer completes its work (which is why a load/save cycle will restore these data, as a path explorer run is completed on loading).
Title: Re: Bug: Changing a passenger line schedule deletes all air passenger routing info.
Post by: jamespetts on September 10, 2018, 08:54:19 PM
This is indeed difficult to isolate effectively. I have created a small test game in which I can reproduce this: the connexions for air traffic disappear when the path explorer is invoked, only to reappear the next time that it is invoked. I have not yet found which specific piece of code in the path explorer actually triggers this. I have also not found any code in the path explorer, nor in the halts (which store the connexions data) which distinguishes between air and other types of transport.

My testing has been very severely hampered by failing hardware on my own computer, which seems to be resulting in blue screen errors every 15-30 minutes this evening. It is impossible to continue testing in these circumstances. It is difficult to tell at this juncture whether the problem might abate in the future (as it has in the past), or whether I will need to replace the computer fully before I am able to resume any intensive work of the sort that fixing this will entail.

If anyone would like to look into what might be causing this in the meantime, that would be very helpful, as this is an especially bizarre and mysterious bug, relating as it does specifically to air transport but originating in a part of the code that has no algorithm that appears capable of distinguishing air transport from any other sort.
Title: Re: Bug: Changing a passenger line schedule deletes all air passenger routing info.
Post by: DrSuperGood on September 11, 2018, 03:03:46 AM
QuoteIf anyone would like to look into what might be causing this in the meantime, that would be very helpful, as this is an especially bizarre and mysterious bug, relating as it does specifically to air transport but originating in a part of the code that has no algorithm that appears capable of distinguishing air transport from any other sort.
I have seen it happen to other types of transport and I think I even reported it somewhere in the past. However as can been seen the other types of transport are nowhere near as bad and usually eventually fixed themselves in a way that did not necessitate looking further into.

Could it be related to passenger classes? Air generally uses very high and other more premium classes which generate small traffic. On the other hand most of my other passenger lines offer some sort of very low class option so generate huge quantities of passenger traffic.

QuoteIt is difficult to tell at this juncture whether the problem might abate in the future (as it has in the past), or whether I will need to replace the computer fully before I am able to resume any intensive work of the sort that fixing this will entail.
Usually caused by the GPU or PSU. Of course it might not be the case just statistically over the last 15 years I have had many of those things fail. PSU is usually the main electrolytic capacitors reaching end of life causing unreliable voltage levels on the rails which fall below the stable operating voltage of some components causing undefined behaviour which eventually triggers an OS BSoD. GPU I am guessing it is the power circuitry for similar reasons which manifest in any of graphical glitches to eventual driver crashes and if the OS cannot restart the driver it will BSoD.

All BSoD generate some sort of error descriptor which can be viewed with blue screen viewer and such. GPU caused BSoD would be from graphic driver related errors. Running a memory test can rule out main memory being the cause.
Title: Re: Bug: Changing a passenger line schedule deletes all air passenger routing info.
Post by: jamespetts on March 10, 2019, 02:14:44 PM
This seems to be the next major critical bug for serious work: initial work on this, demonstrating that it can be reproduced but is very difficult to track down, was interrupted by the even more critical loss of synchronisation bug, now fixed.

First of all, can anyone confirm that this is still an issue?
Title: Re: Bug: Changing a passenger line schedule deletes all air passenger routing info.
Post by: jamespetts on March 16, 2019, 01:20:57 AM
I have been able to reproduce this in my original testing save.

The problem appears to be that higher class routing data data are overwritten in swap_connexions in phase 3 of the path explorer and for some reason sometimes not restored when phase 3 is re-run with the higher class.

Running swap_connexions with only the highest class solves this problem but creates another, which is that passengers will attempt to route using connexions that are too expensive for them (but they will not board the convoys).

This will need furhter and more detailed investigation, as this is a very complex area of the code.
Title: Re: Bug: Changing a passenger line schedule deletes all air passenger routing info.
Post by: DrSuperGood on March 16, 2019, 02:16:50 AM
Why does it only effect aircraft? Or have you managed to get it to effect other modes of transport?
Title: Re: Bug: Changing a passenger line schedule deletes all air passenger routing info.
Post by: jamespetts on March 16, 2019, 11:45:42 AM
The effect appears to be class linked, and aircraft are always set to the "very high" class. When the class is reduced, the effect disappears.
Title: Re: Bug: Changing a passenger line schedule deletes all air passenger routing info.
Post by: jamespetts on March 16, 2019, 01:54:42 PM
I have pushed what is at least an interim fix for this.

The problem is as follows: the halts do not store class data for their connexions. This relies on the path explorer going through all classes in sequence. However, it is possible for the path explorer to be asked to refresh all classes while it is part way through refreshing the classes. That will make it refresh the classes that it has started or completed refreshing again once it has completed the refresh, but it will not refresh again the classes that it had not started to refresh. This means that, on the second run, some classes get refreshed and some do not. Because classes are refreshed in ascending order, it is often the case that the higher classes are not refreshed on the second run.

Because class data are not stored in the halts, when a lower class refreshes, connexion data for the higher class are overwritten. This is not rectified by a subsequent pass of the higher class refresh as is intended because in the situation described above there is no higher class refresh (until much later when the whole refresh cycle is run again).

The current interim fix to this that I have just pushed is to re-request a refresh for all higher classes when any lower class is refreshed. This has the potential to make the path explorer less efficient in some cases. This also still allows for the erasure of higher class data temporarily as before, but it is rectified much more quickly.

The only long term fix for this of which I can think is to store class data in the halts' connexions field. However, this has the potential significantly to increase memory consumption by multiplying by five all passenger connexion data and by two all mail connexion data. The Bridgewater-Brunel server is already struggling with the amount of memory being consumed by the game.

Also, this would involve quite a major rewrite of a significant part of the code, which would be very time consuming and would be liable to lead to a considerable number of new bugs which could potentially take many months to resolve, during which time other development work (including critical balancing work and fixing other bugs) would be significantly impacted.

If anyone who has or would care to acquire a reasonable understanding of how the path explorer code works has any better ideas of how to solve this issue more efficiently, that would be much appreciated.

In the meantime, any feedback on how the fix that I have implemented is working in the next nightly build would also be useful.
Title: Re: Bug: Changing a passenger line schedule deletes all air passenger routing info.
Post by: ACarlotti on March 16, 2019, 04:34:01 PM
I'll just briefly note that I'm interested in looking into (and hopefully improving) the path explorer, but I probably won't find time to do so for a while.
Title: Re: Bug: Changing a passenger line schedule deletes all air passenger routing info.
Post by: jamespetts on March 16, 2019, 07:03:12 PM
Quote from: ACarlotti on March 16, 2019, 04:34:01 PM
I'll just briefly note that I'm interested in looking into (and hopefully improving) the path explorer, but I probably won't find time to do so for a while.

That is very interesting.

As you may know, the path explorer was written many years ago by a very talented programmer who retired from Simutrans development not long after it was completed, although he did do some work to maintain it for a while. It was a great improvement on the much slower system that I had earlier written.

Over the years, additional features have been added to this system by me and, not having the original programmer's skill, probably not as optimally as he would have written them. It would be interesting to see what further refinements might be wrought upon this system to bring it up to date with the current features and some future planned features, including a system in which some passengers take into account comfort when routing, as discussed here (https://forum.simutrans.com/index.php/topic,8172.0.html).

Incidentally, I should note that by far and away the biggest use of computational resources in larger games are hashtable lookups for the routing data. If there were a way of making the Simutrans hashtable more efficient (and I believe that the current implementation just iterates through the whole dataset until it finds a matching key), this would have the potential to make a very great difference to performance.
Title: Re: Bug: Changing a passenger line schedule deletes all air passenger routing info.
Post by: ACarlotti on March 17, 2019, 01:42:13 AM
Quote from: jamespetts on March 16, 2019, 07:03:12 PMIf there were a way of making the Simutrans hashtable more efficient (and I believe that the current implementation just iterates through the whole dataset until it finds a matching key), this would have the potential to make a very great difference to performance.

My first thought was "That's not how hash tables are supposed to work". Having had a quick look at the code, I can see that that isn't quite how the code currently works. In fact, it seems to uses 101 'bags', each of which contains a linked list of elements, sorted by key. Which is still not how their supposed to work.

Effectively, this might reduce search time by a constant factor of up to about 100 compared to just using a sorted linked list, which presumably was adequate on smaller maps. But hash tables (when implemented properly) should run in O(1) time (not O(n) time as I think the Simutrans hash tables do at present).

I'm going to put implementing proper hash tables near the top of my todo list, for both Standard and Extended.
Title: Re: Bug: Changing a passenger line schedule deletes all air passenger routing info.
Post by: jamespetts on March 17, 2019, 01:48:19 AM
Quote from: ACarlotti on March 17, 2019, 01:42:13 AM
My first thought was "That's not how hash tables are supposed to work". Having had a quick look at the code, I can see that that isn't quite how the code currently works. In fact, it seems to uses 101 'bags', each of which contains a linked list of elements, sorted by key. Which is still not how their supposed to work.

Effectively, this might reduce search time by a constant factor of up to about 100 compared to just using a sorted linked list, which presumably was adequate on smaller maps. But hash tables (when implemented properly) should run in O(1) time (not O(n) time as I think the Simutrans hash tables do at present).

I'm going to put implementing proper hash tables near the top of my todo list, for both Standard and Extended.

I did not work out fully the workings of the code, but the hashtable running in O(n) (even a 100th of the O(n) of a vector of the same size) is really not ideal! Dealing with this might make a major difference to the performance with larger games.

One question is whether it is sensible to continue using the Simutrans hashtable or whether we should migrate to std::unordered_map now that we are standardising on using modern(ish) compilers capable of at least C++11 (rather than pre-C++98 as was once the standard). There is much to be said for not reinventing the wheel.
Title: Re: Bug: Changing a passenger line schedule deletes all air passenger routing info.
Post by: DrSuperGood on March 17, 2019, 05:40:17 AM
You can try benchmarking the existing implementation against the C++ standard one. If a performance gain is observed then swap over to the standard one rather than trying to invent your own. Later down the line one can try to make a more efficient/targeted implementation but the standard one might be good enough for an immediate improvement.
Title: Re: Bug: Changing a passenger line schedule deletes all air passenger routing info.
Post by: jamespetts on April 09, 2019, 10:40:39 PM
The path explorer enhancements over the week-end achieved what I believe is a full fix to this in place of the workaround that had been implemented previously. I should be grateful if anyone could confirm that this has been dealt with fully or whether any vestige of this issue remains.