Multi-threading in simulation code

[jamespetts]

Citycars following the route would be a nice addition and provide some additional depth to road transport due to necessity of increasing road capacity to take into account intercity private car traffic. I know there is a looong list of more important projects in line If I remember correctly there was some mechanism implemented to include this feature but the performance impact was considered to big. Would multithreading solve this issue?

Thank you for clarifying the difference.

It is something that I should like to see, too, but the amount of computational effort and coding effort involved would be enormous. Multi-threading can only, at best, multiply computational ability by the number of cores compared to single threading. For the simplest implementation of private car route finding, where each time that a private car is generated, it tries to find a route to its destination and then follows that route, much more than 4 or even 8 times the processing power of a modern powerful CPU running single-threadedly would be needed. A more complex system that might be more efficient has been discussed in detail, but any such system would be fantastically complex to implement.

It may be done one day, but it represents a huge challenge to make this work effectively for large maps (i.e. those many thousands of tiles square and with many hundreds of cities, as the computational effort increases exponentially with size and complexity).

[jamespetts]

I have spent some time to-day re-working the passenger and mail generation, as well as industry, systems to allow for multi-threading of passenger generation when in multi-player mode.

I have implemented a suggestion given by Neroden some years ago to introduce a delay based on the walking/carting/transfer/transshipment time(s) between passengers and goods arriving at a stop and being able to depart from it, between passengers starting out from their origin building and arriving at the origin stop, and between passengers and goods arriving at their destination stop and arriving at their destination building. I have done this by having a vector in each stop (and a further general vector in karte_t for goods/passengers that walk, take a private car, or are hand-carted to their destination and do not go via any stop). During the multi-threaded part, the passengers and goods are added to this vector, together with a timestamp in ticks of the earliest time at which they may be removed. Every step, in a single threaded part of the game, the code iterates through this vector, and finishes the delivery of any passengers or goods that are ready to move on according to their timestamp.

For the pedestrians/private cars, I have made the multi-threaded parts of the code add these objects, not directly to the sync list, where the order would be indeterminate, but to a vector specific to each thread of sync objects. Each (which has a thread local random number generator seed) thread is assigned a sequential thread number when it is first created, and that number is used to index the array of vectors of sync_steppable objects. Then, in a single-threaded part of the code after the passenger generation has finished running, the code iterates through the array of vectors in order so that, no matter in what order that the sync_steppable objects were generated, they are added to the interactive part of the game world in exactly the same order on all clients.

However, at present, I am still getting desyncs when I run with the multi-threaded passenger generation code enabled when in network mode. Testing shows that this does make a significant difference, so I will continue to investigate.

[O01eg]

I think it possible to test if it caused by RNG access races by fixing RNG result to constant value.

[jamespetts]

I have been spending an extremely large amount of time working on this as late. Fixing any network mode desync is exceptionally time-consuming, as it involves repeatedly testing a very large saved game (which takes minutes to load each time). In this instance, the desync occurs only after being connected for about 10 minutes, so each cycle of testing and adjustment is extremely lengthy. This is the reason that I have not had a chance lately to work on code translation or cross-compiling.

