Transport Tycoon Forums

Just a small optimisation, that may greatly increase perfomance in huge maps (I tested it with extra-large map patch in 8192x8192 map). Works only in windows, but I'm sure anyone, who may use it in any other OS can easily port it.
I don't know (and don't want to find out) how to public such patches here, I don't want anything, I don't guarantee that this patch will work. I'll likely won't answer on any message, so if you find bugs, fix it by youself.

the problem with threads in this game is determinism. for all possible orders of execution, your algorithm must always result in the same data. otherwise you break multiplayer.

that means, you have to make sure that a thread can never access any data that another parallel thread changed, or will change.

This patch is only for tiles loop, so problem solved very easily: each thread works on it's own part of map, and wait in main thread while all threads finish their part. So, same work done simultaneously in multi-thread. Look at diff file, solution is pretty "deterministic" yet. But anyway, I don't want to play multi-player.

it's not as easy as you think. tile handlers may access other tiles, e.g. for industry or house tiles a NewGRF may check any number of surrounding tiles for various effects. or the tropic saw mill can chop down trees in neighbouring tiles. now the result will be different if that other tile grows a tree in the same tick.

and "i don't play multiplayer" is not an argument. you published this patch, so you must make sure it works for other people, and other people might want to play multiplayer.

Eddi wrote: and "i don't play multiplayer" is not an argument. you published this patch, so you must make sure it works for other people, and other people might want to play multiplayer.

Sorry Eddi but I disagree. He made this patch, that much is true. He is under no obligation to ensure it works on everyone's system, and he is under no obligation to make sure it works in multiplayer. His work ergo he can do what he wants with it.

If he wishes it to ever be included in trunk, well that's a different kettle of fish. But as it stands, no-one can demand anything of him.

SquireJames wrote:If he wishes it to ever be included in trunk, well that's a different kettle of fish.

Yeah, but the next persons that have no real clue about the issues but read "multithreading" will start asking for us to merge it with trunk. After all, the performance is so much better.

I see nothing that makes sure the calls to Random are made in the same order. I know for a fact that Random is called from the tile loop, so if I run with 1 core and you with 16 there will almost certainly be a different order in which the randoms of a tile are executed. Furthermore, since Random can now be called from different threads, it needs to be made multithreading safe by means of mutices and such as now you can trigger cases where thread A reads the state, thread B reads the state, thread A writes the state, thread B writes the state with 2 cores, whereas with one core A reads and writes, and then B reads and writes. As a result, the (random) value B gets differs between the two cases.

To make matters worse, you have the same concurrency issues with things like cargo/passenger generation and moving it to stations.

So, I see now. I guess, it's price for low bandwidth in network game. Interesting, is there any possible solution that may combine benefits of multithreading and deterministic... I should think about it.

Upd:Hm... I think this is possible at the price of twice the memory consuption. The solution is something like "double buffering": all the game data stored twice, the game logic reads the data from the first buffer and writes it to the second buffer at an each odd tick and reads from the second and writes to the first buffer at an each even tick. Calculations are splitted between constant count of threads (4 I suppose), each one have it's own randomizer. It is huge amount of work, but it should be theoretically possible, I think?

(Sory me bad england spik херово, i from ruissa and I really can't understand these 'the', and 'a', and 'do-did-does-done-and-so-on')

aberro wrote:Upd:Hm... I think this is possible at the price of twice the memory consuption. The solution is something like "double buffering": all the game data stored twice, the game logic reads the data from the first buffer and writes it to the second buffer at an each odd tick and reads from the second and writes to the first buffer at an each even tick. Calculations are splitted between constant count of threads (4 I suppose), each one have it's own randomizer. It is huge amount of work, but it should be theoretically possible, I think?

Still doesn't really solve how to handle if the different calculation slices interact. Consider flooding for example: The tile loop handler for water tiles checks if the neighboring tiles should be flooded and if yes, changes them to water tiles. If another thread executes the tile loop for one of these tiles concurrently, maybe a tree tile, which also modified the tile (maybe because the tree died), you'll have a write conflict.

It is of course possible to solve such conflicts with e.g. mutexes or other synchronization primitives, or by storing writes in a temporary buffer that is only applied to the map by the main thread after all calculations have finished. I very much doubt the final resulting code will actually be faster though. In the end you can multi-thread anything with enough synchronization logic, but it just doesn't make sense if the result is slower than a single thread.

Conclusion: Multithreading OpenTTD is certainly not impossible, but fast multithreading likely means completely rewriting most of the game logic and network code.

-- Michael Lutz

Michi_cc wrote:Consider flooding for example: The tile loop handler for water tiles checks if the neighboring tiles should be flooded and if yes, changes them to water tiles. If another thread executes the tile loop for one of these tiles concurrently, maybe a tree tile, which also modified the tile (maybe because the tree died), you'll have a write conflict.
-- Michael Lutz

Each thread processes it's own part of the map, so such conflicts could appear only on borders between a parts. They can be fixed by processing a border tiles after all threads in the main thread.

I think this should happen sooner or later, one way or another. For now I just want to come up with way to do it easily, maybe even do it by myself. And to hear out a such possibly bugs, conflicts and possibilities.