Print

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

[nondescuid]

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.

I agree with that.

I wonder if we could borrow a concept from the game "Cultures", where you had to build signposts. When someone had to walk a long distance, they followed the signposts to find their way - the same reason why google map tries to get to a highway ASAP, so it can cover a far distance with only a few nodes. But once burrows have been implemented, they will serve the same purpose.

[kaypy]

Hmm. I wonder- does Kobold Quest use the same style of pathfinding as DF? Maybe it would be possible for some of the more thread-familiar coders to get that multithreading, if the code would then be reusable by Toady...

[dreiche2]

Yeah that sounds like a good idea, having some test program (that maybe just used the same pathfinding algorithm)  so someone could present Toady with a finished solution.

[Neonivek]

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

The largest jump Dwarf Fortress made was turning the game 3d... the next would be having the world change while you play.

So no... Dwarf Fortress is slower then the rate of development at this point and time as he can't really add anything as absolutely process power absorbing as 3d with 200 dwarves

[Draco18s]

Yeah that sounds like a good idea, having some test program (that maybe just used the same pathfinding algorithm)  so someone could present Toady with a finished solution.

Go grab Kobold Quest, it uses the same engine DF does.

[dreiche2]

uh I meant "someone" as in someone who has both an idea of how multi-threading works and time on his/her hands

Although, I might actually have a little bit of the latter after this month, so if KQ does indeed use the same engine, maybe I will have a look..

[dreiche2]

Okay, sorry for the double post, but on a second thought...

It's not really as complicated as it sounds.
[...]

If this explanation is correct, then shouldn't it be possible to demonstrate how multi-threading works with any type of loop of the kind we need? I mean, assume we have something like this now:

Code: [Select]

for iDwarf=1:nDwarfs
        pathToTake = doPathFinding(dwarfList(iDwarf), mapData);

then if you want to demonstrate how multi-threading works, you don't really need to know what doPathFinding does etc., only how what its interface is to the rest of the program (e.g. what variables are passed and returned, if there is something with references or pointers involved, etc). So you could program a little example that is ready to compile and uses the same structure (same interface type), and then Toady could simply copy and paste everything and change some function names and test if it works?

[Exponent]

Concurrent programming has a notorious reputation for looking easy in many cases, appearing to work just fine during testing, and then blowing up later, or on a different machine.

The two biggest things to worry about in this case are:

1)  Does the pathfinding algorithm write to public data?  For example, if it is storing temporary values in a map grid that is allocated once near the beginning of the program (rather than inside the pathfinding function itself, each time it is called), then multiple pathfinding threads running at once are going to destroy each other's efforts in some way or another.  If something like this is the case, then additional code would be needed to ensure that multiple pathfinding threads aren't trashing each other, and that would almost definitely require some concurrent programming knowledge, not to mention additional time/effort, on Toady's part.

2)  Does the pathfinding algorithm read public data that might be written by other parts of the program?  If so, then the algorithm might get confused as the map actually changes before the algorithm is complete.  Toady would have to ensure that pathfinding threads only start during a region of game processing where everything relevant to the pathfinding algorithm is read-only, and also ensure that all pathfinding threads complete before this region of game processing is over.  A generic form of this checking could be provided, but Toady would need to determine where these regions are.

Additionally, another problem comes to mind:  Toady might be calling the pathfinding function just in the middle of other algorithms, as needed.  But with concurrent programming, it's generally easier and safer (especially if we're trying to have a nice generalized piece of code that Toady can insert into DF easily) to start all the threads, wait until all the information has been calculated, and then use it.  So all the paths would need to be stored in some format, and then the code would need to execute that would actually make use of the paths.  This would likely involve a decent amount of shifting around of code and algorithms.  And again, it would require some knowledge and time/effort on Toady's part; it isn't something that others could do themselves without seeing the actual DF source code.

If KQ is close to DF regarding its pathfinding, then it is possible that Toady might be able to utilize changes that other people make.  But there would probably be a substantial number of changes, and copying lots of code without knowing what it does very well is just asking for trouble.  Especially when it involves multithreading.

[dreiche2]

true true, a lot of 'if's... but I think it's at least a possibility that we do indeed have the simplest case possible here. Only Toady knows, of course, but maybe he can/likes to answer that. Especially if it's just about confirming/negating that we have a simple function call to a read-only function.

About your second point, assuming you can just write a wrapper around your doPathFinding function that handles the mulithreading, would it be much of a problem to wait with the execution of the main program till everything is over? After all, as it is now with only the original function in place, the main program wouldn't continue until after the function call is over, either.

About your last point, I understand your point that it might be more efficient to the multitasking in a batch and not everywhere the path finding occurs. But even if you do it the less efficient way by just writing a wrapper for your original function, maybe it would still work better than now? Or just put the multithreading into that part of the code where the real work is done (e.g. where you have a big loop over all creatures, and not just some single independent requests in other parts of the program)?

Of course, there is still *some* effort involved by Toady in the end because of course he has to place the code somewhere. But he can still decide if it is worth the trouble. I just think by giving us relatively little information, e.g. about how the main pathfinding function calls are organized, it *could* be relatively simple for us to do some ground work for Toady.

And after all, I don't see why Toady wouldn't want to put a little effort into making DF multi-threading. The question is of course how much effort, and I understand that it looks like a hassle. So I just wonder if it could be much simpler in the end that it looks, and if we could find that out for Toady... but yeah, unless we know about all these "if"s, it's all just speculation...

[Wahnsinniger]

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.

AH HA HA ha ha ha. Trust me, there's FAR better use of Toady's time and talents than figuring out CUDA programming (and whatever ATI has for their cards). GPU Programming is great for teams trying to fold DNA and what not. A lone programmer making a game? Not so much.

