Bay 12 Games Forum
Dwarf Fortress => DF Suggestions => Topic started by: ivze on March 13, 2011, 02:12:53 pm
-
I've been playing for half a year. Most of my fortress have been lost to lags and related boredom, less to invaders and other !!fun!!.
I believe that The Developer should have multithreading arc in schedule. Things are getting more and more complicated, while a single CPU core, DF is able to utilize, isn't going to get proportional rise of performance for technical reasons.
You may consider this a bit like trolling :), but I have a naive idea. If DF has any architecture parts (pathfinding?), where an array of items is processed to produce other array of items, each processing independent, this is easily paralleled with technologies like OpenMP. Provided DF has parallelable parts of code, this would be as straight as adding some #pragma-s in front of for() loop in C/C++.
I do not underestimate the complexity of DF, however. I know that it must be megatons of code. I respect The Architector for doing the wonderful thing for all of us!
-
I would be the most under rated yet best arc ever.
-
I whole heartedly agree with this sentiment. However, if I am not mistaken, doesn't adding multi-threading into software create some significant potential stability issues (which, of curse, can be eliminated with effort)?
-
I certainly agree with the spirit. There is much to be gained in pathfinding.
There are much easier steps that could be taken that I would hope get attention. Suggestions such as:
* Stockpile-only pathing. For example if a kitchen needs food to cook with, it only checks to see if designated stockpiles for cookable food exist and contain food. If they do, path to the stockpile (but claim the food). Once the dwarf reaches the stockpile, path to the food. (Enablable/disablable. A mature fort benefits highly, a fledging fort might lack stockpiles)
* Cache pathing. The only time a path needs to be reevaluated a major event, such as (1) a square is dug which joins two free spaces that were not originally touching (or a door is unlocked, floodgate opened, etc), (2) a non-passable object is built in a square such that a path between the eight surrounding squares no longer exists (door locked, floodgate closed. etc), (3) traffic designation changed, (4) burrow designation changed. There's an extra complexity/advantage to be gained here when a path is gradually enhanced, and it's difficult to explain but easy to implement if anyone is interested.
* Shared pathing. See cached pathing, then add to it. Each time a path is identified, it can be used as a sub-path to another path. It doesn't matter of the end points of the path necessarily appear on the new path (picture worth a thousand words, ask if curious).
Now this all keeps the current mentality that all pathing must be PERFECT. Every path ever possible is completely evaluated. Much is to be gained if we had an O setting that said how much extra effort should be spent to optimize, and what is "good enough".
-
There have been a few discussions about this, and I would generally support a 'performance arc' to try to make larger forts more playable.
My own testing (posted somewhere, but I forget where), though, shows that pathing may not be the major source of late-game slowdown. In my tests, both the number of revealed squares and the number of items (tested by mining out full levels of sand and then stone with only the starting 7 dwarves, then gathering the stones together and atom-smashing them) in 40d were significant contributors to fps drop, which I can only imagine got worse in DF2010 with the addition of caverns and generally much deeper embarks.
While I'm not sure about the internals of DF (and running it through a profiler would be the only real way to figure out what the performance bottlenecks are), my suspicion is that memory access (particularly the job system and whatever global tile state structure DF uses) is a major limiting factor at the moment.
Multithreading should be reasonable at some level, though possibly not with OpenMP (nothing in DF strikes me as likely being non-interacting arrays to which the same operations are applied). At a level slightly more complex than OpenMP, allowing creatures to interact with the world (move, claim items, etc.) atomically should allow each creature to have its own thread, which should scale nicely (likely as a queue of creatures that need to be processed for the current step and a pool of threads to process them), since on the surface DF looks like it should be easy to break into separate tasks with a small amount of synchronization. Since it may not be the current bottleneck, though, and has a tendency to introduce subtle and non-deterministic bugs, it may not be the best thing to focus on if there are other low-hanging fruit available.
-
I whole heartedly agree with this sentiment. However, if I am not mistaken, doesn't adding multi-threading into software create some significant potential stability issues (which, of curse, can be eliminated with effort)?
Multithreading should be reasonable at some level, though possibly not with OpenMP (nothing in DF strikes me as likely being non-interacting arrays to which the same operations are applied). At a level slightly more complex than OpenMP, allowing creatures to interact with the world (move, claim items, etc.) atomically should allow each creature to have its own thread, which should scale nicely (likely as a queue of creatures that need to be processed for the current step and a pool of threads to process them), since on the surface DF looks like it should be easy to break into separate tasks with a small amount of synchronization. Since it may not be the current bottleneck, though, and has a tendency to introduce subtle and non-deterministic bugs, it may not be the best thing to focus on if there are other low-hanging fruit available.
Oh yes, it does... That's the hard and true way of going multithreaded!
-
I whole heartedly agree with this sentiment. However, if I am not mistaken, doesn't adding multi-threading into software create some significant potential stability issues (which, of curse, can be eliminated with effort)?
The main one is synchronization, which usually means stuff like locking areas of memory so that one thread knows to wait for another thread to be done writing parts of memory so they don't both write over each other with a random thread winning the race.
Part of the problem is that certain system routines aren't thread safe, meaning they'll cause threads to clobber each other if two threads call them at the same time, so in addition to making sure your own code is thread safe, you have to make sure that you're not using system code or third-party code that isn't thread safe.
Because multicore processors haven't been so important until lately, there is a lot of code out there which isn't written with thread safety in mind even when it doesn't make use of multiple threads itself. This is because synchronization is a pain which increases the amount of effort required to code something, which then increases the cost of writing the code, and people don't want to undertake that cost when there hasn't been much reason to except in the past 5 or so years with everyone using multicore processors.
So anyway, without actually seeing the code it's difficult to say how hard it would be to make some parts multithreaded without introducing lots of synchronization bugs (which can often be hard to isolate in debuggers). So even if, in theory, certain parts of the code should lend themselves well to multithreading it doesn't mean the existing code would be easy to modify for multiple core support.
Porting to different operating systems also presents more of a challenge with multithreading as some system routine in one OS might not be thread safe in another OS.
-
An Performance Arc sounds good to me. Off the top of my head, getting Dwarf Fortress to be remade for 64-bit functions would be good for allowing it to use more than 2 Gigabytes of memory, which is becoming increasingly more common, and undoubtedly would be useful for the long-term future of Dwarf Fortress. Is there anything else in addition to 64-bit and Multi-Threading that would be useful in an Performance Arc?
1 - Multi-threading
2 - 64-Bit Dwarf Fortress
3 - SSE1 & SSE2
4 - MSX
5 - Temperature
6 - Pathfinding & Hauling
7 - Fluids
8 - Data & Item Storage
9 - Profit!
-
I'd be super happy with just 64bit. I'd like to gen a massive world history, but you hit the 2gb memory wall pretty fast..
-
This has all been discussed before, so I'm reluctant to jump in. I will mention though the one thing which wise individuals usually say in these discussions and everybody usually ignores:
There are probably lower-hanging fruits, that can yield performance improvements with less development work, than multithreading.
That is to say, it's entirely likely that by simply running the game with a profiler, it would be possible to identify hot-spots that could be rewritten with some thought for dramatic performance gain. Based on previous forum threads, I think Toady knows this already. So the first step in any "performance arc" should Toady do such a thing would likely to be just that.
That said, I do think multi-threading could allow the game to scale greatly in the future and could be of great benefit somewhere down the road. I for one would like to be able to embark in a 16x16 site instead of a 4x4 :)
A 64-bit build could also get some bang with relatively little buck depending on how the game is written - the 64-bit Intel/AMD chips have twice as many general-purpose registers available in 64-bit mode, which can be used to reduce memory access when functions are called. Whether or not this would actually benefit DF specifically is something Toady knows better than any of us, though.
EDIT: Oh, and one other thing I want to throw out there: I know not everybody agrees with me about this, but I think that if it were possible for the user to optionally select a less-optimal pathfinding algorith, that executes faster, there would be great merit in doing so. Nobody wants the pathfinding to be completely stupid, but there are plenty of fun games with simplistic pathfinding that run on much slower PCs than DF will. If I could have my dwarves take paths that are 5% less optimal, but can be computed in 5% the time, that could go a long ways towards my 16x16 embark dream.
I can't say whether or not that could actually be possible, though. I'm just speculating.
-
There are probably lower-hanging fruits, that can yield performance improvements with less development work, than multithreading.
This. Multithreading and weapons seem to be the new suggestions that seem to get a new thread every week.
Toady is an extremely dedicated programmer, but he was basically a novice when this project was started ten years ago when he had fairly limited experience beforehand, and he's pretty much just been learning how to program as he goes along. This means that there are quite a few fairly basic things which Toady has only recently started to work with that optimize the code. One of them was just using a different compiler a couple of years ago that bumped up performance.
Rewriting the pathfinding code and item data storage code and the fluids code and temperature codes, for starters, can do quite a bit. The combination of pathfinding and item data storage are the real bottlenecks right now - iterating through tons of items for things like temperature checks, or having to do functionally flood pathfinding in many cases tie up the most resources, and the major problem comes down to memory access time as tremendous amounts of data gets checked every frame, usually without actually changing any of the data, anyway.
-
There is a reason that Toady hasn't made DF 64 bit. I emailed him a while ago asking for him to compile a 64 bit version.
The answer, unsurprisingly, was no.
Here's the email:
Dear Toady,
Would it be possible for you to compile a 64 bit binary for Linux? As I'm currently running my Linux machine on Ubuntu 10.04 64 bit and I don't particularly want to make a virtual machine for it. While I'm at it, is there any reason why the game isn't open source?
I've discussed the 64 bit stuff with Baughn, and as I understand it
I'd have to repartition my computer and work through a bunch of
compile errors. I don't have time for that at this point, though it
might happen later, the next time I have to reinstall windows,
perhaps, which is on the same machine.
DF is my sole source of incoming, and I'd be assuming a massive risk
by releasing the source.
Tarn
-
I think Toady should also look into memoizing paths. I remember that he said that couldn't do that because paths could change randomly, so a path that worked in the past might not work anymore. You might have water flood across a hallway, or a door might get locked, or something else. However, there's no reason that the dwarves would know that until they get to the barrier. It would be more realistic if they tried the old path, found out it was blocked, and then started the pathfinder to get a new path.
One trick that might help with pathfinding would be to define some 'centers'. All paths would lead to and from those centers. This would help with both memory and CPU issues.
Without centers, if you have 300 different places you want to go to, and you want paths to get to and from every place to any other place, you'd need to make 44,000 paths. Each path might take up around 1 KB, so you'd end up with 44 megabytes of paths, and you'd need a lot of CPU time to make all of those paths. However, if you want all of those places to go to and from one center, then you only need 300 paths. That keeps the pathing information down to just 300 KB, and it wouldn't take so long to get those paths.
The way that Toady could do it most easily, I think, is to define buildings, rooms and stockpiles as 'places'. The wagon at the embark site could serve as an initial default center. Other centers could be defined based on traffic. A frequently-visited stockpile could become a center. A main stairway connecting some floors could be defined as a center as well. The trade depot might become another center. Each 'place' would store a path to the 3 nearest centers, and each center would store a path to all other centers. To get a path to some location, you'd start at where the dwarf is, and find the nearest 'place'. Next, you'd find the 'place' nearest to where the dwarf wants to go. Next, you'd look at the three centers for each place, and determine which of the 9 possible paths is the shortest (the length of each path would obviously be stored so it doesn't need to be recalculated each time).
When a dwarf tries a path and finds that it doesn't work, then a new path would be found, and the dwarf would run the old pathfinder to get around the obstacle.
So, to keep the Performance Arc list going:
1 - Performance profiling
2 - Multi-threading
3 - 64-Bit Dwarf Fortress
4 - Path memoization
5 - SSE1/SSE2?
6 - MSX?
7 - ?
8 - Profit!
-
I'm sure I had a discussion about path finding earlier...
-
There is a reason that Toady hasn't made DF 64 bit. I emailed him a while ago asking for him to compile a 64 bit version.
The answer, unsurprisingly, was no.
Maybe there should be a "buy Today a 64-bit dev machine" donation drive? :)
-
If we were to do that, what kind of machine is required in terms of expense? I would guess that $400 would be for a minimal prefab, while $1,000 would cover something that is somewhere in the middle tier, depending on if Toady is willing to assemble a machine from custom parts or has a friend to handle it. Maybe if a Drive is setup, we can have multiple points on the donation threshold for what Toady can get for the money.
01 - Performance profiling
02 - Multi-threading
03 - 64-Bit Dwarf Fortress
04 - Path memorization
05 - SSE1 & SSE2 Instructions
06 - MSX Instructions
07 - Temperatures
08 - Fluids
09 - Data & Item storage
10 - Pathfinding, Hauling Arc, activity prioritization
11 - ?
12 - ?
13 - Profit!
-
Great, just what another multithreading thread needs, a derail into being yet another pathfinding thread.
This is the problem with constantly rehashing the same topics in different threads: The suggestions are always fundamentally the same, and always warrant the same fundamental response for as long as we are stuck in the rut of not reading the discussions that came before. It's not like there aren't good answers, but that the simple answers always come first, and the problems with the simple answers never change until you overcome their problems by reading the arguments came before.
Here, let me just pull up a few of the previous pathfinding suggestion threads, first of which was active just a few days ago:
http://www.bay12forums.com/smf/index.php?topic=76278.0
http://www.bay12forums.com/smf/index.php?topic=78413.0
http://www.bay12forums.com/smf/index.php?topic=42678.0
http://www.bay12forums.com/smf/index.php?topic=39067.0
Those are just some of the ones that tried something a little different, and only includes suggestions, not general discussions, which are much more prolific.
Hierarchical ("node-based" or "rectangles") pathfinding is a generally better solution - cutting the fortress into "rooms" as nodes which the game can pathfind through faster than flooding through every individual tile, provided node connection is maintained. As the first of those threads was discussing, it's just a matter of how you organize this sort of thing.
EDIT: Oh, and Pathfinder Project (http://www.bay12forums.com/smf/index.php?topic=43265.0)... for as drama-fueled as that became, it was certainly lengthy and in-depth about pathfinding.
-
Hasn't Toady expressed in the past that he has no interest in learning parallel processing? That kind of kills most of these ideas right off the bat.
EDIT: Toady answers the question:
DF Talk (http://www.bay12games.com/dwarves/df_talk.html) #9, at 57 minutes 53 seconds, or Ctrl+F "multiple cores" on the transcript.
The part that isn't on the transcript:
Toady: hehhehhehhehhehhehhehheh
Rainseeker: Uh oh.
-
Wouldn't it kill future expansion of DF, 10 years later or so, if you do not include multicore processing?
There are millions of methods of adding multicore, even multithreaded agents with message parsing, an example of this would be HTML5 Web Workers.
I am not saying this would be easy, but what would be the monetary requirement for the developers to work on this option? $10,000 to $20,000?
-
Well email Toady and offer 20k for him to do multi threading. He'd probably say no.
Toady makes DF for the love of it, he makes it because he finds it fun. It isn't "developers" either, it's developer. As it has already been said, there's much more time efficient ways to improve performance that don't include multi-threading. The game isn't going to get much computationally intense than it currently is, the main slow-downs being pathfinding, temperature and fluids. IIRC you can get large increases in FPS by getting rid of temperature, but it pretty much turns magma into a slow water. I can't remember how much faster it is though.
-
Actually, given that 20k is almost a year's salary... I think he'd consider it for that price tag if it was from one donor. Because the response when it was released would be alot of donation. But not so if 10,000 people donated $1 a piece. Then, they'd feel they already paid for the improvements.
So where is a rich benefactor who loves ASCII when you need him?
-
Toady makes DF for the love of it, he makes it because he finds it fun. It isn't "developers" either, it's developer.
DF is my sole source of incoming, and I'd be assuming a massive risk
by releasing the source.
Tarn