Multi-core support please!

[ProDigit]

Unless YAPF does some magic stuff there, I find it very slow for ships, same for NPF. The problem is that unlike other vehicles, ships can take an ultra mega gazillion number of routes, since every water tile is like a tile with rails is every possible direction. Now go and calculate the best path through possibly a few million tiles in big maps. Good luck. The old pathfinder just gets a simple route there, yes, it can be VERY VERY bad, but it's done very fast.

I didn't read much about these algorythms, but I'm just saying, what the game does... And the fact is, that the YAPF works a lot faster for me. But it's probably because of the low sea-level, I'm using in most of the maps...

Unless you enable the 32bpp blitters or set the color to over 8bpp, OTTD, in full-screen, switches to 8bpp, and that is MUCH faster than doing it in 32bpp, which in windowed mode isn't possible. Now, what slows this further down on both, is the full animation as palette cycling isn't that fast currently. Just disable it, you won't see everything so smooth and water won't animate, but it will run a LOT faster.

About the 32bpp, I have 8bpp in both, windowed and full-screen mode and the game runs the same in both modes. I used to have 32bpp in windowed mode, but the game was running terribly slow, so I switched to 8bpp and everything's fine, even with a windows resolution 1600x1200 (fact is, that the resolution hasn't got almost any effect on the performance, the game runs the same in 640x480 as it does in 2048x1536). And as far as I've tested it, the full animation feature has nothing to do with game performance whatsoever, it doesn't matter, how many animated things there are at the same time on the screen, or in the map overall... I do have a good graphic card, GeForce 8800 GTX (and yet I'm playing this 15-year old game! ), but of course I'm aware, that OTTD performance has nothing to do with graphic accelerators...

Maybe you have diffierent experience with what helps and what doesn't, but this is how my OpenTTD on my PC works and if someone has performance problems with a game filled with ships, "maybe this will help", as I stated in the very beginning...

My game runs fine as well, but I've noticed, that running the game fullscreen, and then Fast-Forwarding (FF) it, actually makes the game like 1.1 or 1.2x faster.. I don't know why but if I run it in windowed mode, the game goes.. well.. at least 5 to 7 times faster (in FF).
I think somewhere there is something right about what he says, but I can't back it up other then in windowed mode my FF goes faster then in fullscreen.

[Belgabor]

Something that struck my interest:
Has anyone with a multi-core system (I don't have one) tried if it it beneficial to run a dedicated server and play a one-pc "network" game? Theoretically the server and client would be scheduled on different cores and it should run better than playing "normally".

[Roujin]

The client still has to perform everything, like in the single player game. Plus a bit overhead for the communication with the server, I guess.

So it wouldn't be beneficial in any way...

[JacobD88]

In relation to multi core processors, but not in relation to actually using multiple cores, the best way to get a processing performance boost out of OTTD is to move its affinity from the primary processor on your PC to an extra processor with little or no load.

There are utilities out there if you google for them to set the (O)TTD exe to do this permanently when ran (look for "set affinity" apps, IMGCFG.exe is one of them), but the easiest way to do it (for windows platforms) on-the-fly is to run (O)TTD, alt-tab to desktop and get task manager up, select processes, find "openttd.exe", right click on the process, select "Set Affinity" and select only one of the extra processor cores (anything but the primary) for (O)TTD to use, de-select all the others, i use a quad-core Phenom II, so i find it best to select the fourth core for (O)TTD's affinity as this core is rarely used by windows or any other program, so is the least-loaded core NOTE: You have to do this every time you use (O)TTD which is why the aforementioned apps are useful...

If using a Dual-Core, select the second core, even if it appears to have more load, as last core in a CPU is inherently used less over-all

Result - A boost in (O)TTD's processing performance, but as mentioned elsewhere here, it is capped by other factors to do with computer architecture and the software so not much will be obvious, but at least you know the core you are using is as clean as it can be which is great for multi-player particularly if you use an on-board LAN port to get your internet connection through as on-board devices inherently (but not always ) use some CPU power from the primary core Setting openttd.exe to use an extra core means all those windows and device processes are left on the primary (and maybe second) core and openttd.exe is free to use what it wants of the additional core

I do wander if a useful patch for OTTD would be one to allow people to set the affinity for OTTD permanently upon installation (for noobs this could be an advanced install option to keep them out of it and stop the forums getting loads of questions), with an option in the advanced options tab to change it post install... That way no-one would need to look around for apps to change the affinity permanently, and people who want to be sure they are getting as much CPU power to (O)TTD as possible, get it...

[peter1138]

1) Tertiary means third, not "non-primary".
2) The process scheduler will balance CPU core usage, so there is no 'unused' or 'little used' core.
3) Setting processor affinity is mostly a cache issue, so only really has any effect on processes which fit entirely in cache. If it doesn't, there'll be cache misses either way.
4) On a fairly loaded system, setting processor affinity may be detrimental as it will restrict the process to one core while other cores might have spare capacity.

