Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[nondescuid]

Instead of more clock cycles, Moore's Law now gives us more CPU cores - the current trend is towards manycore processors. To use all that power, DF has to become multithreaded.

I realize that retro-fitting a multithreaded design into the whole program (including debugging) would probably equal the effort of a total rewrite. Therefore, I propose that only the biggest performance hog - path finding - will be multithreaded.

Pathfinding is particularly suited for this because of the following reasons (note that I am assuming that all pathfinding calculations in a frame are done in one block, i.e. there are no other calculations in between):
- no need for locking: the data that has to be read by the pathfinding calculation (terrain data) is not modified and no two threads have to write their result (the path for one single creature) to the same location
- pathfinding is a performance hog, therefore low-hanging fruit optimization-wise
- you can put all path-finding jobs in a queue, then spawn as many worker threads as the machine has CPUs and let the main thread wait until all jobs are completed. Because there are so many path-finding jobs, this will scale not only to dual cores, but also to quad-cores and beyond.
- pathfinding might be an opportunity to optimize performance in a part of the code that is very unlikely to be re-written soon

Disadvantage: some enthusiasts might starve after they have blown all their money on a server with 64 CPUs to play their 200 dwarf fort at 150 fps...

[Jay]

Using multiple cores at all: Impossible without a total rewrite of the hooks that allow it to use even the one core.

[Felix the Cat]

Using multiple cores at all: Impossible without a total rewrite of the hooks that allow it to use even the one core.

Boost::thread ftw.

[Draco18s]

Therefore, I propose that only the biggest performance hog - path finding - will be multithreaded.

Here I thought it was flows.  My mistake.

Retro-fitting a multithreaded design into the whole program (including debugging) would equal the effort of a total rewrite, even just doing pathfinding.

[Mel_Vixen]

And i think toady wouldnt make two versions each time. One for multicores and one for us guys who by not haveing money must use old singlecores.

[Felix the Cat]

Therefore, I propose that only the biggest performance hog - path finding - will be multithreaded.

Here I thought it was flows.  My mistake.

Retro-fitting a multithreaded design into the whole program (including debugging) would equal the effort of a total rewrite, even just doing pathfinding.

Not necessarily... I'm active with the Spring project (which has a lot of DF players), which was originally single-threaded. Someone managed to get the pathfinding working in its own thread. No total rewrite was necessary. Not even a rewrite of the core pathfinding code was necessary (or possible, considering that it works by voodoo magic i.e. nobody understands it).

That said, SMP is indeed a bitch and a half, and I certainly wouldn't want to be in Toady's shoes when he finally decides to tackle it.

Maybe Toady will decide to split some of the completely new mechanics into their own threads - i.e. global economy.

(And DF currently uses 6 threads, according to Task Manager.)

...and single-core processors can handle multi-threading just fine, they just don't get any performance gains out of it. Your PC is multi-threading right now - Windows is running in one process, your internet browser is running in another, and they split CPU time to do their things. (ok, fine, multi-processing, but it's the same concept)

[Exponent]