(I know you weren't actually suggesting he do it, so don't consider this an attack.)

I was part of a class in college who were on the bleeding edge of CUDA development (seriously, there were guys from NVIDIA helping and I think the class just amounted to beta-testing it). Programming it sucked, though our team did get a model of a bunny to display via a ray tracer on the GPU.

Anyway, I would think the only way players could contribute to Multithreading is come up with a comprehensive model on how Toady could transition to it as painlessly as possible. Since he won't release the source code (fully understandable now that its his main means of income), thats about all you can do.

[sweitx]

Concurrent programming has a notorious reputation for looking easy in many cases, appearing to work just fine during testing, and then blowing up later, or on a different machine.

The two biggest things to worry about in this case are:

1)  Does the pathfinding algorithm write to public data?  For example, if it is storing temporary values in a map grid that is allocated once near the beginning of the program (rather than inside the pathfinding function itself, each time it is called), then multiple pathfinding threads running at once are going to destroy each other's efforts in some way or another.  If something like this is the case, then additional code would be needed to ensure that multiple pathfinding threads aren't trashing each other, and that would almost definitely require some concurrent programming knowledge, not to mention additional time/effort, on Toady's part.

In this case, you'll need to take a lock.  Not difficult if the language support it, if not... you need to go assembly, which I don't think we should burden Toady with that.

2)  Does the pathfinding algorithm read public data that might be written by other parts of the program?  If so, then the algorithm might get confused as the map actually changes before the algorithm is complete.  Toady would have to ensure that pathfinding threads only start during a region of game processing where everything relevant to the pathfinding algorithm is read-only, and also ensure that all pathfinding threads complete before this region of game processing is over.  A generic form of this checking could be provided, but Toady would need to determine where these regions are.

Additionally, another problem comes to mind:  Toady might be calling the pathfinding function just in the middle of other algorithms, as needed.  But with concurrent programming, it's generally easier and safer (especially if we're trying to have a nice generalized piece of code that Toady can insert into DF easily) to start all the threads, wait until all the information has been calculated, and then use it.  So all the paths would need to be stored in some format, and then the code would need to execute that would actually make use of the paths.  This would likely involve a decent amount of shifting around of code and algorithms.  And again, it would require some knowledge and time/effort on Toady's part; it isn't something that others could do themselves without seeing the actual DF source code.

If KQ is close to DF regarding its pathfinding, then it is possible that Toady might be able to utilize changes that other people make.  But there would probably be a substantial number of changes, and copying lots of code without knowing what it does very well is just asking for trouble.  Especially when it involves multithreading.

I think what you're saying is a sync operation.  Basically request a sync before AND after a pathfinding and you should have no problem (sync will wait for other threads to finish).  This may kill performance, but is easy to program providing the language/compiler support it.

[Core Xii]

If this explanation is correct, then shouldn't it be possible to demonstrate how multi-threading works with any type of loop of the kind we need? I mean, assume we have something like this now:

Code: [Select]

for iDwarf=1:nDwarfs
        pathToTake = doPathFinding(dwarfList(iDwarf), mapData);

then if you want to demonstrate how multi-threading works, you don't really need to know what doPathFinding does etc., only how what its interface is to the rest of the program (e.g. what variables are passed and returned, if there is something with references or pointers involved, etc). So you could program a little example that is ready to compile and uses the same structure (same interface type), and then Toady could simply copy and paste everything and change some function names and test if it works?

Yes, of course.

In this case, you'll need to take a lock.  Not difficult if the language support it, if not... you need to go assembly, which I don't think we should burden Toady with that.

There is absolutely no reason to go assembly. There are lots of libraries out there that implement thread functions in a friendly way that Toady can use, such as Boost::Threads as mentioned earlier and SDL. The hardest part is grasping what a "condition variable" actually is, but when you figure that out, the rest is easy.

[Felix the Cat]

In this case, you'll need to take a lock.  Not difficult if the language support it, if not... you need to go assembly, which I don't think we should burden Toady with that.

I believe DF is in C++ from taking a look at the memory model it uses, as I pointed out earlier and Core Xii reiterated the Boost family of libraries is standard, well-documented, and thoroughly tested for performance and stability before being released as strenuously as STL libraries (which are part of the language), and boost::thread provides a collection of relatively easy-to-use thread creation and management wrappers. ("Relatively" being the key term, I wouldn't define any threading as "easy-to-use" in the sense that std::vector is easy to use, but boost::thread is WAY better than, say, the nightmare of Win32 threading. Then again, pretty much everything in the Win32 SDK is a nightmare. Hurrah for Microsoft and their obsession with creating infinitely backwards-compatible code, leaving it closed-source, and providing shoddy documentation.)

The current C++ standard also conveniently provides the volatile keyword for use in multi-threaded environments - it marks variables that can be changed from outside the current thread of execution and thus prevents the compiler from making certain optimizations. Much easier than locks for non-time-critical reads, such as... pathfinding!

[MMad]

So no... Dwarf Fortress is slower then the rate of development at this point and time as he can't really add anything as absolutely process power absorbing as 3d with 200 dwarves

Sure he can! All that's needed is to simulate the entire world in real-time.
Stationing your military in a foreign capital would be pretty annoying, methinks.

[Draco18s]

AH HA HA ha ha ha. Trust me, there's FAR better use of Toady's time and talents than figuring out CUDA programming (and whatever ATI has for their cards). GPU Programming is great for teams trying to fold DNA and what not. A lone programmer making a game? Not so much.

Because CUDA (and other GPU appropriation programming languages, there are a dozen) is better than multicore support.

Oh wait, IT'S THE SAME THING, BUT USES A DIFFERENT PU!  ONE THAT'S TYPICALLY SLOWER!

Right.