In summary, processor affinity is probably great for those small number crunching programs, but probably not so great for something a little bit larger.

I'm not an OS expert though

[JacobD88]

1) Tertiary means third, not "non-primary".
2) The process scheduler will balance CPU core usage, so there is no 'unused' or 'little used' core.
3) Setting processor affinity is mostly a cache issue, so only really has any effect on processes which fit entirely in cache. If it doesn't, there'll be cache misses either way.
4) On a fairly loaded system, setting processor affinity may be detrimental as it will restrict the process to one core while other cores might have spare capacity.

In summary, processor affinity is probably great for those small number crunching programs, but probably not so great for something a little bit larger.

I'm not an OS expert though

1) My apoligies, i thought tertiary was anything including and beyond the third

2) In windows VISTA or 7 BETA it does a better job of balancing the core usage, but under XP even with the AMD-CPU optimiser (as i use AMD CPUs on all my systems, not sure if intel chips have similar software) core balancing is pretty poor, in fact multi-core handling in XP is generally bad

I frequently find on my older dual core system that runs XP, one processor (usually the primary) will be at 100% load with the other at 20%... Why doesn't XP just balance each processor to work at 60% load? Or at least balance the processes in a manner that spreads the size of the processes between cores so you may get one processor with 65% the other at 35%... 100% really shouldn't happen with multi-cores (except when the cache size cant hold the process as below made me realise)...

3) I hadn't thought of that thanks, but is there any benefit to getting OTTD to use a single non-loaded core then???

4) Agreed, as mentioned in my post i have a quad-core Phenom II so im in the fortunate position of (generally) having more cores than i need, so if i set the affinity to the fourth core i don't tend to find i have anything loaded on to that core by windows for it to compete with so OTTD is free to do as it pleases (unless i multi task with a HD rendering premier pro for example, but hey that happens rarely...). I can imagine point 4 being more of a problem on dual core systems than 3x or 4x core ones, unless your multi-tasking with big programs, basically...

[Conditional Zenith]

2) In windows VISTA or 7 BETA it does a better job of balancing the core usage, but under XP even with the AMD-CPU optimiser (as i use AMD CPUs on all my systems, not sure if intel chips have similar software) core balancing is pretty poor, in fact multi-core handling in XP is generally bad

I frequently find on my older dual core system that runs XP, one processor (usually the primary) will be at 100% load with the other at 20%... Why doesn't XP just balance each processor to work at 60% load? Or at least balance the processes in a manner that spreads the size of the processes between cores so you may get one processor with 65% the other at 35%... 100% really shouldn't happen with multi-cores (except when the cache size cant hold the process as below made me realise)...

That is rarely the OSes fault. The OS can't magically split a single thread into multiple threads, so if there is one thread that requires 100% load, and the rest of the threads put together only amount to a 20% load, then there is nothing that can be done (except splitting that one thread into more threads, which is the application programmer's job).

[peter1138]

Don't confuse threading with the ability to schedule a process across cores. A slice of processing time can be run on different cores. It will still not be using more than 100% of a single core.

Probably the reason Windows will stick a high load process on a core instead of spread out is precisely because of the cache. A program stuck in a tight loop could well fit in cache.

[Core Xii]

I frequently find on my older dual core system that runs XP, one processor (usually the primary) will be at 100% load with the other at 20%... Why doesn't XP just balance each processor to work at 60% load? Or at least balance the processes in a manner that spreads the size of the processes between cores so you may get one processor with 65% the other at 35%... 100% really shouldn't happen with multi-cores (except when the cache size cant hold the process as below made me realise)...

