Print

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

[sweitx]

//Is setting the affinity in the OS alone good enough for that?//
Would help, since you can get DF to run ONLY on one processor and everyone else run on the other (DF only use one, as far as I know).

However, with the new OpenGL-based DF, that may no longer be true because depending on it's implementation, OpenGL may be able to use multiple cores for it's job.

[jaked122]

I thought when I read the first post, that it was basically saying to turn DF into an operating system that would run independantly of vista, linux, whatever else you might run it on. that would give it a fairly good speed boost, assuming it was performance optimized as windows vista, or the linux kernel, it could run increadibly fast, once the libraries and interfaces were smoothed over. this could make DF the fastest rediculous scale game ever!

[The Architect]

It would indeed have been placing DF into a program that simply interfaced with the systems, rather than being dependant on any single one. However we've been informed by those that know such things that the idea is impossible. The main reason being that Toady would not like to give us the resources we would need to do anything of the kind.

[happydog23]

From what I've seen in the game, there are plenty of places we could argue about that might be done more efficiently, however it is all conjecture until someone who has seen the code or taken the time to reverse enough of the assembly to understand what's going on decides to speak up. 


The idea that you HAVE to have the source code to implement threading is wrong in my opinion.  It would be amazingly obnoxious to do without the source code, but we do have the assembly and there are tools for changing it and making it more readable.  Honestly its probably not worth the effort to do it in assembly though (Especially this close to the next release).


In the mean time, I have an idea I'm willing to be flamed on it:

And please note that anything I say about internals and structures of the game below is mostly just guesswork.  It could be right, it could be close, it could be so wrong Toady bursts in to tears laughing at how inefficient the methods I "accuse" him of using are.  It’s really all meant to be more of a discussion piece.

I had a lot more information in this post, but I’m hoping I can just post a summary here:

I assume DF has essentially one main game loop.  This loop basically says take each individual dwarf, do dwarfy things, go to the next dwarf.  When all the dwarves have been gone through, one “turn” is complete.  (I know there are stones, gravity, temperature, other creatures, fluids and more to do on each "turn."  I said the loop "basically" does this).

Now assume we have 100 dwarves and 4 processors (or a quad-core or 2x dual cores it doesn’t really matter).  Instead of looping through 100 dwarves on 1 processor, we could loop through 25 dwarves on each processor.     When all 4 of those loops are finish, one turn is complete.

Spoiler (click to show/hide)

(and it is important to have roughly equal numbers of each type on each processor.  If we have 100 stones and 100 dwarves, putting 50 stones on 2 processors and 50 dwarves on 2 processors is not going to be as effective as 25 stones and 25 dwarves on each processor)

TO borrow G-Flex's example of baking a cake (since it is the only example I really saw in the thread on why multi-threading DF is hard):

• Preheat the oven to 350 degrees.
• Grease a pan.
• In a large bowl, beat the eggs.
• In another large bowl, mix the sugar, flour, and baking powder.
• Add the other liquid ingredients to the eggs and mix thoroughly.
• Add the egg mixture to the flour mixture and mix them together.
• Pour this into the pan.
• Stick the pan in the oven for 40 minutes.

Breaking up that list is hard.  Having a computer do it is even harder.  However what if we aren't making one cake.  Let’s make 2.  Now if you had to make two cakes, it gets a lot easier to split things up.  One of the simplest is going to be to put two chefs in two different kitchens with the same list as above, and in roughly 50 minutes, you'll have two cakes. 

It does get harder though.  Let’s assume the chefs are in the same kitchen (with plenty of counter space and bowls and ovens).  We've got plenty of everything except Grease.  (No one brought any animals, we don't have a butchershop, whatever).  With only one tub of grease for step 2, only one chef can grease his pan at a time.  Now maybe we can make one chef grease his pan right before he pours the cake in to the pan, or maybe one chef is going to have a smoke break while the other greases his pan, the point is that they can't both grease the pan at once.   

Some of the things that objects and dwarves do might be like the grease, but from the behavior I’ve seen in my dwarves, it appears to me that a lot of the protection functions would need to implement already exists.  One issue I can think of is finding a new job for a dwarf to do.  Previously only one dwarf could ever be looking for a job at once.  There’s no need to protect that data if only one dwarf looks at once.  But if we have 4 or 8 or maybe you play on a supercomputer with 2000 processors and have 2000 dwarves looking for a job at once, then you might start ending up with more than one dwarf picking the same job at the same time.  You would probably end up getting a "Job Item misplaced" message at some point, but until it happened you'd have extra dwarfs just wandering in circles (trying to do a job till some other dwarf beat them to it).

If multi-threading is even possible in this way depends entirely on how the code and pathing algorithms are written.  If they’re all accessing/changing shared memory all the time, then things could get extremely… FUN…  (Though I’m not entirely sure programming FUN is as fun as dwarf FUN).  But its doable with or without code.  Its not that hard with some code.

[Rysith]

[suggestion]

That's definitely something that's possible, and I suspect that DF would in general be amenable to in general. The trouble comes in in two places

