News:

Simutrans Wiki Manual
The official on-line manual for Simutrans. Read and contribute.

Bug: Changing a passenger line schedule deletes all air passenger routing info.

Started by DrSuperGood, September 10, 2018, 01:22:58 AM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

DrSuperGood

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...

  • Load server game. Online or offline does not matter as the issue is completely re-creatable.
  • Look at routing information for an airport. I recommend Yerington International @3576,2755 as it has both internal and external destination passenger air lines operating from it.
  • Confirm passenger routing entries exist using the Details view of Yerington International for both Cagbury International Airport and Millstead Airport and leave the Details window open to watch for changes.
  • Can also confirm inverse entries on the related airports exist if desired.
  • Select Royal Western company and open the line manager.
  • Modify any passenger line. For example change the line frequency of the only tram line from 40 to 41. This line is not directly connected to any airport.
  • Almost immediatly should both the above mentioned passenger routing entries disappear from details view. Passengers will no longer accumulate at any airport for any air passenger route. Any passengers that have already accumulated will still wait for their intended aircraft, however no more will come.
  • All airports can be checked and all airports will be missing their passenger routing entries for air lines.
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.

jamespetts

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).
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

jamespetts

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.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

DrSuperGood

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.

jamespetts

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?
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

jamespetts

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.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

DrSuperGood

Why does it only effect aircraft? Or have you managed to get it to effect other modes of transport?

jamespetts

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.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

jamespetts

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.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

ACarlotti

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.

jamespetts

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.

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.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

ACarlotti

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.

jamespetts

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.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

DrSuperGood

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.

jamespetts

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.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.