The short-term reasons are explained above, but I want to add that XP does balance it out in the long run. It may run a single core at 100% for the duration that you run the program in question, but it will also alternate which core it runs on the next time you launch it, as to evenly distribute reliability across the cores (so that one core won't die before the others from being used more than the rest).

[ProDigit]

...
I frequently find on my older dual core system that runs XP, one processor (usually the primary) will be at 100% load with the other at 20%... Why doesn't XP just balance each processor to work at 60% load? Or at least balance the processes in a manner that spreads the size of the processes between cores so you may get one processor with 65% the other at 35%... 100% really shouldn't happen with multi-cores (except when the cache size cant hold the process as below made me realise)...

On my system (Win XP MCE2002 with SP3) the system MOST of the time balances out the process.
Most of the time I have between a 70-30 to 40-60%load (on fullload), closer to 60-40 or 55-45 ratio;even when playing openttd.

I rarely or seldom have 100%load on one core!

I wished it was more that way, cause then I would see what CPU my other programs use (which I can do like you mentioned, by setting affinity).

Though apart from the cache issue there's also the chance that both CPU cores will run cooler (eg: running on 1 core gives you 80 degrees C / 45 degrees, while running it on 2 gives you 60/60 degrees C).
And it's better to run a cpu core cooler than hot (even if they supposed to operate upto 120 degrees C, it will affect the life expectancy of the CPU).

[athanasios]

From a Google search:
http://portal.acm.org/citation.cfm?id=1241603

[Eddi]

that sounds funny and all, but who around here has a VLIW processor? the itanium did not exactly revolutionise the processor architectures...

[Bilbo]

I thought of another possibility how to use more cores than one (or two while saving) - give them to NoAI!

Every AI could spawn an extra thread to do some calculations. In this thread AI won't be able to examine the world or modify it (due to the locking issues or possibility to read tile in half of the update, etc ..., etc ...) but it can do any calculations (calculate best route given list of industries, etc ...)

So the AI may work like:

Code: Select all

 AI examines world, copying some information to some structure.
 AI spawns new thread, giving the structure to it.
 loop(forever) {
  do planned actions
  if (thread finished) {
    examine results
    plan some actions based on results
    reexamine world, creting new data structure for thread
    run new computation thread
  }
 }

There could be limits (max. 1 extra thread per AI), but if it gets implemented, you can effectively use multiple cores with AI with relatively little modification of existing code. The game itself still is single threaded, just the AI can run some "independent" computations in background.

[donchatryit]

1) Tertiary means third, not "non-primary".

Nope, it means anything past secondary. Not simply third. It can be used to only apply to third though.

[Eddi]

1) Tertiary means third, not "non-primary".

Nope, it means anything past secondary. Not simply third. It can be used to only apply to third though.

i nominate this for most useless post of the month award.

reasons:

• it is neither informative nor contributary to the topic
• it replies to a (deservedly) long forgotten part of the discussion
• it fails at being "know-it-all-y"
• it fails at being "troll-y"
• it is not even to be considered an april's fools joke

i have probably forgotten a few

[Yexo]

I thought of another possibility how to use more cores than one (or two while saving) - give them to NoAI!

Every AI could spawn an extra thread to do some calculations. In this thread AI won't be able to examine the world or modify it (due to the locking issues or possibility to read tile in half of the update, etc ..., etc ...) but it can do any calculations (calculate best route given list of industries, etc ...)

This may sound nice but in my experience AIs always need to access the map. The most time-expensive thing AIs do is pathfinding, and they definitely need map-access for that. Also it's mean every AI writer has to seperate his/her AI in two threads, which may not be easy.

[Bilbo]

I thought of another possibility how to use more cores than one (or two while saving) - give them to NoAI!

Every AI could spawn an extra thread to do some calculations. In this thread AI won't be able to examine the world or modify it (due to the locking issues or possibility to read tile in half of the update, etc ..., etc ...) but it can do any calculations (calculate best route given list of industries, etc ...)

This may sound nice but in my experience AIs always need to access the map. The most time-expensive thing AIs do is pathfinding, and they definitely need map-access for that. Also it's mean every AI writer has to seperate his/her AI in two threads, which may not be easy.