The largest problem, and I totally understand this because I was at this point once, is that (from what I've heard) Tarn is not highly experienced with multithreaded programming.  And learning multithreaded programming is an absolute pain for many, perhaps most.  So many bugs are likely to occur, even in ideal multithreading situations, when you're just learning.  Some people are surely able to pick it up easily, but in general, the reasonable assessment of such a task for a person with little relevant experience should be that it would be very risky.  It could very easily turn into a major headache, and get in the way of other areas of more rewarding development.

Now I'd love it if Tarn were already great at multithreaded programming, because DF is just algorithmically screaming to be multithreaded.  But I can also understand that if he doesn't find the idea of learning multithreaded programming to be intrinsically appealing (I do find it wonderfully enjoyable to learn about, but I'm sick in the head), it's probably best to just stick to the other improvements to the game, especially those dealing with content, since that certainly seems to be where Tarn's greatest interests lie.

[Mel_Vixen]

Ok multithreading is a bitch as terminologie.
 
I meant and i think op meant that too, splitting the programm so that the Processes of pathfinding runs on the second core ,of an multicore system,  so that it makes the game faster cause it gets more processor time.

 There are some isues that can be very crapy if you write multicoreprogramms for example in synchronisizing your programmcomponents if you have more then one timedepended Processes in it.

[Core Xii]

It's not really as complicated as it sounds.

The main thread spawns a number of auxiliary threads into a 'thread pool' when the game starts, equaling the number of available cores.

In addition you create a task queue - A list of dwarfs and their destinations that require pathing.

You also create a condition variable; a lock that guarantees that only one thread is accessing the queue at a time.

Now, the aux threads go to sleep. The main thread runs all game logic, and when it gets to the pathfinding phase, it gathers all the dwarfs and their destinations to the queue we created, then signals the condition variable to wake up all the threads. The main thread itself goes to sleep.

The aux threads, woken, access the queue in turn, taking a dwarf, removing it from the queue, and pathing its path. Then they return to the condition variable - If the queue is empty, all work is done, and they go to sleep. The last aux thread that completes its task (keep count how many are active) signals the main thread that the job is done.

From here the main thread resumes game logic that follows.

Since the map data array is only read during this operation, there is no need to manage thread access to it. The dwarfs don't need to be locked either, since each thread only works with its own dwarf, whose access is managed by the queue.

[Red Jackard]

And i think toady wouldnt make two versions each time. One for multicores and one for us guys who by not haveing money must use old singlecores.

You know, if Toady ever did look into this - unlikely at the moment - I doubt he'd make two separate versions just for the people using obsolete computers which for the most part are no longer sold on the market.

[Neonivek]

Look... Toady doesn't need to optimise his game...

I know what your saying "But I can barely play it now and in five years it will use 2-10 times as processing power to run as before"

However I rebuttle to say: "In five years, a decent computer should run Dwarf Fortress with ease, judging by the rate in which technology increases, so you will be able to run five Dwarf Fortresses at once"

Lets face it... Toady just has to take his sweet sweet time making the game and all his optimisation problems will be solved simple because our hardware will be better.

[Yanlin]

This game menaces with spikes of multithreading.

[nondescuid]

However I rebuttle to say: "In five years, a decent computer should run Dwarf Fortress with ease, judging by the rate in which technology increases, so you will be able to run five Dwarf Fortresses at once"

Yes, you will be able to run five fortresses at once, all of them at 200 FPS, while they are still small. No, you won't be able to run one big fortress at 200 FPS. The point of my post is that you can no longer rely on improvements in processor technology to just make your program faster if said program does not use at least as many threads as the new CPU has cores.

Using multiple cores at all: Impossible without a total rewrite of the hooks that allow it to use even the one core.

That's my initial assumption down the drain then

[MMad]

However I rebuttle to say: "In five years, a decent computer should run Dwarf Fortress with ease, judging by the rate in which technology increases, so you will be able to run five Dwarf Fortresses at once"

Honestly, at this rate I think the requirements of DF will outpace the development of technology.

[LShadow]

I think the path-finding logic will become less of an issue when the concept of "burrows" comes along. Rather than having to walk a huge graph across an entire fortress, common routes from burrow-to-burrow can be stored; path finding only happens within a local component of the graph (i.e., within a burrow) once the necessary routes are cached. Toady always seems on top of these sorts of optimizations, so I suspect he's already thinking about it (or already done it and I'm just to lazy to find out first).

Targeting multiple cores makes sense in that your standard off-the-shelf box is multicore. Heck, there's probably a good argument to be made about targeting GPUs these days. I also think that, with a single developer and a lack of concurrent programming experience, Toady should probably wait until multicore development tools mature and languages catch up with safe concurrency grammars.

When push comes to shove, I'd prefer better content and stability over better performance.