I have so far found a problem in the convoy multi-threading code that I had thought was working, but which causes a desync when tested with a different saved game (the difference might be that the one that I am now using has ships; I was previously using one of Rollermaterial's reconstructions of the UK, which has rail and road vehicles, but no ships), which I have not looked into yet, and a consistent problem with the passenger generation multi-threading, which I have narrowed down to the generation of pedestrians and city cars (with both disabled and with the convoy multi-threading disabled, it runs without a desync).

The issue with the generation of pedestrians and city cars I had thought was that, although I had made the order in which they were inserted into the sync list deterministic as described above, sometimes there would be too many objects on a tile for any more pedestrians/city cars to be generated, and which ones would be skipped because of this and which ones would be generated would be indeterministic.

To remedy this, I changed the code (not yet on Github) so as to add the objects to the ground tiles at the same time as they are added to the sync list, single-threadedly in karte_t::step().

Doing this seems to increase the amount of time before a desync occurs, but does not appear to prevent it from happening. I have tried with private car generation disabled but with pedestrians enabled (private cars being the more likely culprit, since they interact with player road vehicles), but the desync still occurs. I have yet to try private cars enabled and pedestrians disabled with this new system, but I had tried both combinations with the previous version (adding the objects to the ground multi-threadedly and adding them to the sync list single threadedly), and that failed (i.e. caused a desync).

Does anyone who is more familiar with the code than I have any idea whether the creation of private car/pedestrian objects themselves (as distinct from adding them to ground tiles or the sync list) changes the game state in any way aside from: (1) the state so far as it relates to those objects themselves; or (2) the random number generator's seed (which is now thread local)?

I should be very grateful for any assistance.

Edit: Oddly, the desync seems not to occur with private cars enabled and pedestrians disabled.

Edit 2: The private cars were not causing desyncs because, in the particular testing scenario that I was using, they were not appearing at all. Using Rollermaterial's saved game (with pedestrians turned back on and private cars set to the default level rather than a very low level as they are in the game as saved), the desync occurs very quickly indeed - more quickly than in the very old saved game that I was using previously. This has made it a little easier to test.

I have also realised that making the RNG seed thread local has meant that the RNG seeds other than on the main thread are not checked in the checklist for mismatches. This leads me to believe that the actual problem could well be outside the realm of pedestrians and private cars themselves, relating more fundamentally to the passenger generation system, but only appearing as a desync (within a reasonable time) when pedestrians and private cars are enabled because any differences between server and client would then change the state of the RNG seed on the main thread much more quickly.

Indeed, I have noticed that there do appear to be differences in the number of transferring passengers as between server and client at King's Cross in Rollermaterial's 1943 saved game arising after a few seconds.

I will therefore have to look with greater precision at the other aspects of multi-threaded passenger generation, which may take some considerable time.

Edit 3:  The problem with the passenger generation code is proving extraordinarily hard to find. With pedestrians and private cars disabled,  I notice that the number of passengers arriving at a station (King's Cross in Rollermaterial's saved game is what I use to test) visibly gets out of sync between client and server, but it takes a long time for this to happen, usually starting with there being 1 more or fewer transferring units on the client or server, and then slowly escalating. Disabling the congestion system has no effect, and I have tried many times without success to find any code in the passenger generation method that has any side effects.

I have also spent some time looking into the convoy multi-threading desync issues, and, again, this proves extremely difficult to understand. On one saved game, a very old game from the Bridgewater-Brunel server, it will desync within a few minutes of connecting if convoy multi-threading is enabled, but will remain connected for a long time if both it and passenger generation multi-threading are disabled. However, on Rollermaterial's saved game, with convoy multi-threading enabled and passenger generation multi-threading disabled, it will stay in sync when run overnight.

I had thought that the difference between them was that the older game had ships and Rollermaterial's game did not, but, checking just now, I see that Rollermaterial's game indeed has not only ships but also aircraft. Disabling the JPS system for ships also made no difference to the desync in the older game. Both games have electricity supply, the desync problem with that having been fixed a long time ago.

Edit 4: I think that I have finally fixed the issue with the passenger generation: the trouble seems to have been that the packets were being added to the lists in a non-deterministic order: the order in which they were taken out of the lists clearly mattered for keeping the game in sync. I have now used the same solution for the halt and world lists as I had used with the pedestrian and private car lists: separate vectors in an array indexed by the thread number, which are then each iterated through in sequence to produce a deterministic output. The code with this fix is now on Github, and the multi-threaded passenger generation is, I think, finally working in network mode.

Thank you all for your patience whilst I have worked to deal with this issue. Hopefully, this will bring great improvements in performance in the future.