Transport Tycoon Forums

For most players there's no gain in multicore anyways, as the game runs perfectly fine as it is. Only the three people who play the biggest map until it's completely filled will benefit. While one can has as much fun on a smaller 512x512 map, with the added benefit of getting to start a new game once in a while, with no performance problems at all

This discussion reminds me a bit of the "GUI is too small" discussion: people buy the wrong hardware and then complain to somebody who had nothing to do with this decision, demanding the game to be changed to fit their personal equipment.
A lot of people fell for the small size Full HD screen trap. E.g. 1080 pixels on 9 inches high screens. Do the math: a very high resolution, so everything that remains the same size in pixels will be much smaller then when you had only 768 pixels on that same height. Whose fault is that?
Now we're getting the same: people buying a processor with a whopping 4 cores, but an individual clock speed that is much lower than their 3 GHz pentium 4. Do the math again: you can do more things at the same time, but you can't do a single thing quicker. Whose fault is that?
If you answered "my own, not that of the OpenTTD devs, I should have queried what the system requirements of my favourite game are before I purchased this new hardware", then you answered correctly.

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

There's no point in that. By the time that is done, trunk has gained so many features that it will take a long time to port those back. At which time trunk will have gained a lot of new features...

The only way to do this is (I think) is a full feature freeze for one or more years and completely rework the game for multicore. That's not fun, not for the players, and probably not for the devs either (why fix something that isn't broke?).

cogwheel wrote: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.

My OTTD uses much more... Maybe, because I change memory limit in config?!
64 Mb for sprites - is very low limit for now.
But this memory not need to be doubled. This is cache.

So, who says that all memory need to be doubled? It is not necessarly, I think

P.S.: But anyway, adding multythreading is very hard and time-capacious task. Much better idea to give more attention for another improvements. Especially 32 bit graphics, cargo distribution and other.

Rubidium wrote:The pathfinding for trains and road vehicles is, in my last profiles at least, relatively insignificant..

Most of the CPU time is needed to push trains around, though on large maps the tile loop also starts to consume significant amount of CPU (depends on how many trains and other objects are in the map).

From my testing of large map patch I remember that on much larger maps (8192x8192) the tile loop becomes a major problem, eating about 80% of some semi-decent CPU (Core 2 Duo) and making even larger maps (16K x 16K) run at slower speed while eating 100% CPU. While that map size is not usable for anything except perhaps testing (the game needed also 3 GB of RAM and double of that while saving), it can show that some stuff won't scale good to large map sizes (i.e. the tile loop)

I tried running a map 2048x2048 with 2950 trains, 92 RV's, 4 ships and 457 planes for a while

Some interesting stats from that run:
57.67% CallVehicleTicks() - major of CPU is needed to merely push vehicles around
79.55% of that was Train::Tick() - pushing the trains around (calculate speed, see where the tracks are going and then push entire consist, wagon by wagon few pixels forward). The code is already quite optimized and most of the necessary stuff is cached (like total weight of the train). As trains are relatively independent this could be done in parallel, though there are some cases (like pathfinding), that needs to be deterministic, which makes running this in several threads quite a bit more difficult that it seems to be.
5.39% of that is Ship::Tick() (quite lot for only 4 ships, though I used r23992 for this run and I saw some ship PF improvement in the changelog, so perhaps this is now better)
2.41% of that is Aircraft::Tick()
21.27% DrawDirtyBlocks() - this depends heavily on zoom level. Could be better or worse based on how much you are zoomed in/out and how many viewports/minimaps/etc... you have opened
5.32% RunTileLoop() - not so bad, but on large and less crowded maps this percentage gets worse.

So, if all vehicles for which a path needed to be searched would be set aside for path finding when all other were set aside to first get a path and then be processed it could mean a performance improvement for the insane corner cases? A single core could show exactly the same behavior, but then with a single thread (preventing sync problems).

If you'd want to increase performance on insane map sizes, having multiple threads process different pieces of the map could help?

If the game discovers it has more the n vehicles to process it could decides to use multiple cores to process all the vehicles.

Bottom line: keep the types of tasks serialized, but when enough needs to be done of single task type it could perhaps be done by parallel threads, each doing a different chunk of the job.

