Print

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

[Funtimes]

As computers will raise in power, DF will raise in complexity.

This needs a name. Like Moore's law.

Urist's Vengeance.

[Aorik]

*creates a reaction titled "Divide dwarf by zero" and runs it

[riffraffselbow]

Theoretically, some token Multi-threading "shouldn't" be "too" hard. This is all based on my limited understanding of it all, but asynchronous coding isn't magic or rocket science, it's just a pain in the ass.

[Moody]

Well, from what I've read - Toady has been reluctant to multithread because he doesn't know how to do it and would rather focus on other areas of the game.

If pathfinding was done in multiple threads instead of sequentially, that might speed things up significantly, no? I don't know how it's programmed, but I'd assume some sort of loop. Couldn't there just be a whole bunch of threads branched to work on each creature individually, then join again afterwards?

It's incredibly primitive in terms of concurrency, but atleast it's something.

[Marconius]

The problem is that significantly changing how a program works halfway through is not only a pain in the ass and a lot of work, but could also lead to a whole lot of complications. This is why you generally design a program first and implement it after.

Dwarf Fortress is already an enormous piece of software, and even if it is coded well and modularly, it would still be a lot of hard work to change it to support multithreading and then to kill all the arising bugs. And Toady would probably like to spend his time on something a bit more visible and fun. So I doubt we'll see multithreading for a long while, if at all.

[devek]

Well, from what I've read - Toady has been reluctant to multithread because he doesn't know how to do it and would rather focus on other areas of the game.

He knows how to do it, he just doesn't know how to do it and get a performance gain. The way DF works, threading would most likely slow it down.

If pathfinding was done in multiple threads instead of sequentially, that might speed things up significantly, no? I don't know how it's programmed, but I'd assume some sort of loop. Couldn't there just be a whole bunch of threads branched to work on each creature individually, then join again afterwards?

Not really. With any loop you don't branch a thread off for each iteration of the loop because starting a thread is more expensive than calculating the path. What you do is make a pool of threads and send them work units.

For example, when Dwarf Foreman cuts down trees/shrubs it assigns 600 trees/shrubs to a work unit and they are picked up and ran by the worker threads. Even with the best design, there is efficiency loss. Assigning the job to 4 cores doesn't make the job run 4 times faster. On my test map the non threaded version took 60ms to run, while the threaded version took 25ms and I have a i7(4 cores + hyper-threading).

On the subject of path-finding.. there simply isn't enough dwarfs in the fortress to justify spawning a single thread. No matter how you go about it, it will be slower. Threading a loop that deals with the 7000+ pieces of vegetation that can exist on a standard embark area makes sense, threading a loop that deals with how many of your dwarfs are doing a specific thing is never going to be productive.

The problem with pathfinding is how it is done.

When you go to google maps and ask for directions, do you think it goes through and calculates your entire route from scratch?** In computer science we have data types to deal with spatial information. I could rewrite the pathfinding for DF to work on 1 thread faster than any threaded implementation possible(unless you had a fort with 10000 dwarfs)... but it would take a LOT of work. Toady is just one guy, and he would rather work on fun stuff than totally rewrite huge chunks of the game to make it a little faster.

** (That isn't to imply that DF calculates routes from scratch either, it doesn't)

[Soralin]

Well, you're making computers more efficient but there is still a wall that will be reached.

Once 100% of the power/energy that goes into a computer is used for computations, you can't go further

The good news is, that computer wouldn't require a heatsink or any cooling...

Actually, you could go further. There's always MOAR POWER

http://en.wikipedia.org/wiki/Matrioshka_brain 

[Makaze2048]

I could rewrite the pathfinding for DF to work on 1 thread faster than any threaded implementation possible(unless you had a fort with 10000 dwarfs)