Well, then the main thread will need to copy tyhe map data and then start pathfinding on it. Or alternatively, we can allow tile querying functions in the second thread. Unlike querying vehicles (where you can end up on invalid memory location if you examine linked list while some element is being free'd elsewhere), querying tile can at worst result in examining the tile in middle of some update, but as there are no pointers, we can easily make code robust enough to handle this.

Therefore we can safely allow functions that read single variable from tile array (GetHeight, GetOwner ...), since it will either atomically read the variable before some change or after the change. If it examines two or more tile variables (GetCargoAcceptance, especially for larger radius) - we have to think about it, maybe disallow it.

As for the separating to two threads - it won't be mandatory. Only people with computationally intensive AI's wishing to utilize extra CPU power have to split their AI's into threads.

[Rubidium]

Yeah... but... many "queries" read things outside of the map:
- tile acceptance reads stuff from outside of the map (i.e. the town array and industry array);
- any commands in the query mode read stuff outside of the map (and write current company);
- many commands in query mode test for vehicles.

And what queries are atomically? GetHeight yes, but then you can't assume that the next tile is max 1 higher or lower. GetTileOwner on itself is atomic, but... the preconditions for calling it aren't. It may not be called for houses and industries. Now imagine an industry gets build... Also GetTileType is atomic, but anything that "depends" on the tile type (i.e. almost ALL other map accessors) are similar to GetTileOwner. This means that for doing sensible things for pathfinding not cloning the map is a VERY BAD idea. Unless you want to make the AI handle the cases where the API returns inconsistent data.

Next come some other "issues"; like 14 AIs running such a thread on a single core CPU. The game would become horribly slow as all AIs get a slice of CPU time of say 5 ms (average for Linux) so the tick would take 14*5 + time to run the game state which is way more than > 30 ms.

The new suggestion you have will be copying the whole game state. Ever experienced the hiccup during autosave on big maps? No imagine that happening much more often, basically every time an AI tries pathfind. And what about the memory requirements? Each running AI take ~50% memory of OpenTTD without AI.

[Eddi]

we can easily make code robust enough to handle this.

let me rephrase this: "we can make all map accessors (including ones that have nothing to do with AIs) significantly slower so that in some rare cases threads can be used, which probably won't make up for the reduced speed, because multiple conditions must be met:

1. the computer must have multiple cores
2. there must be an AI in the game
3. the AI must be coded multithreaded
4. the thread must have a significant workload

[Bilbo]

And what queries are atomically? GetHeight yes, but then you can't assume that the next tile is max 1 higher or lower.

With current API you can't assume it neither. Since AI's get suspended avery 10000 ticks (configurable), AI may get suspended between querying adjacent tiles and in the meantime someone else (another AI, player ...) may change the tile about to be examined or even flatten surrounding area. So with little "luck", the measured difference between adjacent tiles can be as much as 15 :)

Next come some other "issues"; like 14 AIs running such a thread on a single core CPU. The game would become horribly slow as all AIs get a slice of CPU time of say 5 ms (average for Linux) so the tick would take 14*5 + time to run the game state which is way more than > 30 ms.

The computational threads would run with lower priority. And if you have 14 AI's on singlecore, won't they be a bit slow in curetn singlethread configuration too?

We can also run more computationa threads in one real thread and switch between them every X opcodes, so there could be usable means of restrincint the game to reasonable number of threads/cores.

The new suggestion you have will be copying the whole game state. Ever experienced the hiccup during autosave on big maps? No imagine that happening much more often, basically every time an AI tries pathfind. And what about the memory requirements? Each running AI take ~50% memory of OpenTTD without AI.

AI can copy only part of the map and .... OK, bad idea.

Hmm ... well, I think pathfinding won't work well with multiple cores, I had originally another calculations in mind:

The thread gets complete list of towns (these are 100% static, only population slightly changes in time) and industries (these change only a little in time, so updates from main thread to computational threads won't be frequent) and then it calculates some potential routes (Looking as most profitable: deliver cargo T from X to Y. Second most profitable: deliver A from B to C, ....)

The actual pathfinding and connecting the routes would happen in the main thread.

The only "entity" communicating with second thread is the main thread, so no need to change game core code.