Multi-core support please!

[Expresso]

Aside of training people in the art of using colorful language, making openttd use multiple desyncs... errr... multiple threads might turn several developers into mad scientists (especially when hunting for bugs). This, in turn, would result in the "corruption" of openttd, i.e. it'll be turned in a excellent torturing device for whichever poor soul happens to use it.

That being said, there are parts which might benefit greatly from running on their own thread. Saving and loading already happens on its own thread iirc. Another part which might benefit from its own thread is the user interface.

Granted, putting the UI on its own thread might be a lot of work, but at least the UI isn't critical to the game state. Only when the user actually changes something, there would be a need of some sort of synchronizing mechanism (locks, message passing, canary values). Glitches, or lagging behind (preferably not too much, though) are acceptable in the UI, as long as the game state remains consistent.

This is, imho, much less difficult to implement then putting AIs on their own thread. Low-end systems will benefit from this too as the game itself and the UI run independent from each other if this gets done. As a result users of low end systems will be able to play on the bigger maps, without being troubled by an unusable openttd.

[ProDigit]

some member on the forum posted a post that openttd is already multithreaded; is this true?

[DaleStan]

If by "some member" you mean "some OpenTTD developer", then yes. Some OpenTTD developer has posted a post that openttd is already multithreaded.
And, given that it's an OpenTTD developer, I'd tend to believe them.

Mind that you read their posts (there are quite a few of them) carefully to determine what is and isn't multithreaded, of course.

[XeryusTC]

some member on the forum posted a post that openttd is already multithreaded; is this true?

Indeed it is. The saving of a game is done is a seperate thread, everything else runs in the same thread though. But essentially it is multithreaded.

[fonso]

I propose implementing _new_ features with a thread pool pattern like the one I use in cargodist. As long as you make sure you
1. Sync up the threads at defined times
2. copy all needed data on starting and syncing threads
3. save the complete starting state of every thread in the savegame
this is fairly easy to maintain. I do know there is a tradeoff between the time saved by doing things in parallel and the additional time needed for the copying of data and starting of threads. The best approach in my eyes is imlementing features as threadable, but not forcibly running them in a new thread. Cargodist for example can run the linkgraph calculations either in the main thread or in a seperate thread for every component. This could be refined by breaking up the calculation into smaller steps to reduce the lag if the job is run in the main thread. At the moment the jobs are always run in separate threads if threads are available, but other metrics could be applied. Perhaps some framework could be implemented for that. Cargodist already goes a long way with the LinkGraphJob class.

[ProDigit]

some member on the forum posted a post that openttd is already multithreaded; is this true?

Indeed it is. The saving of a game is done is a seperate thread, everything else runs in the same thread though. But essentially it is multithreaded.

Well,that's already something! Does that include autosave?
Because I remember in the old TTD days, that everytime the game autosaves, it would freeze for a couple of seconds.
Perhaps it is just my imagination, but I haven't seen my game freeze when autosaving anymore. It could also be because of better hardware though..

