The passenger-generation branch and multi-threading

[jamespetts]

On the passenger-generation branch of my Github repository, I am working on some code to change the way in which passenger generation works. One of the features of this is to remove passenger generation from the cities and make it a function of the whole world. Instead of passengers being generated from buildings chosen at random from a city's building list, there are now new world building lists for passenger origins, commuter targets, visitor targets and mail origins and destinations. Like the existing city lists, these are weighted vectors, and origins and destinations are both chosen at (weighted) random from the lists in much the same way as they are currently chosen from the city lists. I have had this system working for a while, and it seems to work acceptably in principle, although I have not fully tested it yet.

However, there is an issue with loading the lists from a saved game. Just as with the city lists, when loading in a multi-threaded environment, it is essential that the buildings are all added to the list in the same order to avoid desynchronisation in network mode. (This ordering is achieved without effort in single-threaded code where the code path is determinate). I have copied and adapted the code necessary to make this work from the code used in the city building lists. It works, but the trouble is that it is very slow - much slower than loading the city building lists. The reason for that is no doubt that, although there are far fewer of the lists, four compared to over four hundred city lists in the saved game from the Bridgewater-Brunel server, each list is much longer, and the "insert_ordered" method, I imagine, gets exponentially slower the longer the list.

The effect of all this is that loading a large saved game with many buildings (the saved game from the Bridgewater-Brunel server) is many times slower in multi-threaded mode than in single threaded mode, which largely defeats the point of multi-threading. (The game runs at acceptable speed once it has loaded).

I should be very grateful for advice on this. Is there a container class available out there somewhere with a compatible open source licence that allows for the same function as our weighted vector but with a faster method for inserting the items in order? Alternatively, would it be better to remove that part of the loading process (called from laden_abschliessen()) from multi-threading entirely? If so, since I do not know a great deal about how the multi-threading code works, I should be very grateful for some guidance on how best to force this part of the code to run single-threaded (although I suppose that all the insertions could run in their own thread, which need not be the main thread?).

Any thoughts on the topic would be much appreciated.

[kierongreen]

Sometimes multithreading is just not the answer. I spent most of Saturday trying to multithread routing. Again, that has to be done in a consistent way, and again, making sure threads were synchronised created so much overhead it ended up being slower. Laden abschliessen is run after all the objects have been loaded from a file by looping over all plans - there should be a single threaded variant present of this loop alongside the multithreaded version so just delete the multithreaded one.

[jamespetts]

Thank you for your reply - most helpful.

Hmm - would that not end up taking all of laden_abschliessen() out of multi-threading, however? All that would be needed to be removed from its scope is the part where the buildings are added to the world list.

[kierongreen]

That's the easiest course of action, and really the only one unless you want to introduce laden abschliessen_single and laden abschliessen_multi for every object in the game (looping first over single with one thread, then the multithread ones after with several threads)

[jamespetts]

I see. How significant is the speed advantage that multi-threading gives to laden_abschliessen() in particular? Might there be some advantage in having a separate, single threaded, method for adding buildings to the world list from the city lists called immediately after  laden_abschliessen() is complete, leaving  laden_abschliessen() multi-threaded?

[kierongreen]

That's what I suggested. Alternatively taking laden_abscliessen out of multithreading altogether is an option. Advantage of multithreading depends on number of cores - on my system with 4 virtual cores (2 real) I get about a 2.5x speedup with 4 threads, 1.5x speedup with 2 threads. When I helped introduce multithreading I tried targeting sections of code that took a long time to execute - loading, updating images (e.g. to/from underground mode) and rotation.

[jamespetts]

Thank you for the help with this - I have now implemented what you have suggested. Incidentally, in going through the code, I have identified a possible optimisation for Standard: currently, as I understand it, buildings are inserted into the city lists in order whenever a game is multi-threaded. However, this is unnecessary for a single-player multi-threaded game, as the order does not matter provided that, in a network game, the order is the same on all clients. I suggest the following alteration to gebaeude.cc in Standard therefore:

Code Select Expand


#if MULTI_THREAD>1
pthread_mutex_lock( &add_to_city_mutex );
#endif
- our_city->add_gebaeude_to_stadt(this, true);
+ our_city->add_gebaeude_to_stadt(this, umgebung_t::networkmode);
#if MULTI_THREAD>1
pthread_mutex_unlock( &add_to_city_mutex );
#endif


[kierongreen]

Thanks for the suggestion. Will think about benefits of potential time saving vs making differences between single and multiplayer.

[jamespetts]

Let me know what you think about that - I should be interested in any views, especially as to what the disadvantages are of such distinctions.

[kierongreen]

Disadvantage is potentially different behaviour in single vs multiplayer for possibly not much speedup. That's what it comes down to.

[jamespetts]

Is the difference in behaviour likely to be significant? As I understand it, the only differences will be within the range of what occurs randomly in any event (in other words, one random thing occurring instead of another).

[TurfIt]

I'm not sure why you're seeing such a slowdown multi vs single threaded here. The mutex makes it such that only a single thread is accessing the building list at once anyways; Even  though there's multiple building lists, there's still only a global mutex (could change to per list mutexes...) which should be similar to having a global list. You should be seeing multi taking the same time as single for this. Possibly single just happens to be rebuilding the list in a way that minimizes the amount of reweighting/moving passes in the vector. i.e. It happens to always insert near the end of the vector making it perform more like the single player append operation.

I rather doubt you'll find a faster insert to a weighted vector out there. It's already doing a binary search for where to insert, and then inserting which is the real problem shuffling everything to make room. If inserting is too slow, remove the insert! How about appending in laden_abs, and then sorting the list afterwards?


---
IMHO differences between multiplayer and single shouldn't be introduced - especially for such a trivial potential speedup. Right now you can continue a multiplayer game singleplayer if desired.

[jamespetts]

The slowdown occurred as a result of using "insert_ordered" on a list comprising all the buildings in a very, very large map many times over. Using "append" is much faster. (Using "append_unique" was also very slow, but testing showed that this was not necessary).

As to differences between multi-player and single player; how would the change that I suggest above stop players continuing a multi-player game in single player mode?

[TurfIt]

Of course insert_ordered is much slower than append, it's doing much more work. I'd read the original post as it was calling this multithtreaded vs single was causing you a slowdown, if not..

The change above wouldn't stop someone from continuing single player, but would result in different things happening given the same random seed. IMO you should be able to continue exactly the same.

[prissi]

The random seed is changed anyway after reloading a game. So you usually do not get the same random events twice. Then it would make sense to remove.