a) Computers normally have several other things that they are doing at the same time, so even if you put 1/4 of the dwarves on each processor you'd get imbalances. So, you need stuff to make sure that a single processor that's slow (because the OS has decided that it should be running your music player, or whatever) doesn't hold things up. Because the OS can move which processor you're running on around (you get a Thread, which runs on some processor, but the program doesn't have control of which one or for how long), the order in which the dwarves, goblins, rocks, etc. do their dwarven, gobliny, or rockish things need to not matter (which it may now). For example: what happens if a goblin and a dwarf on different cores attack each other at the same time, both claiming to have killed the other? That leads to:

b) Along those lines, you need to make very, very sure that when something asks what the state of the game is, it gets an answer that is consistent with the answer that all of the other cores would get if they asked the same question. Two dwarves can't both think that they can grab the same rock to carve, and at a lower level to things can't both be trying to modify the same bit of memory at the same time, or the entire program destabilizes and dies, probably corrupting the game state in the process. That (in general) leads to the difficulty with multithreading: "It works most of the time" isn't good enough, because even a small mistake can end up having horrible (and hard to debug) consequences.

Now, that doesn't mean that it's not possible and, as I said, I suspect that DF does have a lot of places where it could be multithreaded. It's just that the required infrastructure and complexity is something that I can completely understand if Toady doesn't want to tackle right now, or even ever.

That was also probably one of the worst descriptions of the challenges around multithreading I've ever given. If it's the sort of thing you're interested in, go read the wikipedia article on thread safety]http://en.wikipedia.org/wiki/Thread_safety]thread safety.

[Blacken]

The "thinking" stage of the AI probably does consume a good chunk of CPU time. The main problem I can see with just splitting up tasking like that, I think, would be resource contention. Assuming locking on items/workshops and that sort of thing is atomic, it wouldn't be too large of an issue.

[G-Flex]

I'm not sure I would assume very much about the resource handling or modularity of DF's code. Not very much at all, really.

[Blacken]

I'm not sure I would assume very much about the resource handling or modularity of DF's code. Not very much at all, really.

True, but look at the outward-facing feature set. Dwarves say "that's mine" from the other side of the map if need be, and it's removed from the tasking for everybody else. So long as it's not possible for two dorfs to claim the same thing at once, you're A-OK. It parallelizes (relatively) easily. The logical way to do this is to have a bitflag or an integer somewhere that says "that's taken, don't touch it", and that's probably "atomic enough" as far as we're talking about.

[G-Flex]

Really, though, there are a lot of things about some systems that'll have to change for completely different reasons.

Right now, for instance, jobs choose dwarves and not the other way around. This will probably make decision-making for dwarves a hell of a lot harder once they can have, say, different priorities for each job.

[Blacken]

Really, though, there are a lot of things about some systems that'll have to change for completely different reasons.

Right now, for instance, jobs choose dwarves and not the other way around. This will probably make decision-making for dwarves a hell of a lot harder once they can have, say, different priorities for each job.

It will? I don't see why, but I could be missing something. It's the same kind of filtering, just going in the opposite direction.

[G-Flex]

It just sounds like it would be conceptually more difficult.

If dwarves choose jobs, it's easy for dwarves with variable job priority to select jobs: Have them start at their highest-priority jobs, checking to see if there are available things for them to do for each, stopping when they find one, so they wind up doing the highest possible priority work for themselves.

If the jobs choose dwarves, that's difficult. A stone item needing to be hauled can look for a dwarf with hauling enabled, but it has to not only know which dwarves have other labors at higher priority than hauling, but also whether or not those dwarves have other jobs they can do associated with those labors, which it won't know unless it knows about all the *other* jobs seeking dwarves.

I guess it would be a workable problem, but it seems more conceptually backwards to me, so it's probably more likely to cause problems in the future.

[Rysith]

The logical way to do this is to have a bitflag or an integer somewhere that says "that's taken, don't touch it", and that's probably "atomic enough" as far as we're talking about.

The problem with concurrency is that "atomic enough" isn't unless it's actually atomic, particularly because the "don't touch it" flag may not become visible in main memory to other threads for a long time (in processor-land, actually probably less than a millisecond) and the consequences of a data structure getting out of sync that way can be really bad, up to and including crashing DF.

[The Architect]

I don't think it would be possible as DF is now to split job assignment. I'm not sure why that was suggested, but it would really be an evilly hard problem to deal with. What you could reasonably do given the resources is separate some elements like the jobs and pathfinding onto different processors.

[Nadaka]

I don't think it would be possible as DF is now to split job assignment. I'm not sure why that was suggested, but it would really be an evilly hard problem to deal with. What you could reasonably do given the resources is separate some elements like the jobs and pathfinding onto different processors.

That is not an assumption we should make at this time about the actual game. The idea of batching off jobs and pathfinding to multiple threads assumes that the game update loop handles all jobs/paths in a step instead of handling jobs, paths, actions, etc for each object/unit in sequence.

[The Architect]

It's true that we really can't make any assumptions with surety. That wouldn't be an assumption. About all we can do is look at the data we have from the game interface, which clearly indicates the impossibility of multithreading jobs that might share materials. It is reasonable to assume that given the right information from Toady we might be able to separate some other things like pathfinding.

It is also very clear from what has been said that we are not going to be able to do any of this ourselves. But I would really like to backtrack a few posts, and consider the idea of changing the way objects are handled to the system suggested there. It is the one that prevents every other RTS game based on resource consumption from going to hell as objects multiply, and I really do think it might be applicable here. Thoughts?

Note: When I say "consider the idea", I mean just that. Let's consider the idea for viability so that it can either be suggested to Toady or discarded. I would appreciate skipping over re-re-restating the obvious fact that we can't do it ourselves.