Threads which are temporarily not needed, could be paused until needed again. This way they do consume some memory, but you don't need to start/stop them all the time and they don't waste cpu cycles. However, I don't know much about the overhead pausing and unpausing threads causes.

Still, it would require an awful lot of work, possibly introducing the mysterious desync from hell bug and what happens when newgrfs come around the corner?

Now, there are things I do not understand of the OpenTTD source code, so there probably are more things then meet the eye at play. Still, these are some raw ideas from my mind.

Thoughts?

You forgot about locking the map between threads, as it changes with blocks getting claimed and freed, and paths being allocated and released again.
Given that you can virtually do nothing without map access, any concurrency that changes the map is pretty much serialized by the locks, and thus completely useless.

The tile loop triggers all kinds of nasty extra things, such as generating cargo, growing house/industries, and so on. The result is that you get all kinds of different issues w.r.t. what is far enough away to not influence anything. Given 64 tile stations station coverage + 2x10 for (max) catchment around that + 2x16 for the maximum industry size means that a roughly 128 tile wide band between "threads" can't be fuly multithreaded, which means that if you have a 512x512 map with 4 threads, that 40% can't be in any of the threads. Result: 0.6*0.25+0.4 = 0.55, so a measily 45% theoretical improvement with 4 seperate cores for 5%, which means you make the game about 2% faster.
Then we're even forgetting the concept of animated tiles. These tiles are added to a list and need to be iterated in the same order. Guess what... they're made animated/added/removed to/from that list during the tile loop.
We should also not forget all other fun that happens, for example accessing memory. That generally does not scale nicely with the number of cores. Given the tile loop goes over the whole map it's safe to assume it doesn't all fit in the CPU's L1/L2 cache, so multiple threads will be asking for the main memory causing the threads to be waiting on eachother. All in all I think you'd be happy if you get more than a 25% improvement on a quad core CPU. So, roughly 1% overall given Bilbo's profile.

Ofcourse you can add them to so list and sort that before inserting/removing. However, you'd need to push stuff into the list in a safe manner which means locking which means synchronisation between the cores and as a result tanking most of the improvements you'll make by running it on multiple cores.

Likewise a massive amount of effort of the vehicle ticks goes into actually moving the vehicles, i.e. updating the vehicle location caches. Again, there's only one vehicle location cache so you need synchronisation. As it happens for every vehicle that is moved that means a lot of synchronisation points and a pretty big chance to end up in a lock convoy which will, if it happens often enough, reduce the performance when multithreading.

Multithreading OpenTTD simply requires rewriting the game logic from scratch with multithreading in mind. As long as nobody dares to do that, the chance of anything significantly useful w.r.t. multithreading OpenTTD beyond what it already does is near zero.

Again I'll mention the multithreading test SmatZ did a while ago. He made the core routines run in several threads without any locking. The result: massive amounts of desyncs, lots of crashes (due to partial updates of structs and so on), a 5-10% decrease in performance for single core and a 0-10% increase in performance for dual core. Now add the locks and extra logic to make everything work right and I fear you won't have much of a performance boost due to multithreading. I'd actually expect worse performance.

This again proves that OpenTTD's game logic is not something that lends itself for scalability w.r.t. multithreading. There are some cases where some improvement can be yielded, but I wouldn't expect anything even close to linearly scaling to the number of cores.

A quick test shows me there are roughly 255.000 'base' tile accessor calls per tick (214.100 GetTileType(), 51.300 TileHeight()). Someone at Google says a mutex taking a lock and unlocking costs 25ns; this excludes the time needed to wait on other threads. Simple math yields that we'd be at ~13ms per tick for locking these two map accessors! Given the game didn't use 100% of a core it didn't take more than 30ms for a tick, so it'd be relatively safe to estimate that locking adds at least a 50% performance penalty.

Given drawing to the GPU and audio already happens in a different thread, I'd guestimate that for it to have benefit on a dual core CPU OpenTTD's multithreading performance needs to scale linearly, which it clearly doesn't. I doubt you'll overcome the performance penalty of the locking on any of the current normal user's systems (i.e. max quad core).

So if it's already multithreaded in these areas, why is multicore support on the rejected features list? I'll withdraw the main thrust of my comment, in that case. It was just very disconcerting to see the entire idea shrugged off, especially now that I find it actually wasn't...