Perhaps some other things can be processed in another thread, like rendering scenery and factories/companies that use animation (like eg: the water, lighttowers, the smoke of the chimney of coal powered electric companies, AI's thoughts (of what to build), the chat log or command window, etc...).

Just an idea.

[planetmaker]

Well,that's already something! Does that include autosave?

Of course. You don't expect to see the save function implemented twice, once with, once without threading?

[Bilbo]

Perhaps some other things can be processed in another thread, like rendering scenery and factories/companies that use animation (like eg: the water, lighttowers, the smoke of the chimney of coal powered electric companies, AI's thoughts (of what to build), the chat log or command window, etc...).

Rendering is fast (when compared to other calculations), especially on large maps, and some systems have limitation, that the program have some "GUI thread" and other threads can't call any GUI functions (Win32 for example). So multithreading won't help here. Same goes for chat log or command window. Having thread for AI would help - I suggested it some time ago, but that would arise many problems when communicating with the "main" thread (main and calculation thread would need to access the same variables, which would mean complicated locking and potentially lot of trouble), so implementation is unlikely in near future.

Good candidates for conversion to multithreadness (as they are theoretically well parallelizable) are tile loop and vehicle movement - there are some issues with pathfinding, GRF callbacks, Random(), multiplayer and lot of other stuff that needs to be solved. This would complicate the code quite a lot (and probably will degrade performance in the singlethreaded case), so I don't expect it to get implemented in near future... devs have already rejected many ideas about adding multithreading to the game :)

[ProDigit]

how about the jukebox?

[peter1138]

Yeah, come on, handling the logic for stopping/starting a music file is surely a candidate for threading!

(Cos the (low CPU!) GUI can't be threaded without major work, and actual playback is already handled externally...)

[Eddi]

you should convert the map into a neuronal network, where each node only deals with a single tile. then you can easily parallelize the nodes

[ProDigit]

you should convert the map into a neuronal network, where each node only deals with a single tile. then you can easily parallelize the nodes

and have what? 524.288 threads?
That'd be drowning the CPU.

I'm sorry if the idea of running the jukebox in a parallel thread seemed silly. I had no idea it already ran in a separate thread.
I was just trying to suggest an idea.

[CommanderZ]

and have what? 524.288 threads?
That'd be drowning the CPU.

When OTTD's map array is converted to neurone network, CPUs will have no trouble dealing with that many threads

[cogwheel]

I realize this is a pretty big necro, but I think it's time to revisit this question. Today's computers are much better equipped to handle the demands of multithreading. Early in this thread the idea of doubling memory usage was essentially laughed off as a ridiculous idea. I think that's a complete non sequitur now.

With the current openttdcoop game loaded, OpenTTD is using 74 MB on win7 64-bit. That's with nearly 3000 trains and nearly 1.5m population in a single city. Another of the openttdcoop games at 1024x1024 used around 85MB. With memory capacities measured in ones to tens of gigabytes, my answer is YES ABSOLUTELY memory usage should be doubled in order to take advantage of many-core processors.

Between SIMD and manycore standard these days (even on mobiles!), there really isn't anything to worry about in that regard. The things that must stay synced can be synchronous. Everything else SHOULDN'T be. Period. All rendering should be in a separate thread. Sound should be in a separate thread. Hell, the UI could be in a separate thread.

I am nowhere near qualified to volunteer for the job, or even to judge how difficult these things might be to accomplish. But at the very least they need to be removed from the rejected features lists.

[kamnet]

You're assuming that everybody is playing on these newest computers.

[Rubidium]

All rendering should be in a separate thread. Sound should be in a separate thread.

Regarding the former: all rendering that does not depend on the game state is already in a seperate thread on the maintained platforms (we did see significant speed improvements in a fairly empty fast forward scenario). We can rewrite OpenTTD to render from a clone of the game state, but autosave starting is noticable and rendering would then do exactly what autosave does: clone the game state and work on that. So, yes we can make rendering be done in a completely seperate thread, but it is slower. The actual sound and music playback already happens in another thread.

Regardless: trains depend on other trains w.r.t. route finding and blocking eachothers paths. Likewise road vehicles depend on train w.r.t. level crossings. All vehicles depend on eachother for the vehicle location caches. This means that ships and aircraft can (relatively) easily be split off, but they are least used and least processor intensive and you'd still need to do an awful lot of locking for the vehicle location cache which might even be worse over all.

Similarly someone made these vehicle parts of OpenTTD multithreaded a while back by a hack. The results were that single core lost a few percent of performance and multicore got a whopping 10% speedup. However, since there was no locking it crashed all the time due to invalid game states. Adding the locking would probably kill much if not all of the already insignificant 10%.

Finally there's a small feature called multiplayer. This requires all clients and the server to do exactly the same. If you start with multithreading, then you will easily end up with stuff being executed in different orders and as such different game states and the inevitable desyncs.

[Transportman]

Finally there's a small feature called multiplayer. This requires all clients and the server to do exactly the same. If you start with multithreading, then you will easily end up with stuff being executed in different orders and as such different game states and the inevitable desyncs.

What I am going to say might be very stupid (no code experience), but isn't it possible to do all pathfinding calculations on the server and send those results to the clients? Then the client doesn't have to do those calculations anymore and just deal with the results the server sends. Or does that generate a lot of network traffic/other problems?

[Eddi]

Since OpenTTD has a very large game state, this would create very heavy bandwidth usage, and effectively would block out all people with lower bandwidth from playing multiplayer at all.

[Expresso]

OpenTTD is a game in which nearly everything is dynamic i.e. no assumptions can be made about the state of anything in the game. That makes that OpenTTD has to process a lot of data every second.

When a save occurs the game has to be paused (otherwise the saved data will be inconsistent) and all the data has to be copied (this is the pause when an autosave happens), compressed and stored on disk.

OpenTTD is designed in a way which favors a single core. If you design such a game to favor multiple cores, the code would be radically different.

Management of game integrity and time needs to change completely for multi-threading to work properly, something I'm not sure the devs are willing to invest the time in.

You see, action A needs to come before action B, which in turn must come before action C. Now, how do you make sure action A, B and C happen sequentially while they have been processed in parallel? Of course you don't want action C to wait for action A and B when it's done first, because you want to continue with action D.

If OpenTTD was coded from the ground up with multi threading in mind, no problem. Only problem is that OpenTTD is designed with a single core in mind. If you want to have multiple threads properly handling things and network consistency, expect it to take a few years.

However, if this is done properly performance could improve dramatically... it is difficult and time consuming, though. Better to spend time on interesting new features and fixing bugs then to get the game to do multiple cores.

Perhaps somebody could start coding OpenTTD (say for version 2.0) with multiple cores in mind?

As for doing pathfinding on the server: are you insane? The amount of data needed to be sent over the network would explode to the point that even glass fiber connections would struggle.

[Rubidium]

The pathfinding for trains and road vehicles is, in my last profiles at least, relatively insignificant. There are things that waste more time. The following are the top 10 most consuming methods in a 'random' game (PSG132 final). This game had roughly 600 trains, 600 road vehicles, 60 ships and 30 aircraft.

Code: Select all

    %  name    
23.83  DeterministicSpriteGroup::Resolve(ResolverObject*) const
 7.99  VehicleGetVariable(Vehicle*, ResolverObject const*, unsigned char, unsigned int, bool*)
 3.59  Md5::Process(unsigned char const*)
 3.26  Vehicle::ShowVisualEffect() const
 2.81  GetNewVehiclePos(Vehicle const*)
 2.62  GetGlobalVariable(unsigned char, unsigned int*, GRFFile const*)
 2.43  GetCustomEngineSprite(unsigned short, Vehicle const*, Direction, EngineImageType)
 2.36  RealSpriteGroup::~RealSpriteGroup()
 2.26  Blitter_8bppOptimized::Draw(Blitter::BlitterParams*, BlitterMode, ZoomLevel)
 2.20  TrainLocoHandler(Train*, bool)

In total they represent 50% of OpenTTD's running time. I ran this for about a minute which is why MD5 processing is still in the list, which is done when scanning the NewGRFs. Roughly 4% was spent on scanning NewGRFs. All pathfinding combined takes about 0.25%!

The updating of the state of the game takes 80%. Another 5% is from starting OpenTTD, meaning that the actual drawing takes 15% of the CPU time. Most of this 15% is spent pushing graphics to the video card, which is done in a seperate thread so you won't bother OpenTTD's game loop.

In this game roughly 50% of CPU is spent determining the (new) image to draw for the vehicles by querying the NewGRF. Improving that is where you can get a significant speed improvement. Not by splitting pathfinding or drawing or vehicle moving to a seperate threads.

So please, before saying X or Y is slow, please do some profiling to at least get an idea what is actually slow and what isn't.