Sorry but I'm going to have to call BS on that. While I agree that threading is fairly useless when calculating an individual path it is supremely suited to calculating multiple paths concurrently. There is certainly an overhead associated with threading but when given non interlocking tasks such as pathfinding (path thread A cannot alter the data of and does not care about the results of path thread B and vice versa) that overhead is tiny when compared to the gain of running as many instances of that process as you have free cores. So no, you don't need 10,000 dwarves to make threading out pathfinding worthwhile. In fact so long as pathfinding execution time > threading overhead execution time then you'll see a gain with only a single dwarf (the main thread would then have excess time for other activities).

Now having said all that, threading is hard. And setting up something like threaded pathfinding that needs data that is being constantly manipulated by the main thread is especially bad. Locking or periodically copying the required data into a static set for the child threads is a real pain and can be memory/performance intensive. In this case I'd say that there would need to be a separate worldstate array that only contained movement cost entries that is updated via a queue whenever the real world state is. Each pathfinding thread upon start would examine the queue, if empty it does it's thing, if changes are present look for any other pathfinder threads already running. If there is one he waits until they're all finished. Once the other thread is finished the queue is locked, the changes are applied and the thread does its thing. If there are multiple pathfinders waiting it's no big deal as only one of them will be able to lock the queue, as soon as the others receive the the queue lock they'll see that's it's now empty release it and immediately begin executing.

And of course that will totally not work because I don't think I've ever had an initial threading plan actually work, there's always something that goes wrong and you have to redesign it from the ground up. Point is that threading pathfinding would be incredibly efficient but I understand why it hasn't been done yet.

[nbonaparte]

Well, you're making computers more efficient but there is still a wall that will be reached.

Once 100% of the power/energy that goes into a computer is used for computations, you can't go further

The good news is, that computer wouldn't require a heatsink or any cooling...

Actually, you could go further. There's always MOAR POWER

http://en.wikipedia.org/wiki/Matrioshka_brain 

I take it you've read Accelerando?

[devek]

I could rewrite the pathfinding for DF to work on 1 thread faster than any threaded implementation possible(unless you had a fort with 10000 dwarfs)

Sorry but I'm going to have to call BS on that. While I agree that threading is fairly useless when calculating an individual path it is supremely suited to calculating multiple paths concurrently.

How many multiple paths are we talking about? You haven't broken down the problem.

If your fort has 200 dwarfs and another 200 pets/invaders/etc what is the chance that all 400 of the creatures will need to path during a single frame? Only a small percentage of your dwarfs are path-finding during a single given point of time.

Even in the worst case scenario, with 400 creatures needing to path.. there will be no performance gain from threading unless your path function is incredibly slow. Why would you spend time threading the function (making the game slower for people on a single core) when you could just make the function faster?

Now if I had something like 10,000 paths to calculate... that would be different and I would put them into groups of 600 and see gain.

Now having said all that, threading is hard.

No

I don't think I've ever had an initial threading plan actually work

Sorry

Point is that threading pathfinding would be incredibly efficient but I understand why it hasn't been done yet.