All I know is that when I'm at max zoom, performance tanks on large maps with lots of trains. The only thing causing it to churn is the zoom level which means it's "amount of stuff to render" causing the bottleneck, no?

Technically, OpenTTD is currently multi-core.
However, most users consider 'multi-core' to be distributing the game over several CPU cores, such that each cores takes about the same amount of work. In that sense, it is not multi-core, and never will be.

FooBar wrote:For most players there's no gain in multicore anyways, as the game runs perfectly fine as it is.

Beg to differ.

OpenTTD is being ported to mobile devices.
any mobile device, or netbook (powered by an AMD C or Intel Atom processor), does not have sufficient power to run the any game larger than 128x128 on a single core.
Meaning, as time progresses, and more vehicles are running/flying/floating on the screen, the CPU has a hard time keeping up.

Most Mobile devices like android phones, cheap chinese tablets, and the Raspberry Pi still have but an 800Mhz per thread core.
Raspberry Pi only has one core(what you'd expect for a $35 computer).
Most mobile phones, netbooks and normal tablets are dual thread compatible, meaning a single processor having two cores. Most of them have a 1,2Ghz cpu, dual threaded, and most modern netbooks and tablets and phones are getting to be equipped with slower in speed, but higher in core count, 1Ghz quadcore cpu's.

Currently netbooks are dual processor, dual cores, intel's with Hyperthreading, meaning most intel netbooks sold today already support upto 4 threads at a time, at a speed anywhere between 800Mhz, to 1,4Ghz (intel atom rating is 1,6-1,83Ghz).

I just plan to place some facts here, along with some boring terminology, so forgive me if I elaborate a bit (mostly on an intel atom 1,6Ghz core, as I have most experience with these):

In this case, a processor consists of 2 cores, the primary core, and the secondary, which is the hyper threading core (although names like 'cores' and 'processors' are often intertwined, a processor is a hardware unit, a core is the part that processes a single thread; a processor can have 2 or 4 cores, when they have hyperthreading, it is not exactly an extra core, but at least can be seen as an extension to the core to perform a secondary thread at a lower performace. Because of all the terminology, if a computer has 2 units, with hyperthreading, I will refer to them as 4 cores even if it only has 2, because it can process 4 threads at a time, and so far I'm ashamed to say, I don't really know the correct name of the extension of the primary core, known as the hyperthreading part '?core?').



If an Intel atom processor is rated @1,6Ghz, it performs like a 1,2Ghz desktop cpu at best on a single thread. Since it has HyperThreading, each core will seldom see a 100% utilization on a multi threaded app. Instead of letting each core (of the dual core cpu) process 1 thread, there will be times when windows lets only one core do all the work, part through the primary core, part through the secondary part of the core, the hyperthreading core.

If one core is processing a single thread, it's anywhere between 1 and 1,2Ghz (roughly speaking; let's say 1,2Ghz at best).
If 2 of the primary cores on the Intel atom processor would work simultaneously, the processor would perform like a single core 2,4Ghz desktop processor.
If one core is processing the threads, while the second core is idle, the total speed would be 1,6Ghz at best (that is when the threads are optimized to the core's performance, the 1,2Ghz that the primary core can do, and whatever extra the hyperthreading core can squeeze out of the first core).
If the primary core is processing one thread, while the secondary hyperthreading core is processing the second thread (in case the second processor's primary core already doing something) you'd get similar results, 1,6Ghz at best.
If the hyperthreading core is the sole part processing one stream of data, while the main core is actively doing something else (like virus scan or something other), then the Intel Atom performs like a 400Mhz cpu at worst.
If both primary cores are 100% active, and dual threads are ran off the hyperthreading cores, you'd see a speed anywhere around 400-800Mhz


So, depending on the game, if it has only one thread, depending on the thread allocator within the operating system, it might entirely be that a single thread operates between 400Mhz, to 1,2Ghz on an intel Atom processor rated at 1,6Ghz.
With dual threads, the performance is anywhere between 1,2 and 2,4Ghz at best (though 1,8Ghz is more realistic).

If some program could be optimized for this processor, running 4 threads, 2 heavy ones as primary threads in core 0 and core 2, while the secondary threads are less heavy, running from core 1 and core 3 (the hyperthreading cores) it is theoretically possible to have a performance similar to a 3,2Ghz single core desktop cpu, from an intel atom.
Practically it's impossible to get that performance out of this cpu, because it's very difficult to keep all 4 threads 100% occupied all the time, and to balance the load to 100% all the time.

All this to illustrate the importance of hyperthreading.
True, in desktop area,it makes more sense to run a game from a single thread, without the overhead of multi threading to program.
But even then, large landscapes, hundreds of vehicles, require quite a powerful cpu to keep up.
And even with an intel Core i7, at a single thread, you'll not be able to fast forward a large and complex game fast enough....

as it stands now, it is best to run OpenTTD either dual threaded (for most older phones and netbooks) or tri-thread, cause that's where the market is heading to (quad threads).

I suggest you read Rubidium's response above, which summarised says: "Full Multi-core support would require a major re-write of the game, especially networking, and overall, most users would see very little performance increase"

Lord Aro wrote:I suggest you read Rubidium's response above, which summarised says: "Full Multi-core support would require a major re-write of the game, especially networking, and overall, most users would see very little performance increase"

And if you read my response above, you'll notice that pretty soon most users will see a lot of performance increase, and why!

But this thread is already over a year old since I last visited it, and I understand a rewrite is a lot of work. I'm not asking for better threading, merely pointing out that it does make a difference on mobile platforms, with all the above numbers and data to back it up (at least from Intel Atom's perspective), but I believe similar results are with ARM powered devices.

Besides HT is already implemented and brought forth some improvements!

We all know that having a multithreaded application will potentially make more use of a CPU's (semi)cores. A core with hyperthreading is just somewhere between one and two cores due to the design.

So what's the point in repeating that? It's not going to change the amount of work required to make OpenTTD multithreaded. It's only wasting time of developers that have to read it and reply to it, effectively postponing such change if it would happen at all.

Having said that, OpenTTD is never designed to run on mobile phones. The remarks for OpenTTD on those platforms is either "great" as they can play OpenTTD somewhat, or "very bad" as the interface totally sucks for such devices. So I wouldn't care about multithreadedness of OpenTTD as you'd first have to tackle the more important stuff for mobile devices such as the user interface before bothering with multithreading.

Even then, those fancy mobile devices have a GPU that does fancy stuff fast, however it doesn't do the plain old stuff such as palette animation. So quite a bit of CPU will be needed for that and, believe it or not, the drawing to the video card and palette animation happens in a seperate thread and has shown speed ups of up to nearly 200% on a dual core system.

That would imply that under normal circumstances OpenTTD would use two cores. Then there's a core that can handle audio playback and midi sampling (this really takes loads of CPU with timidity, up to slowing down OpenTTD very noticably on single core systems) and finally there's autosaving that would use the fourth core. And there you have it... all cores of your quad core mobile phone are used by OpenTTD.

As far as I know all vehicles in OpenTTD recalculate their route frequently. They need to calculate the full route but only use a fraction of it before recalculation (which is especially bad for ships). But routes can get cached long (i.e. recalculation only when starting from station/depot, when a tile on a calculated route has changed, the route is blocked (a red signal in five tiles (exactly)) or every 1s when waiting at a red signal).

This has the disadvantage that all improvements to the network will be used with a short delay (in worst case the roundtrip time). At least before 1.0 there were room for such optimisations.

Don't forget about memory bandwidth. OpenTTD has to pump a lot of data around each second. However, some things could be done smarter (to spare memory access, which might improve performance... which really is the core question here.

After having stared at the code and realizing a lot of it could use improvement, but having no clue on how to get it done, I believe some ideas are in order:

• Somewhere else I read most of the engine time is spent is simply moving vehicles around. As the game reserves x tiles ahead, the path is known for vehicles until they finished their reserved tiles. So, why not separate all vehicles into some lists in order to streamline memory access?
  • Vehicles which need a new reservation (and maybe a new path found).
    These need some more time, and are are more memory intensive.
    This includes vehicles which are at signals, leaving depots or manually turned around.
  • Moving vehicles
    These vehicles know their path and only need their speed, direction and reservation (behind them) cleaned up. Most of the time they need to know nothing of the next tile. They just need to know whether they need to break or accelerate. No need to access the map there. Occasionally they need to figure out what the next tile is telling them.
    Now, for multi-threading this, you only need to post the cleaning up of rservations on the other thread after finding paths for all the vehicles.

The net result of this is that the same actions are more organized. Something which you want for multi-threading and memory performance alike.

EDITS: slight correction and some additions

*BUMP*

...to continue on the topic of what might inprove performance.

It puzzles me that things of interest to the rendering engine is kept together with info only of interest to the game logic. Would it be beneficial to separate graphics and game logic information? To some degree there's overlap and I'm not sure about how should be dealt with that.

This mostly applies to vehicles (iirc 100 bytes per vehicle), but there could be other places).

