Multithreading patch

Forum for technical discussions regarding development. If you have a general suggestion, problem or comment, please use one of the other forums.

Moderator: OpenTTD Developers

Post Reply
aberro
Engineer
Engineer
Posts: 64
Joined: 20 May 2013 20:20

Multithreading patch

Post by aberro »

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.
Attachments
multithreading_patch.diff
(6.59 KiB) Downloaded 242 times
Eddi
Tycoon
Tycoon
Posts: 8258
Joined: 17 Jan 2007 00:14

Re: Multithreading patch

Post by Eddi »

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.
aberro
Engineer
Engineer
Posts: 64
Joined: 20 May 2013 20:20

Re: Multithreading patch

Post by aberro »

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.
Eddi
Tycoon
Tycoon
Posts: 8258
Joined: 17 Jan 2007 00:14

Re: Multithreading patch

Post by Eddi »

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.
User avatar
SquireJames
Tycoon
Tycoon
Posts: 1863
Joined: 07 Aug 2004 11:56
Skype: squirejames5
Location: Stoke-on-Trent
Contact:

Re: Multithreading patch

Post by SquireJames »

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.
Image
Rubidium
OpenTTD Developer
OpenTTD Developer
Posts: 3815
Joined: 09 Feb 2006 19:15

Re: Multithreading patch

Post by Rubidium »

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.
aberro
Engineer
Engineer
Posts: 64
Joined: 20 May 2013 20:20

Re: Multithreading patch

Post by aberro »

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')
Michi_cc
OpenTTD Developer
OpenTTD Developer
Posts: 619
Joined: 14 Jun 2004 23:27
Location: Berlin, Germany
Contact:

Re: Multithreading patch

Post by Michi_cc »

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
aberro
Engineer
Engineer
Posts: 64
Joined: 20 May 2013 20:20

Re: Multithreading patch

Post by aberro »

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

Return to “OpenTTD Development”

Who is online

Users browsing this forum: No registered users and 7 guests