Until you have sat down and spent a few hours running IDA again DF(or you're Toady and have the actual code), you can't really say you understand much about DF.  It annoys me when people who are probably not as good at programming as Toady, try to tell him how to program.

[MaDeR Levap]

On my test map the non threaded version took 60ms to run, while the threaded version took 25ms and I have a i7(4 cores + hyper-threading).

You scoff at over 2x perfomance gain? Seriously?

[devek]

On my test map the non threaded version took 60ms to run, while the threaded version took 25ms and I have a i7(4 cores + hyper-threading).

You scoff at over 2x perfomance gain? Seriously?

A lot of people seem to think that doing something with 4 cores will be 4 times faster. I only threaded that part because it took a few min and I knew there would be good gain, but this is just development code and the final product will be able to do the same thing near instant with 1 thread if it wants..

[Makaze2048]

How many multiple paths are we talking about? You haven't broken down the problem.

Doesn't matter. Assuming you make path finding (or any other threading call for that matter) truly asynchronous and the overhead of kicking off your pool thread is less than the work it's doing then you've saved work for the main thread.

Only a small percentage of your dwarfs are path-finding during a single given point of time.

Agreed, but who cares? As I said if even one dwarf needs to pathfind then that's a potential savings for the main thread.

Even in the worst case scenario, with 400 creatures needing to path.. there will be no performance gain from threading unless your path function is incredibly slow.

How do you figure that? Are you assuming we block until the pathing threads are complete or something. Path results are requested from an asynchronous thread, near the beginning of the main loop, if they're ready then great we use them near the end. If not then they're acted on in the next frame. The next frame which comes faster than it would if it was synchronously calcing paths.

Why would you spend time threading the function (making the game slower for people on a single core) when you could just make the function faster?

I never said it shouldn't be optimized. Assuming that can be done reasonably and while maintaining code flexibility then great do that too. As for single cores you can largely call something like pathfinding synchronously if desired as decided by an init flag. And let's be honest single cores are going away, is there any one even still selling them these days.

Now having said all that, threading is hard.

No

I don't think I've ever had an initial threading plan actually work

Sorry

Hey, if threading is that easy for you then congrats. Maybe I'm just old and grew up in a single threaded world. On the other hand you sound like someone still in school who finds the dinky little threading exercises they give you to teach concepts too easy.

Most of my threading implementations get redesigned because half way through the client suddenly remembers that oh yeah there's this thing we forgot to tell you that completely changes how that's going to work. Or they work great for what they're designed to do but the locking scheme is totally incompatible with the new feature we're adding 6 weeks from now.

Threading a realtime large scale app in the real world is hard. And if you don't believe that then you haven't had to do it yet.

Until you have sat down and spent a few hours running IDA again DF(or you're Toady and have the actual code), you can't really say you understand much about DF.  It annoys me when people who are probably not as good at programming as Toady, try to tell him how to program.

I have absolutely zero concrete knowledge of how the DF internals work. Only a reasonable extrapolation of how they could in theory work. And based on that I gave a hypothetical example of how I'd do it after 2 minutes of halfhearted pondering.

Toady is not some sort of programming god. He's a absurdly motivated programmer and there are a hell of a lot of things in DF that are done right. But there are also a hell of a lot of things done wrong. And he probably knows the vast majority of those things and shakes his head when he thinks of how foolish he was back when he wrote them (you show me a programmer that doesn't do that and I'll show you a crappy programmer). Even assuming for the moment that he is a better programmer than me is that any reason not to offer suggestions or feedback? I don't think so and if that annoys you then... Oh well, deal with it.

And I still maintain that threading is a net gain for any given task if (number of concurrent tasks * thread execution time) > ((overall threading maintenance * main loop executions) + (thread spawn time * number of concurrent tasks)). Until you can refute that statement or explain how it does not hold true for pathfinding in DF then you've got no case as far as I can tell.

[MaDeR Levap]

You scoff at over 2x perfomance gain? Seriously?

A lot of people seem to think that doing something with 4 cores will be 4 times faster.

Their misconception is their problem. I was asking because I seen people squeezing tediously every bit and every percent of performance gain - and what I see here? Someone scoffing at 2x gain (!!) after a 5-minute coding (!!!!) because... 4 cores cannot do 4x gain. Good grief.

final product will be able to do the same thing near instant with 1 thread if it wants..

Test it. You could be in surprise (obviously by then gain will be lower than 2x, but still should be good).

How do you figure that? Are you assuming we block until the pathing threads are complete or something.

Yes, exactly this assumption comes in play. DF is build around assumption that layout of map can and will change constantly. Tiles are dug out, fluids flow, there was some cave-in...

Path results are requested from an asynchronous thread, near the beginning of the main loop, if they're ready then great we use them near the end. If not then they're acted on in the next frame. The next frame which comes faster than it would if it was synchronously calcing paths.

Cannot be done. As I said above, map layout could change between frames. So main loop must wait for finishing all pathfinding threads.

[Dbuhos]

My game never really lagged from anything beside a giant war in adventure mode where a dwarf settlement got raided by a huge group of animals.