Expresso wrote:It puzzles me that things of interest to the rendering engine is kept together with info only of interest to the game logic. Would it be beneficial to separate graphics and game logic information? To some degree there's overlap and I'm not sure about how should be dealt with that.

What do you gain by splitting it?
I'd say you only introduce extra work to retrieve the graphics. How is that going to speed up things?

This mostly applies to vehicles (iirc 100 bytes per vehicle), but there could be other places).

Unlike vehicles themselves, vehicle data does not move in memory, so size is hardly relevant.

sorry if i necro post,
im new but im wondering...

allot of online games put timestamps on the data the send to prevent desyncing

which has some good and some less good things about it.

the good thing is that desyncing is dealt with

the less good thing is that if someone is a few timestamps behind, the server needs to recalculate the difference in time to make the lagging player catch up with the rest, this is... the right method, in most online games however the server only sends the latest timestamp, which is a window for objects to glitch trough each other.

on the other hand, lots of pc's have multiple cores and.... i don't quite know but if i was member of a group of 4 and i was the boss, i would give every core a different job, 1 for rendering, 1 for 200 moving entities, and 1 for station inventories or so, and the leader compiles it together after checking timestamps.

i might be saying stupid things but ive seen one game that does its calculations similar to this, old game, a turn base strategy that starts an .exe for every side, every turn, thats where i got the idea from

My FX-8150 is very sad to read this topic

@mastamage22:

But you're making assumptions that are not true for OpenTTD.

1. Tagging with time stamp to get an order assumes that you can do independent calculations, ie whether I compute A and then B, or B and then A, makes no difference. This does not hold for vehicles in OpenTTD.

2. Distributing tasks is fine (and is already done), but unless all tasks are somewhat equally big, you won't see a big decrease in time. This is what happens in OpenTTD.
Vehicle movement is THE big thing, and you cannot split it into several jobs, as vehicles influence each other (that is, order of calculation matters here). Also, they need write access to the map for their computations, which means you cannot do more than one such computation at a time. Theoretically you could make a copy of the map, but then you run into trouble with keeping both copies in sync with each other (as well as the problem that no two trains should use the same block, even if both are computed at different maps).

This and other attempts haven been considered, and sometimes even tested in an implementation, without getting anything working in a sufficient useful manner. The program data just doesn't fit the requirements for a good multi-core implementation.

Alberth wrote:@mastamage22:

But you're making assumptions that are not true for OpenTTD.

1. Tagging with time stamp to get an order assumes that you can do independent calculations, ie whether I compute A and then B, or B and then A, makes no difference. This does not hold for vehicles in OpenTTD.

2. Distributing tasks is fine (and is already done), but unless all tasks are somewhat equally big, you won't see a big decrease in time. This is what happens in OpenTTD.
Vehicle movement is THE big thing, and you cannot split it into several jobs, as vehicles influence each other (that is, order of calculation matters here). Also, they need write access to the map for their computations, which means you cannot do more than one such computation at a time. Theoretically you could make a copy of the map, but then you run into trouble with keeping both copies in sync with each other (as well as the problem that no two trains should use the same block, even if both are computed at different maps).

This and other attempts haven been considered, and sometimes even tested in an implementation, without getting anything working in a sufficient useful manner. The program data just doesn't fit the requirements for a good multi-core implementation.

oki, well im not smart when im talking about computer stuff and games.

why i did post it is mainly because the chip producers are experimenting with new cpu types, which are most like have 4-5 times more processing cores.

also, i noticed something funny, windows update always uses core 0 and knocks all other programes to the other cores, windows update couldnt relocate openttd causing it to multiply.

as i said, im stupid if it comes to programming, and personally: why did OS writers not implement a generic multicore support for programmes?