Bay 12 Games Forum
Dwarf Fortress => DF Dwarf Mode Discussion => Topic started by: Putnam on November 16, 2022, 01:32:54 am
-
Source: I actually profiled the game, which is the only way to actually determine what is slow in a program.
Pathfinding is slow, yes. It's hilariously slow. The thing is, it doesn't happen often at all. When it does, fortresses drop to sub-single-digit FPS levels. This usually happens because you're using tightly closed doors. Don't do that.
Pathfinding happens so rarely that my profiling has shown it contributes to about 6% of an individual tick's processing time. This is compared to the largest cause, one whose contribution to total CPU usage actually grows faster than pathfinding and one that is still the slowest thing in early game: units checking other units for line-of-sight/proximity checks (running away from hostiles etc), which is more like 20%. The truth is that FPS death is not a matter of multithreading pathfinding or anything like that, it's a combination of just about everything in there.
Not to say there isn't some major high-level optimizations to be made. A lot of the CPU time in unit checks is wasted in branch misprediction due to the fact that it's checking the units vector and just skipping everything that happens to be inactive/caged/a ghost; if those units' indices (or pointers to them, as the case happens to be, unfortunately) were simply cached in a vector that contains only active/uncaged/non-ghostly units, that would be avoided and the game would probably run quite a bit faster.
In general, just, like. Trying to optimize a program without profiling is just... blind flailing at nothing of consequence. If you want to contribute to figuring out what is causing FPS issues, first you have to figure out how to actually use the tools that let you find out what's causing FPS issues. I don't know if this is a gatekeepy viewpoint, but I've seen people so hyperfocused on pathfinding, which does not cause FPS issues except in extreme edge cases and tightly-closed door mishaps, that they seem to be convinced that fixing the pathfinding will fix the FPS issues.
It won't. Pathfinding is not a major contributor to FPS issues. Sorry, people have just been wrong about this the whole time. You can get an FPS boost from fixing up pathfinding a bit--6% is 6%, reducing that helps!--but FPS death will set in just as it does now, even with magic oracle pathfinding that takes 0 time. It's not a pathfinding issue.
If I seem bothered by this, it's because I pondered the pathfinding a good deal too before I actually bothered to do the bare minimum work in actually figuring out why the game runs slowly and learned that, no, pathfinding has basically nothing to do with it. I literally had to be handed a save that had a pathfinding edge case (24 tightly-closed doors) before I even found the pathfinding function, since it's buried so deep due to its, again, not being a major use of CPU time.
-
Not to say there isn't some major high-level optimizations to be made. A lot of the CPU time in unit checks is wasted in branch misprediction due to the fact that it's checking the units vector and just skipping everything that happens to be inactive/caged/a ghost; if those units' indices (or pointers to them, as the case happens to be, unfortunately) were simply cached in a vector that contains only active/uncaged/non-ghostly units, that would be avoided and the game would probably run quite a bit faster.
(Emphasis added)
-
So the last time I played (a while ago) the way to keep early game FPS at a reasonable level was to just have a very small embark space. Could you have a larger embark space, but keep # of units low and still keep it reasonable, if the major problem is units checking over units? Does this mean it would run quicker if you split up your dwarves into different warrens which rarely interacted (so less units seeing over units)?
-
good to read some firm words from Putnam on the issue. *pulls up a lawn chair*
units checking other units for line-of-sight/proximity checks (running away from hostiles etc), which is more like 20%.
so when people complain about fliers, does this also hold true? is it because large groups of flying kea are scouting many more units from their heavenly perspective?
disturbingly, it may be the case that a panopticon is the most efficient fortress design. what horrible reality have you created Tarn?!
-
I wonder what the performance impact might be to keep an index of only "active" units like that up to date would be. Naively I'd assume that it's something that doesn't change frequently and thus should be pretty low impact, but I don't remember exactly how C++ vectors handle things like deletion of elements in in the middle. Did that require copying / moving all elements after the deleted one? I guess shuffling even a few thousand pointers should have minimal impact if it only happens every few frames or however often it happens.
-
I wonder what the performance impact might be to keep an index of only "active" units like that up to date would be. Naively I'd assume that it's something that doesn't change frequently and thus should be pretty low impact, but I don't remember exactly how C++ vectors handle things like deletion of elements in in the middle. Did that require copying / moving all elements after the deleted one? I guess shuffling even a few thousand pointers should have minimal impact if it only happens every few frames or however often it happens.
What about using a linked list instead?
-
Playing on a Mac, and I've thought for a while this was a Windows OS issue. Back before the issue with travellers from outside the map (currently I don't get migrants, caravans, etc, because of a machine upgrade) my Mac had no FPS issues, even with an in-game decades old game. Even now, with the game only just not working, no FPS issues. I am aware that I'm basically running the thing on WINE or whatever, but still, seems odd that it's not an issue for me. Is there something different about your OS handling the game?
-
That's good to know, at least. My fortress design tends to be a bit antagonistic towards optimizing for pathfinding, so good to know that won't kill FPS.
-
I wonder what the performance impact might be to keep an index of only "active" units like that up to date would be. Naively I'd assume that it's something that doesn't change frequently and thus should be pretty low impact, but I don't remember exactly how C++ vectors handle things like deletion of elements in in the middle. Did that require copying / moving all elements after the deleted one? I guess shuffling even a few thousand pointers should have minimal impact if it only happens every few frames or however often it happens.
What about using a linked list instead?
Linked list traversal is very slow compared to iterating over a vector so I'd expect it to be a bad trade, but it depends on the typical size of the collection and how often it changes. I haven't profiled any of it myself of course, so I'm not sure what typical numbers would be.
A funny thought would be just sorting the unit vector by active / inactive status, but sorting it may not have a trivial time component and isn't particularly useful if there are multiple flags or fields it checks for this purpose. I suspect there are multiple unrelated fields.
On this topic, I'm wondering what the implications would be on cache misses if a separate index were used that stored pointers to the units. If their status changed and they were removed and added back then the index would get out of order and lead to poor cache coherency, unless efforts were taken to prevent that. No idea how much that would compare to branch prediction misses on a modern desktop CPU but I'm guessing it's not trivial. Then again, my guess is that DF probably has a lot of cache problems because of how much it keeps track of.
-
That example of 6% and 20% gives no example of the scale of the fort's population and layout. If Observation checks were using 20% CPU, is this because there are 300 dwarfs in a 20x20 room?
I'm thinking of how I often set up a single room with a temple, tavern, library, and barracks in it, and dwarfs gain in observation skills because of this.
-
That example of 6% and 20% gives no example of the scale of the fort's population and layout. If Observation checks were using 20% CPU, is this because there are 300 dwarfs in a 20x20 room?
I'm thinking of how I often set up a single room with a temple, tavern, library, and barracks in it, and dwarfs gain in observation skills because of this.
So… dwarves only ever check to see if they have line of sight of each other if they have line of sight of each other?
-
good to read some firm words from Putnam on the issue. *pulls up a lawn chair*
units checking other units for line-of-sight/proximity checks (running away from hostiles etc), which is more like 20%.
so when people complain about fliers, does this also hold true? is it because large groups of flying kea are scouting many more units from their heavenly perspective?
disturbingly, it may be the case that a panopticon is the most efficient fortress design. what horrible reality have you created Tarn?!
Every unit must check every other unit to see if they're in line-of-sight; this is actually basically unavoidable. It's not the line-of-sight checks that are the problem, it's the checking for line-of-sight. Skipping over units that literally cannot be seen by anyone even in principle takes up more CPU time than pathing.
I wonder what the performance impact might be to keep an index of only "active" units like that up to date would be. Naively I'd assume that it's something that doesn't change frequently and thus should be pretty low impact, but I don't remember exactly how C++ vectors handle things like deletion of elements in in the middle. Did that require copying / moving all elements after the deleted one? I guess shuffling even a few thousand pointers should have minimal impact if it only happens every few frames or however often it happens.
It's O(n) to remove from the middle. This would only happen when units die, become caged or leave the map, though, which is rather rare. "Every few frames" is a massive overestimation, orders of magnitude more often than it's likely to actually happen.
I wonder what the performance impact might be to keep an index of only "active" units like that up to date would be. Naively I'd assume that it's something that doesn't change frequently and thus should be pretty low impact, but I don't remember exactly how C++ vectors handle things like deletion of elements in in the middle. Did that require copying / moving all elements after the deleted one? I guess shuffling even a few thousand pointers should have minimal impact if it only happens every few frames or however often it happens.
What about using a linked list instead?
Since we're talking about something you iterate over, you want a vector, no other choice. Linked list iteration is pretty bad, as mentioned earlier. The fact that removal from the vector is rare (only when units leave/die) means that its worse asymptotic performance isn't terribly relevant.
That example of 6% and 20% gives no example of the scale of the fort's population and layout. If Observation checks were using 20% CPU, is this because there are 300 dwarfs in a 20x20 room?
I'm thinking of how I often set up a single room with a temple, tavern, library, and barracks in it, and dwarfs gain in observation skills because of this.
The checks have little to do with actually being able to see other units. It has to check every unit regardless. Literally half of the CPU time spent in there was skipping over dead/caged units due to branch misprediction. IIRC this fort was something like 100 citizens, where they were doesn't really matter due to the previous. It also has nothing to do with the observation skill, not sure where that comes from. This is the basic checks that e.g. make dwarves run away and cancel jobs.
-
Hmm - so the solution is still the same, right? Atom-smashing corpses and occasionally, your own dwarves.
Does this new-found knowledge help us understand how to optimize our own games a bit more? Maybe...blinding dwarves?
-
Guys, the ideal data structure would be a hash table, e.g. std::unordered_set, no? O(1) insertion, deletion, iteration, at least in theory. At most there could be some data locality issues with jumping between different buckets.
EDIT: Also there is probably something clever you might do for line-of-sight checks. Creatures can only see so far, right? Assign each creature to a set of rectangular blocks which they might potentially be able to see in, then only check line-of-sight in those blocks.
-
Every unit must check every other unit to see if they're in line-of-sight; this is actually basically unavoidable. It's not the line-of-sight checks that are the problem, it's the checking for line-of-sight. Skipping over units that literally cannot be seen by anyone even in principle takes up more CPU time than pathing.
thanks for the clarification. this truly is something us players cannot avoid.
I love the idea that you drop this info less than a month away from the new release - after years and years of (what ultimately appears to be) superstitious rituals in the name of saving FPS.
-
The data structure doesn't matter here. The point is that it's checking every unit against every other unit to work out whether or not they can see each other. This is, fundamentally, O(n^2). The problem isn't actually evaluating the line of sight. The problem is having to, per unit, check against literally every other unit on the map, is slow in principle. Limiting it to a rectangle would trade-off O(n^2) for O(Pn) where P is the number of tiles in this rectangle. Depending on the size of P, this might not scale as well as you'd hope; it only becomes more efficient once you have more units than P. Meaning if you're checking, say, a 10x10 rectangle around every unit, that this only becomes more optimal at 100 units on the map or more.
I think a more immediate optimization is clearing out dead units from the vector. Yes, removing from the middle of a vector isn't optimal, but that doesn't matter because this is a one-time event any time a unit dies/leaves. Just make it a periodic check when iterating through the table that if any of the pointers refer to dead units, to delete them from the vector before continuing.
-
How do items fit into this modelling of the Observation code? A dwarf sees a severed limb on the ground and knows if it belongs to a dead or living unit.
-
Guys, the ideal data structure would be a hash table, e.g. std::unordered_set, no? O(1) insertion, deletion, iteration, at least in theory. At most there could be some data locality issues with jumping between different buckets.
EDIT: Also there is probably something clever you might do for line-of-sight checks. Creatures can only see so far, right? Assign each creature to a set of rectangular blocks which they might potentially be able to see in, then only check line-of-sight in those blocks.
Iteration on unordered_map is likely to be worst than iteration over a vector, and iteration's the one thing you'll be doing most here. Iteration can't be faster than O(n). If you have a quantum computer, linear search is O(sqrt(n)), but that's not terribly relevant.
That second bit is quadtrees etc., which could work but has overhead unto itself.
Every unit must check every other unit to see if they're in line-of-sight; this is actually basically unavoidable. It's not the line-of-sight checks that are the problem, it's the checking for line-of-sight. Skipping over units that literally cannot be seen by anyone even in principle takes up more CPU time than pathing.
thanks for the clarification. this truly is something us players cannot avoid.
I love the idea that you drop this info less than a month away from the new release - after years and years of (what ultimately appears to be) superstitious rituals in the name of saving FPS.
Yeah, sorry, I got into profiling in earnest after I learned how easy it was working on Cataclysm DDA and auxmos (https://github.com/Putnam3145/auxmos), started doing it to see if I can find any funnies, eventually figured out what pathfinding was by getting a real bad FPS death fort with tightly-closed doors and seeing the big problem there... it took me a while for a few reasons.
How do items fit into this modelling of the Observation code? A dwarf sees a severed limb on the ground and knows if it belongs to a dead or living unit.
It honestly probably just goes through the corpses vector, which is only in-play, active corpses. Not nearly as much worry.
-
Very interesting, thanks for posting this. Do above ground fort areas, big rooms with lots of workshops inside and big dormatory/dining room/tavern make massive difference in these calculations?
Reason why I ask is because I have pop 80, 2x2 forts that follow all FPS advice I studied in dozens of hours and experimented 100s of hours with but I still get FPS issues after 5-10+ years.
I always use big rooms like that instead of lots of small rooms so maybe that's bad too because theres more exponential interaction between creatures in the same room/line of sight?
-
Very interesting, thanks for posting this. Do above ground fort areas, big rooms with lots of workshops inside and big dormatory/dining room/tavern make massive difference in these calculations?
Reason why I ask is because I have pop 80, 2x2 forts that follow all FPS advice I studied in dozens of hours and experimented 100s of hours with but I still get FPS issues after 5-10+ years.
I always use big rooms like that instead of lots of small rooms so maybe that's bad too because theres more exponential interaction between creatures in the same room/line of sight?
Recent testing suggests "not really". Been running a 6x6 fort with 70-80 citizens entirely above-ground at 30 FPS for 6 (8? I forgot to note down the year the fort started lol) in-game years now.
The problem isn't the interactions, the problem is checking for interactions. Every creature must check every other creature no matter what, essentially. There's optimizations to be made there with sectors etc. but the overhead might not be worth it.
-
Limiting it to a rectangle would trade-off O(n^2) for O(Pn) where P is the number of tiles in this rectangle. Depending on the size of P, this might not scale as well as you'd hope; it only becomes more efficient once you have more units than P. Meaning if you're checking, say, a 10x10 rectangle around every unit, that this only becomes more optimal at 100 units on the map or more.
Just to say, the example of P=100 could make it sound as if there might be a reasonable inflection point where the savings is worth it in the case of large, populous fortresses. Alas, this discussion – http://www.bay12forums.com/smf/index.php?topic=180525.msg8425293#msg8425293 – declares that legendary Observers have a vision radius of 25 tiles. Extended in all possible directions, I think(?) that's a "theoretical" detection volume in the neighborhood of P=125000 tiles as the game currently stands. Edit: no, messed that up in my head. Nearer to P≈25000?
-
The data structure doesn't matter here. The point is that it's checking every unit against every other unit to work out whether or not they can see each other. This is, fundamentally, O(n^2). The problem isn't actually evaluating the line of sight. The problem is having to, per unit, check against literally every other unit on the map, is slow in principle. Limiting it to a rectangle would trade-off O(n^2) for O(Pn) where P is the number of tiles in this rectangle. Depending on the size of P, this might not scale as well as you'd hope; it only becomes more efficient once you have more units than P. Meaning if you're checking, say, a 10x10 rectangle around every unit, that this only becomes more optimal at 100 units on the map or more.
The data structure was about storing units in such a way that there is fast deletion and iteration. By O(1) iteration I meant O(1) from one unit to the next. The data structure is not for speeding up individual 1-on-1 sight checks.
I've realized that the fastest solution is very simple. When deleting a unit, swap the unit in the vector with the last unit, then remove from the back. Remember, order doesn't matter.
The second rectangular blocks part was about eliding unnecessary sight checks. Also, your 100n estimation for the blocks approach is off. You don't check every unit against every tile in the block, you check every unit against every other unit in the block. If there were 5 units in each occupied 10x10 block, then there would be 4n sight checks.
In general the time complexity is O(mn) where the parameter n is the number of units and the parameter m is the quadratic mean average number of units in each occupied block. Asymptotically there are far fewer units in each occupied block than there are units on the map. Thus this gives almost linear performance
as long as the units are decently spread out.
-
You also have to check every unit in the surrounding blocks, mind, else you get weird behavior on block edges.
-
You also have to check every unit in the surrounding blocks, mind, else you get weird behavior on block edges.
You're right. You could check every block that intersects the unit's view rectangle. Should be at most 4.
-
Very interesting, indeed
-
Don't forget that you're operating in 3 dimensions, here, though that won't add much overhead.
But yeah, chunking out the map into a series of 24x24x24 blocks isn't unreasonable. Then you'd have a (constant-sized) vector of... unordered maps (iteration is as cheap as any other and inserting/erasing should be constant on average). On each unit update, add a check for x/y/z divided by 24 before and after their move to work out what box they were in and what box they should move to. Depending on whether DF uses C++17, you can even do fancy things like extract the nodes so there's not even a memory overhead of moving the entries around. Then instead of checking against every unit in the game, you check against every unit in 27 24x24x24 boxes.
I think you'd still end up checking against a whole lot of units this way, though.
-
So I guess I need to sell that cage in my fortress with 300+ chicken inside?
Do you think I need to wall off all the cave entrance, or maybe even extinct the local fauna? Sometimes there are more wild crundle in my map than my dwarves, which according to your study is a pretty bad thing.
-
So I guess I need to sell that cage in my fortress with 300+ chicken inside?
Do you think I need to wall off all the cave entrance, or maybe even extinct the local fauna? Sometimes there are more wild crundle in my map than my dwarves, which according to your study is a pretty bad thing.
actually, this is a good question: do creatures inside cages perform this "unnecessary sight-check", or are they exempt? AFAIK creatures cannot spot intruders from within cages..
-
So I guess I need to sell that cage in my fortress with 300+ chicken inside?
Do you think I need to wall off all the cave entrance, or maybe even extinct the local fauna? Sometimes there are more wild crundle in my map than my dwarves, which according to your study is a pretty bad thing.
actually, this is a good question: do creatures inside cages perform this "unnecessary sight-check", or are they exempt? AFAIK creatures cannot spot intruders from within cages..
<snip>
A lot of the CPU time in unit checks is wasted in branch misprediction due to the fact that it's checking the units vector and just skipping everything that happens to be inactive/caged/a ghost;
<snip>
(emphasis added)
-
thanks. I am a lazy bastard
-
This is incredibly interesting Putnam, thanks for this.
I understand that profiling is still in progress and it sounds like you've given your findings so far, and more is dependent on discovering other heavily-trafficked areas of code etc.
Have you found anything regarding number of items lying around? This is the next thing I've heard from a lot of people recently, that if pathfinding killing FPS is a myth then it must be overproduction. Having 10,000 roasts in storage when 500 would suffice.
I suppose FPS issues in this vein could be related to literally just having a lot of objects; or the work constantly being performed to produce these objects (i.e. socializing is a low FPS operation by comparison); or the jobs generated by all these objects ("put me in a stockpile!").
So far it sounds like FPS is strongly related to actors and not inert objects. There's also long been evidence that flow, pumps, mist, smoke etc. are high FPS operations.
-
I feel like line of sight checks could be made better than O(n^2). Each unit "has" to check every other unit, but once a line has been checked between two units, you dont have to run the same check for the other unit, right? Just mark each unit that has made its check each tick, and when another unit's check encounters the first unit, skip the math. I think this would bring it down to order of... something I don't know how to calculate, but less than quadratic since the number of new math that has to be done would be less and less for each unit.
-
I feel like line of sight checks could be made better than O(n^2). Each unit "has" to check every other unit, but once a line has been checked between two units, you dont have to run the same check for the other unit, right? Just mark each unit that has made its check each tick, and when another unit's check encounters the first unit, skip the math. I think this would bring it down to order of... something I don't know how to calculate, but less than quadratic since the number of new math that has to be done would be less and less for each unit.
Observation differs from unit to unit and is not symmetric, so this doesn't quite work.
-
I feel like line of sight checks could be made better than O(n^2). Each unit "has" to check every other unit, but once a line has been checked between two units, you dont have to run the same check for the other unit, right? Just mark each unit that has made its check each tick, and when another unit's check encounters the first unit, skip the math. I think this would bring it down to order of... something I don't know how to calculate, but less than quadratic since the number of new math that has to be done would be less and less for each unit.
It's still quadratic. This is the same as handshakes avoiding double counting, which is (n^2+n)/2, or sum of 1 to n.
This is incredibly interesting Putnam, thanks for this.
I understand that profiling is still in progress and it sounds like you've given your findings so far, and more is dependent on discovering other heavily-trafficked areas of code etc.
Have you found anything regarding number of items lying around? This is the next thing I've heard from a lot of people recently, that if pathfinding killing FPS is a myth then it must be overproduction. Having 10,000 roasts in storage when 500 would suffice.
I suppose FPS issues in this vein could be related to literally just having a lot of objects; or the work constantly being performed to produce these objects (i.e. socializing is a low FPS operation by comparison); or the jobs generated by all these objects ("put me in a stockpile!").
So far it sounds like FPS is strongly related to actors and not inert objects. There's also long been evidence that flow, pumps, mist, smoke etc. are high FPS operations.
From what I can tell, items are a concern... but you can almost completely mitigate items' impact on performance by turning off temperature, so that's easy enough.
Flow, pumps and smoke all have something in common: they require things to repath. Pathfinding isn't normally a major cause of FPS issues, but this is because it's done rarely; when something forces pathfinding to happen more often, it'll get far, far worse.
-
I have some questions:
1. Have you contacted Tarn about the potential optimization of caching active/uncaged/non-ghostly units yet?
From what I can tell, items are a concern... but you can almost completely mitigate items' impact on performance by turning off temperature, so that's easy enough.
2. Have you found any possible ways via profiling that temperature for items can be optimized, or is a mostly hopeless "this is as good as it gets for items"?
Flow, pumps and smoke all have something in common: they require things to repath. Pathfinding isn't normally a major cause of FPS issues, but this is because it's done rarely; when something forces pathfinding to happen more often, it'll get far, far worse.
3. Taking your own advice from the OP about profiling... Are you sure it's the pathfinding, and that the actual calculations of flow/which tiles to change aren't a significant/primary part of it?
4. Wouldn't optimizing pathfinding help with both the meager 6% for a normal fortress, and also the slowdowns associated with flows and stuff? Some forms of FPS death, as far as I know (I'll admit I haven't played in a long time; waiting for Premium UI changes), are "I want fancy flows and mist things, but it kills the FPS".
-
I tend to characterize FPS death as "the unavoidable slow death of any and all fortresses to poor optimization", since that's the way people talk about it. People doing things that are known FPS killers and being surprised when they kill FPS feels like something that should be ignored rather than lumped into that.
2. Have you found any possible ways via profiling that temperature for items can be optimized, or is a mostly hopeless "this is as good as it gets for items"?
No, I can't even find it, ha. Every in-play items needs iterated over for temperature, and it does iterate over only items that are in-play, so I'm not sure there's much that can be improved on there.
3. Taking your own advice from the OP about profiling... Are you sure it's the pathfinding, and that the actual calculations of flow/which tiles to change aren't a significant/primary part of it?
Understandable, and the answer's "I haven't profiled hitches due to flow stuff", but the other answer is "ordinary flow through large corridors and such that aren't being pathed through by units doesn't slow down the game to the single-digits while flooding that actually crosses unit paths does", which is pretty good evidence. It's also a problem with the connectivity map (note how there's no hitch before the game says "no path" if you try to send a soldier somewhere they can't reach), having to rebuild that too often will cause problems.
4. Wouldn't optimizing pathfinding help with both the meager 6% for a normal fortress, and also the slowdowns associated with flows and stuff? Some forms of FPS death, as far as I know (I'll admit I haven't played in a long time; waiting for Premium UI changes), are "I want fancy flows and mist things, but it kills the FPS".
Yes, but making pathfinding twice as fast will still mean the game goes into the single digits during such events, and making pathfinding twice as fast isn't terribly feasible. Making it multithreaded and letting the game run while long pathfinding operations happen would make the game 100% non-deterministic, with completely different behavior on different CPUs, so that's a no-go.
1. Have you contacted Tarn about the potential optimization of caching active/uncaged/non-ghostly units yet?
I'm. Not actually sure? I've contacted him about a good deal of that sort of thing in the upcoming release, actually.
Er, most of my profiling is from the upcoming release, I have it in advance for testing reasons. I only got the go-ahead to say that this morning and I apologize if anything I said here made it seem like I'm doing all my profiling in 0.47.05; for stuff like this, I try to keep it vague enough that I don't even need plausible deniability, since I hate denying. Anyway, yeah, I've been pointing out anything particularly odd that I come across, since the point of testing is to make sure release goes smoothly and all. This is why I've been profiling so aggressively lately and part of why I seem so confident in some of my assertions, a lot of my reverse engineering has been done with a back-and-forth with Tarn trying to suss out the exact thing I'm looking at.
I think the 6% value is from the upcoming version, or at least an earlier version of it (it's not final! my word is not law! et cetera!), but I'm actually not sure, since I haven't been labeling my profiles correctly (I don't even know how with vtune, lol). I don't think pathfinding has been changed at all for the upcoming version, though, so it should be still approximately valid.
I did a 6x6 fort earlier, lasted 25 years. It succumbed to FPS death to an extent near the end, sub-20 FPS, but I eventually figured out that this happened because I completely failed to notice a rabbitsplosion. That and the fact that there were over 100 ghosts, maybe. It was not a good fort. I was just doing it to see if there are any crashes in large embarks, since an easy "kill my game please" button is kinda a bad thing to have in a commercial release. Turns out 6x6 forts actually run about as well as 2x2, which is... really, really not the result I expected. The main difference is that getting spooked by marauding invaders causes much, much worse FPS dips, which is the whole "repathing" thing again, I think? Also, one of the main slowdowns was now something I suspect is "tile activity", plant growth etc.
The upshot of all this is, like. My numbers might be slightly too low? Display takes more time now, which lowers the %s on basically everything else by necessity, but it's threaded so it doesn't matter terribly much. This isn't new, believe it or not, 0.47.05 also has threaded display.
-
Tile activity? I'm surprised that makes a major contribution to performance drain. Is the implication there that as you mine things out underground that there are more tiles that have to be considered, to the point it eventually becomes a notable problem?
Yes, but making pathfinding twice as fast will still mean the game goes into the single digits during such events, and making pathfinding twice as fast isn't terribly feasible. Making it multithreaded and letting the game run while long pathfinding operations happen would make the game 100% non-deterministic, with completely different behavior on different CPUs, so that's a no-go.
You know, I've actually wondered about this before. Does it really matter if the pathfinding is done asynchronously and non-deterministically? I guess if the game's internals make strong assumptions that paths are well realized and accurate then trying to retrofit something else into it would be hard, but I'm not sure that it's a strict requirement. I could have sworn that the game already accounted for paths being unexpectedly impassable as creatures followed them, where they stop for a few frames. Maybe that was when an item or workshop was suddenly unavailable instead. It's been literal years since I've played.
Anyway, I guess it may not really help if the game went from having to do big pathfinding crunches when the map topology changes to suddenly having to do checks before a creature walks to an adjacent tile to account for the path being potentially outdated. It might make for a smoother experience, but probably a slower one overall.
It's all fairly academic if it's a rare occurrence anyway.
-
Tile activity? Interesting... I suppose there's not really a nice way to handle things like that. I guess the best you can do is work out a more convenient mechanism to exclude tiles from tile activity and then avoid evaluating whether or a tree should sprout or what-have-you unless the circumstances change. Which, if I had to guess, is already being done.
Still, the numbers given (25-year 6x6 fort dipping below 20FPS with 100 ghosts and only due to a rabbitsplosion) is... really, really reassuring to say the least.
-
What about the thing that I saw discussed on the Kitfox Discord? I forget what exactly was said, but it was something about setting "normal pathing" (probably not the right phrase) to 0 and other paths to 1 giving a big boost? What's the deal with that?
I did a 6x6 fort earlier, lasted 25 years. It succumbed to FPS death to an extent near the end, sub-20 FPS, but I eventually figured out that this happened because I completely failed to notice a rabbitsplosion. That and the fact that there were over 100 ghosts, maybe. It was not a good fort. I was just doing it to see if there are any crashes in large embarks, since an easy "kill my game please" button is kinda a bad thing to have in a commercial release. Turns out 6x6 forts actually run about as well as 2x2, which is... really, really not the result I expected.
But did you test 16x16 though? ;D
-
alright, but like, pathfinding seems like it could be causing, not fps loss outright, but instead stutter. where there's a huge spike in the pathfinding calculations every so often, making the game feel like a slideshow.
i don't know if this doesn't actually happen.
if we assume like, half the frames remain and the other half are basically the game freezing up, it would be a stutter-step fps death. then multiply that with a little path-unfriendly fortress design...
-
thanks again for the explanations, super interesting to read.
Turns out 6x6 forts actually run about as well as 2x2, which is... really, really not the result I expected. The main difference is that getting spooked by marauding invaders causes much, much worse FPS dips, which is the whole "repathing" thing again, I think? Also, one of the main slowdowns was now something I suspect is "tile activity", plant growth etc.
I can agree from my own experience regularly running large embarks. they function about the same as smaller embarks, until you get your first kea invasion, or your forests start to fill out and grow tall, or you dig too many surface tiles..
then FPS goes to sh*t
-
Tile activity? I'm surprised that makes a major contribution to performance drain. Is the implication there that as you mine things out underground that there are more tiles that have to be considered, to the point it eventually becomes a notable problem?
A bit, yes. Toady pointed out "digging out entire layers" as a potential problem in the recent interview. But the fact is that a 6x6 embark is 9x as big as a 2x2 embark, so that's the bigger thing.
-
Re: temperature improvements.
From what I understand temperature is only used for phase changes right now. In that case I think iterating over every item is not really necessary.
There could be a running index of next high phase change temperature TH and next low phase change temperature TL for each tile. This guarantees any temperature within that range will have no effect and can be ignored. This index is a function of the items in a tile, and so is updated only when items move/are created/are destroyed. This is a low cost update since it is rare and there are already tile occupancy stuff, etc. to change when items move.
Now whenever temperature changes, which is also pretty light, it would query the phase change temperature limits and if they are exceeded, then an iteration through the specific items in that tile can happen.
As a result the total cost is on the order of U + M where U is the number of temperature changes and M is the number of items that move. This is less than U + I where I is the total number of items.
In particular, items in constructions which are often a drag on FPS, wouldn't matter. Items in stockpiles would rarely matter unless they are taken out. Magma flow still has frequent temperature updates however.
But all in all if you don't have any major temperature swings in your fortress the temperature calculation cost should be nearly zero.
-
The game actually does use SPEC_HEAT. Heat transfer, per tick, adds (environment temp-item temp) to the fractional portion of the item's temperature fixed point, and if the item's fractional portion is > the SPEC_HEAT of the material, it rolls over to the next.
Temperature is a 32-bit fixed point, 16 bites reserved for the whole part and fractional part each. If e.g. iron is 1000 degrees hotter than the environment, it'll cool by 1000 fractional parts, which means next tick it'll be at (assuming the environment here is 10000) 10097+350 fractional part, which is of course 10097.777... degrees.
-
There is a saying that quantum stockpile improves FPS performance due to render less items on the screen, and even the official wiki mentioned it （but it stated that this fact isn't proven). Is this true or is it a myth?
-
Yeah, the rendering of the tiles themselves is threaded but putting together everything that needs to be rendered takes some time. It ought to be negligible, though, like, only noticeable if you're a weirdo who plays at 1200 FPS like me.
-
The game actually does use SPEC_HEAT. Heat transfer, per tick, adds (environment temp-item temp) to the fractional portion of the item's temperature fixed point, and if the item's fractional portion is > the SPEC_HEAT of the material, it rolls over to the next.
Temperature is a 32-bit fixed point, 16 bites reserved for the whole part and fractional part each. If e.g. iron is 1000 degrees hotter than the environment, it'll cool by 1000 fractional parts, which means next tick it'll be at (assuming the environment here is 10000) 10097+350 fractional part, which is of course 10097.777... degrees.
Ah... interesting. In that case you can remove from the list any items that have reached environmental temperature, which is most of them, no?
-
I think it would depend in part on how much 'environmental temperature' is subject to change. Outdoor weather, for instance. Also, many items (anything worn/equipped, anything in a minecart, etc.) can move from tile to tile. One can easily check if an item matches the tile temperature on the current tick, but that equality is in my opinion an uncomfortably loose predictor as to whether it continues to match its tile temp in the next tick.
(Edit: I only half-expressed my concern.)
-
What about the thing that I saw discussed on the Kitfox Discord? I forget what exactly was said, but it was something about setting "normal pathing" (probably not the right phrase) to 0 and other paths to 1 giving a big boost? What's the deal with that?
You're thinking of a post where someone researched the effects of using different Traffic Designations, and of using init.txt to change some of those to 0 or -1 cost. I'll try to find you the exact thread.
-
What about the thing that I saw discussed on the Kitfox Discord? I forget what exactly was said, but it was something about setting "normal pathing" (probably not the right phrase) to 0 and other paths to 1 giving a big boost? What's the deal with that?
EDIT: snip
-
A lot of the CPU time in unit checks is wasted in branch misprediction due to the fact that it's checking the units vector and just skipping everything that happens to be inactive/caged/a ghost; if those units' indices (or pointers to them, as the case happens to be, unfortunately) were simply cached in a vector that contains only active/uncaged/non-ghostly units, that would be avoided and the game would probably run quite a bit faster.
So does this mean that caging excess livestock is actually worse, or am I misreading things?
-
It's better, it's just not as much better as it could be.
-
It's better because otherwise the game would actually be doing sight checks for the livestock if they were out of the cage, instead of just branch mispredicting on them.
-
Very interesting read, thanks for your efforts, Putnam!
I've always tried to read through discussions on FPS loss when I play over the years, and I hate constantly having in the back of my head, "Well I could design this section of the fort the way I actually want, but instead I need to think about what will be the most FPS-friendly since every fort is playing on a time-limit."
I have always worried about how much of it is actually accurate and how much is just speculation / rumour, so it's nice to get a little verification on which factors are significant or not.
In particular, does this issue with units checking every other unit make any difference on whether a dead dwarf was buried in a coffin vs. atomsmashed / burned in magma? I know you mentioned that ghosts contribute to the "checking for line of sight," but assuming you have slabs for all dead dwarves, is there any one particular method of body disposal that would be "best" as far as mitigating the number of units needing to check each other?
-
Sounds like Toady just needs to do for units what he's already done with df.global.world.items.other vectors.
-
Very interesting read, thanks for your efforts, Putnam!
I've always tried to read through discussions on FPS loss when I play over the years, and I hate constantly having in the back of my head, "Well I could design this section of the fort the way I actually want, but instead I need to think about what will be the most FPS-friendly since every fort is playing on a time-limit."
I have always worried about how much of it is actually accurate and how much is just speculation / rumour, so it's nice to get a little verification on which factors are significant or not.
In particular, does this issue with units checking every other unit make any difference on whether a dead dwarf was buried in a coffin vs. atomsmashed / burned in magma? I know you mentioned that ghosts contribute to the "checking for line of sight," but assuming you have slabs for all dead dwarves, is there any one particular method of body disposal that would be "best" as far as mitigating the number of units needing to check each other?
Doesn't make a difference, unit's still loaded anyway. DFHack's fix/dead-units unloads them either way, though.
-
Doesn't make a difference, unit's still loaded anyway. DFHack's fix/dead-units unloads them either way, though.
Good to know, thanks! Already updating my standard "FPS best practices" personal notes I keep in anticipation of the Steam release.
-
Guys, the ideal data structure would be a hash table, e.g. std::unordered_set, no? O(1) insertion, deletion, iteration, at least in theory. At most there could be some data locality issues with jumping between different buckets.
The principal high-load use for this data requires enumerating it, not searching it by a key, and so a contiguously allocated vector, ideally aligned with cache line boundaries, is what you want for peak performance.
-
I'm a rather non-technical person (though, I do wish I had the brainpower for coding and understanding it!), but my take on this whole discussion so far is: keep populations lower. Its difficult/impossible to control the presence of wildlife, raiders, sieges, etc, but pop-control is easier for your dorfs and their pets/livestock/etc. Keeping those lower should help? (edit: also lowering the number of allowed visitors!)
Also, are vermin counted in these "checking everything for presence of LOS" checks?
-
Then some question about fortress optimisation, on DF 34.11 there was this :
https://dffd.bay12games.com/file.php?id=7750
that was having 400 dwarves , lots of items ... while not suffering from any fps death, it was actually running quite fast.
What was the reason of this , even when i was playing on 34.11 i never saw something running well once i started to get a hundred of dwarves on small map size like that ?
-
It helps just to know that the length of the unit vector matters. Thanks!
Maybe that's a step towards being able to write dfhack scripts to clean up that and other structures that expand during fortress mode? Is there anything from world activation that's growing unbounded and not being trimmed like it would be in worldgen?
Fortresses at FPS death don't have THAT many more units/items/etc if you've been careful about keeping the fort clean. Is there also a giant array of dirty socks or fire ash or pecans somewhere killing the game?
-
My personal non-verified belief is that trees and junk amount to a lot of FPS death.
I'm pretty sure all items are simulated also regarding their tempature and dryness/wetness and so on. So if you have thousands and thousands of items like avocado pits and xxxsockxxx and so on, it's got to use computing power.
I started atom smashing junk straight from the z-screen, where you can really have thousands and thousands of leftover junk items generated for instance by avocados. Some plants generate a waste item, you also get peach pits for instance. And you can easily have 10K of those lying around sucking computing power without even being aware of it.
Another belief I have is that TREES slow down the game. I read somewhere the game simulated the growth of branches and twigs and so on, so a single tree must take up computing power.
I had some forts that were in heavily forested areas and grind slowly to a half, destpite the population not growing a lot. Since then I've taken to do very heavy-handed forest management, preventively clearing most of the surface from trees - and it seems to work.
-
My personal non-verified belief is that trees and junk amount to a lot of FPS death.
I'm pretty sure all items are simulated also regarding their tempature and dryness/wetness and so on. So if you have thousands and thousands of items like avocado pits and xxxsockxxx and so on, it's got to use computing power.
I started atom smashing junk straight from the z-screen, where you can really have thousands and thousands of leftover junk items generated for instance by avocados. Some plants generate a waste item, you also get peach pits for instance. And you can easily have 10K of those lying around sucking computing power without even being aware of it.
Another belief I have is that TREES slow down the game. I read somewhere the game simulated the growth of branches and twigs and so on, so a single tree must take up computing power.
I had some forts that were in heavily forested areas and grind slowly to a half, destpite the population not growing a lot. Since then I've taken to do very heavy-handed forest management, preventively clearing most of the surface from trees - and it seems to work.
No, no, this is pretty verified. The slowest parts of a 6x6 fort I ran for 25 years were:
1. some sort of map activity that I'm like 50% sure was tree/plant growth
2. temperature
So this is, in fact, borne out by the data.
But this can be mitigated massively by just playing on a smaller embark.
-
Obviously the correct solution is to pave all growable soil on the surface.
-
Obviously the correct solution is to pave all growable soil on the surface.
Or just dig away the soil layers, so it's just lovely bare rock.
-
What's the (software) caching of LOS like? AFAICT, whether Urist McAlice can see Urist McBob can change if either of them move, if Urist McAlice gets her eyes stabbed out etc. or if some bit of the environment that affects LOS changes.
So you could have an nxn matrix for your n units used as a cache. Whenever a unit moves, its row and column are wiped. Whenever something in the world changes e.g. a tree is felled so you can see through where the trunk used to be, the whole matrix is wiped (or maybe you can find a way to only wipe a subset of it). World LOS changes don't seem to happen that often unless something weird is happening like obsidian is being formed so you'd usually only have to recalculate LOS relating to entities that moved last tick.
Sorry if this is a bad suggestion I seldom stray this close to bare metal. IDK if it would play nice with the crazy optimisations CPUs do nowadays.
-
I'm not sure there is any.
On my latest fort, which currently has 270 citizens, the "can I see these units?" check has been overtaken by a huge margin by checks that I'm pretty sure are actually line-of-sight stuff, so hey, ignore my advice earlier, you totally should try to keep dwarves from clustering up too hard.
To be specific, it's something that checks that both units are historical figures and then checks their relationships to each other--might have to do with family needs? It's kinda hard to tell what's actually happening, but there's a lot of binary searching through the hist figure vector going on.
-
To be specific, it's something that checks that both units are historical figures and then checks their relationships to each other--might have to do with family needs?
That might also be villain/intrigue stuff, there's a lot of little variables there that afaik are largely in the histfig?
-
My personal non-verified belief is that trees and junk amount to a lot of FPS death.
I'm pretty sure all items are simulated also regarding their tempature and dryness/wetness and so on. So if you have thousands and thousands of items like avocado pits and xxxsockxxx and so on, it's got to use computing power.
I started atom smashing junk straight from the z-screen, where you can really have thousands and thousands of leftover junk items generated for instance by avocados. Some plants generate a waste item, you also get peach pits for instance. And you can easily have 10K of those lying around sucking computing power without even being aware of it.
Another belief I have is that TREES slow down the game. I read somewhere the game simulated the growth of branches and twigs and so on, so a single tree must take up computing power.
I had some forts that were in heavily forested areas and grind slowly to a half, destpite the population not growing a lot. Since then I've taken to do very heavy-handed forest management, preventively clearing most of the surface from trees - and it seems to work.
No, no, this is pretty verified. The slowest parts of a 6x6 fort I ran for 25 years were:
1. some sort of map activity that I'm like 50% sure was tree/plant growth
2. temperature
So this is, in fact, borne out by the data.
But this can be mitigated massively by just playing on a smaller embark.
Is it the size of the embark or the size of the, for lack of a better term, exposed surface area?
A small embark that's been massively mined out would have a lot of exposed space and items that would need ongoing temperature checks.
-
Personally I think that putting a limitation to how many trees grows and growth ratio (depending on amount of trees in area and fungus / mushrooms etc ), might help FPS a bit over time.
I remember that sometimes discovering areas with fungus and then seeing the increase in growth ratio used to also affect the FPS.
Im playing on a 6x6 map right now with a lot of trees and Can't say it's bad. Been ages since I've had a time for DF but I guess im going to play a bit more from day to day.
-
I'd guess opening the caverns and starting fungal growth in all underground areas may still impact FPS, unless the game is running the same checks on every tile whether or not plant growth is actually possible on the tile.
-
Very surprising that LOS is implemented that way. For dwarf fortress I'd imagine a good improvement is to just put everything in an oct-tree, possibly with an additional optimization to subdivide leaf nodes to only cover the z levels that actually have non solid tile connections to other z levels based on some heuristic (im betting most entities that end up in LOS to each other are on the same z coordinate most of the time). any spatial data structure is going to have more overhead than the current implementation for some number and configuration of entities but since the problem is n^2 fps death at 150+ entities it shouldn't really matter. Also have to deal with removing/inserting/possibly rebalancing any structure you use but with < 300 entities and < 1 node transition per tick per entity the vast majority of the time its probably a completely trivial overhead. Optimizing for only interconnected z levels is probably better on average but worse for entities that ignore or dont have obstructing floors/ceilings like fliers or creatures with EXTRAVISION.
Also interested in how often this is calculated. If theres nothing potentially hostile on the map you might not need to do this very often at all. The naive solution is to just set a flag if any entity on the map is hostile to any other entity on the map and change the global LOS check frequency between 1 / n ticks and 1 / 1 tick but obviously that has a lot of down time as an optimization. I think? a better solution is to update the flag per entity whenever an entity comes onto the map / becomes inanimate / becomes animate / changes loyalty / becomes/stops being agressive etc. and then put each entity into a matching fixed length circular timer list and/or check their LOS immediately, and then provide a time delta to each process when its called again so it can scale factors by the appropriate amount as if they had repeated that process once per tick.
EDIT:
On my latest fort, which currently has 270 citizens, the "can I see these units?" check has been overtaken by a huge margin by checks that I'm pretty sure are actually line-of-sight stuff, so hey, ignore my advice earlier, you totally should try to keep dwarves from clustering up too hard.
To be specific, it's something that checks that both units are historical figures and then checks their relationships to each other--might have to do with family needs? It's kinda hard to tell what's actually happening, but there's a lot of binary searching through the hist figure vector going on.
didnt see this, this definitely doesnt sound like something that has to happen every LOS check
-
My personal non-verified belief is that trees and junk amount to a lot of FPS death.
I'm pretty sure all items are simulated also regarding their tempature and dryness/wetness and so on. So if you have thousands and thousands of items like avocado pits and xxxsockxxx and so on, it's got to use computing power.
I started atom smashing junk straight from the z-screen, where you can really have thousands and thousands of leftover junk items generated for instance by avocados. Some plants generate a waste item, you also get peach pits for instance. And you can easily have 10K of those lying around sucking computing power without even being aware of it.
Another belief I have is that TREES slow down the game. I read somewhere the game simulated the growth of branches and twigs and so on, so a single tree must take up computing power.
I had some forts that were in heavily forested areas and grind slowly to a half, destpite the population not growing a lot. Since then I've taken to do very heavy-handed forest management, preventively clearing most of the surface from trees - and it seems to work.
No, no, this is pretty verified. The slowest parts of a 6x6 fort I ran for 25 years were:
1. some sort of map activity that I'm like 50% sure was tree/plant growth
2. temperature
So this is, in fact, borne out by the data.
But this can be mitigated massively by just playing on a smaller embark.
Is it the size of the embark or the size of the, for lack of a better term, exposed surface area?
A small embark that's been massively mined out would have a lot of exposed space and items that would need ongoing temperature checks.
I checked again using a decompiler and some struct knowledge--#1 was actually map block processing, which included spatters and... temperature. So not a terribly huge surprise. And yes, more exposed surface and more items is going to make it far worse. A desert is also going to have less issues, due to fewer contaminants from leaves etc.
-
A desert is also going to have less issues, due to fewer contaminants from leaves etc.
DFHack's clean command has been known to recover some FPS in my old forts. Feels like we should have some performance options to disable things like snow cover and useless tree droppings for fort mode. That's only a delay to the inevitable FPS death, however.
-
I'd guess opening the caverns and starting fungal growth in all underground areas may still impact FPS, unless the game is running the same checks on every tile whether or not plant growth is actually possible on the tile.
the game does this check in a staggered manner over the course of many ticks. only a fraction of eligible tiles are checked each check, and i believe even the "staggered" checks aren't done on every tick. so the ultimate impact is likely to be relatively low even if you were mine out every level of all the caverns.
-
#1 was actually map block processing, which included spatters and... temperature.
contaminant processing has been known to be a lag source for a while now, and i suspect it actually drags more than temperature, since temperature is just two ints in the map data block, while contaminants are vectors of pointers so there's not going to be any cache coherency
-
Source: I actually profiled the game, which is the only way to actually determine what is slow in a program.
Pathfinding is slow, yes. It's hilariously slow. The thing is, it doesn't happen often at all. When it does, fortresses drop to sub-single-digit FPS levels. This usually happens because you're using tightly closed doors. Don't do that.
Pathfinding happens so rarely that my profiling has shown it contributes to about 6% of an individual tick's processing time. This is compared to the largest cause, one whose contribution to total CPU usage actually grows faster than pathfinding and one that is still the slowest thing in early game: units checking other units for line-of-sight/proximity checks (running away from hostiles etc), which is more like 20%. The truth is that FPS death is not a matter of multithreading pathfinding or anything like that, it's a combination of just about everything in there.
Not to say there isn't some major high-level optimizations to be made. A lot of the CPU time in unit checks is wasted in branch misprediction due to the fact that it's checking the units vector and just skipping everything that happens to be inactive/caged/a ghost; if those units' indices (or pointers to them, as the case happens to be, unfortunately) were simply cached in a vector that contains only active/uncaged/non-ghostly units, that would be avoided and the game would probably run quite a bit faster.
In general, just, like. Trying to optimize a program without profiling is just... blind flailing at nothing of consequence. If you want to contribute to figuring out what is causing FPS issues, first you have to figure out how to actually use the tools that let you find out what's causing FPS issues. I don't know if this is a gatekeepy viewpoint, but I've seen people so hyperfocused on pathfinding, which does not cause FPS issues except in extreme edge cases and tightly-closed door mishaps, that they seem to be convinced that fixing the pathfinding will fix the FPS issues.
It won't. Pathfinding is not a major contributor to FPS issues. Sorry, people have just been wrong about this the whole time. You can get an FPS boost from fixing up pathfinding a bit--6% is 6%, reducing that helps!--but FPS death will set in just as it does now, even with magic oracle pathfinding that takes 0 time. It's not a pathfinding issue.
If I seem bothered by this, it's because I pondered the pathfinding a good deal too before I actually bothered to do the bare minimum work in actually figuring out why the game runs slowly and learned that, no, pathfinding has basically nothing to do with it. I literally had to be handed a save that had a pathfinding edge case (24 tightly-closed doors) before I even found the pathfinding function, since it's buried so deep due to its, again, not being a major use of CPU time.
Sorry for my ignorance but when you say "tightly-closed door mishaps" what does that mean?
-
Sorry for my ignorance but when you say "tightly-closed door mishaps" what does that mean?
With a built door, you have the option to close it tightly so that animals cannot go through it but dwarves and other sapient creatures can. However, animals don't treat tightly-closed doors as walls like you might assume, but will instead use the same pathfinding as creatures that can go through them. This results in creatures clustering around tightly-closed doors, unable to get through and spamming the same attempted pathfinding every single frame. This might not be a problem with one or two doors that get the occasional pet stuck on them, but if you have, say, a room full of dozens upon dozens of turkeys all fighting to get through a door, or if every single one of your doors is tightly locked, that can cause problems.
-
ohh ok. I understand. So when someone says tightly closed they are basically saying a locked door. I thought it was some command or feature I was missing lol. Thank you my friend.
-
Not locked. Tightly-closed doors were removed in the steam version, I assume because they were the single largest cause of FPS death by a huge margin, so you won't find the option there. They let creatures who can open doors through but not creatures who cannot, which is most animals.
Also,
Sorry for my ignorance but when you say "tightly-closed door mishaps" what does that mean?
With a built door, you have the option to close it tightly so that animals cannot go through it but dwarves and other sapient creatures can. However, animals don't treat tightly-closed doors as walls like you might assume, but will instead use the same pathfinding as creatures that can go through them. This results in creatures clustering around tightly-closed doors, unable to get through and spamming the same attempted pathfinding every single frame. This might not be a problem with one or two doors that get the occasional pet stuck on them, but if you have, say, a room full of dozens upon dozens of turkeys all fighting to get through a door, or if every single one of your doors is tightly locked, that can cause problems.
Not every frame, more like every 10 frames. Pathfinding is very, very slow, it's just not done often.
-
Not locked. Tightly-closed doors were removed in the steam version, I assume because they were the single largest cause of FPS death by a huge margin, so you won't find the option there. They let creatures who can open doors through but not creatures who cannot, which is most animals.
Also,
Sorry for my ignorance but when you say "tightly-closed door mishaps" what does that mean?
With a built door, you have the option to close it tightly so that animals cannot go through it but dwarves and other sapient creatures can. However, animals don't treat tightly-closed doors as walls like you might assume, but will instead use the same pathfinding as creatures that can go through them. This results in creatures clustering around tightly-closed doors, unable to get through and spamming the same attempted pathfinding every single frame. This might not be a problem with one or two doors that get the occasional pet stuck on them, but if you have, say, a room full of dozens upon dozens of turkeys all fighting to get through a door, or if every single one of your doors is tightly locked, that can cause problems.
Not every frame, more like every 10 frames. Pathfinding is very, very slow, it's just not done often.
ohhh now i understand. Thank you kind sir!
-
Not every frame, more like every 10 frames. Pathfinding is very, very slow, it's just not done often.
My mistake! I am demonstrably not an expert on the matter. Anyhow your profiling has been quite illuminating and I'll be sure to take this thread into account in future fortresses.
-
...
Sorry if this is a bad suggestion I seldom stray this close to bare metal. IDK if it would play nice with the crazy optimisations CPUs do nowadays.
You (and others in this thread) may be interested in 700,000 lines of code, 20 years, and one developer (https://stackoverflow.blog/2021/12/31/700000-lines-of-code-20-years-and-one-developer-how-dwarf-fortress-is-built/) , an interview by the Stack Overflow blog folks with Toady about a year ago in which he talks about some of the internals, the difficulty with getting optimization higher than what it already is, and a little about caching / cache miss issues.
-
Do animals cause as much drain as dwarves from this then?
-
If you've profiled, can you tell how much the world size actually effects FPS? I've always felt that might be more superstition, but don't have the technical know-how to check.
-
I was doing some disassembling (v0.47.05) and noticed the pow function being called on constant doubles (and then rounded down into integers for length and area) at runtime for material physics stuff. Not sure how much this was being done outside of where I observed it (body part constructor,) but hopefully upgrading the compiler optimized that away.
-
I returned to the game after 10+ years of hiatus and had to deal with the fact that my pc from 2018 is as bad at running DF as my pc from 2003 :D
-
I returned to the game after 10+ years of hiatus and had to deal with the fact that my pc from 2018 is as bad at running DF as my pc from 2003 :D
I am so sorry, but lol.
-
I was doing some disassembling (v0.47.05) and noticed the pow function being called on constant doubles (and then rounded down into integers for length and area) at runtime for material physics stuff. Not sure how much this was being done outside of where I observed it (body part constructor,) but hopefully upgrading the compiler optimized that away.
no it's still there; that code is computing a cube root and there is not much the compiler can do to optimize it away. fortunately, that code doesn't appear to be called all that often so it likely has only a minimal impact on performance.
-
no it's still there; that code is computing a cube root and there is not much the compiler can do to optimize it away.
It should be able to optimize trunc(pow(70000.0, 0.333) * 10.0) to 410, provided those functions are constexpr. (All values are being loaded from rdata into xmm, DF 47.05 Windows.)
For materials where the values are runtime (loaded from RAWs,) obviously it can't. I was just thinking that this might be typical in other avoidable places, v141_xp toolchain being what it is.
-
no it's still there; that code is computing a cube root and there is not much the compiler can do to optimize it away.
It should be able to optimize trunc(pow(70000.0, 0.333) * 10.0) to 410, provided those functions are constexpr. (All values are being loaded from rdata into xmm, DF 47.05 Windows.)
For materials where the values are runtime (loaded from RAWs,) obviously it can't. I was just thinking that this might be typical in other avoidable places, v141_xp toolchain being what it is.
all of the values that particular code runs on are from raws or calculated at run time, so of course it can't reduce them at compile time. also DF has _never_ used v141_xp; it was v140_xp for 43.05 through 47.05, and v143 for 50.xx.
-
Er, most of my profiling is from the upcoming release, I have it in advance for testing reasons. I only got the go-ahead to say that this morning and I apologize if anything I said here made it seem like I'm doing all my profiling in 0.47.05; for stuff like this, I try to keep it vague enough that I don't even need plausible deniability, since I hate denying. Anyway, yeah, I've been pointing out anything particularly odd that I come across, since the point of testing is to make sure release goes smoothly and all. This is why I've been profiling so aggressively lately and part of why I seem so confident in some of my assertions, a lot of my reverse engineering has been done with a back-and-forth with Tarn trying to suss out the exact thing I'm looking at.
From the 50.04 release notes:
... Firstly, Putnam is a very prominent, long-time member of the Dwarf Fortress community and will be helping Toady with programming. This is a historic moment, as never before have non-Adams eyes seen the Dwarf Fortress code. Welcome, Putnam! We wish you luck and courage. ..
Congratulations on your promotion from Master Profiler to Legendary Profiler :) The days of "Putnam cancels smooth code: job item inaccessible" are now behind us. Are you allowed to say whether you have a specific mandate such as performance improvement, porting, etc, or have you had all programming labors checked just in case?
-
I mean: https://store.steampowered.com/news/app/975370/view/3625992251248624682
(https://store.steampowered.com/news/app/975370/view/3625992251248624682)
Sped up line-of-sight code
Welp, think he's off to a strong start!
-
If you've profiled, can you tell how much the world size actually effects FPS? I've always felt that might be more superstition, but don't have the technical know-how to check.
I would very much like to know the answer to this too :)
-
Interesting thread shame I'm only seeing it after so long.
Yes, but making pathfinding twice as fast will still mean the game goes into the single digits during such events, and making pathfinding twice as fast isn't terribly feasible. Making it multithreaded and letting the game run while long pathfinding operations happen would make the game 100% non-deterministic, with completely different behavior on different CPUs, so that's a no-go.
You could make it multithreaded but sync up at the end of the tick, so everything else that needs to be done in that frame in parallel to the pathfinding and then whichever bit finishes first waits. Could still be some weird thing like the workshop your dwarf is pathing to gets deconstructed in the other thread the moment you're doing the pathfinding, but that can happen when your dwarf is already on his way anyway so not a huge problem I think?
Another idea - these line of sight checks, tree growth checks, item wear checks - are they done every frame? Because if they are it seems like an easy way to eek out some performance by just not doing it as often.
People doing things that are known FPS killers and being surprised when they kill FPS feels like something that should be ignored rather than lumped into that.
I mean, there's a long long list of habits DF players have had to form to not accidentally kill FPS, which new players wouldn't have.. Ignoring those issues seems unfair and kinda silly, and anything that improves FPS or increases the number of ways the game can be played without killing FPS, would be good I think. Imagine being able to design your fortress however you want and not having to cage your animals up for fear of destroying FPS?
I think btw it's not as simple as assigning a particular number to pathfinding cost like 6%, because it depends on how many tasks are being generated and their average distance from your dwarf, and the layout of your fortress. The fact that it is really slow means even a small increase in the distance, complexity of your fort layout, or number of tasks will tank fps considerably. Personally I still think pathfinding could still be improved a lot by using cached paths between 'intersections' and only actually calculating the last leg on the fly.
The other things where you're updating a huge list of items, say for wear checks, plant growth, temperature updates and so on seem like straightforward cases where threading is going to make a big improvement easy.
-
You could make it multithreaded but sync up at the end of the tick, so everything else that needs to be done in that frame in parallel to the pathfinding and then whichever bit finishes first waits. Could still be some weird thing like the workshop your dwarf is pathing to gets deconstructed in the other thread the moment you're doing the pathfinding, but that can happen when your dwarf is already on his way anyway so not a huge problem I think?
Another idea - these line of sight checks, tree growth checks, item wear checks - are they done every frame? Because if they are it seems like an easy way to eek out some performance by just not doing it as often.
Tried. Game crashes due to the fact that two things tried to pathfind at the same time, which, yes, caused a crash. The problem is that most things that need to do pathfinding need to wait for the pathfinding, and if I'm using a mutex to control the pathfinder then you've suddenly got 8 threads all waiting on the pathfinder and... nothing changed at all.
-
I can only assume that the pathfinder is called in different sections of the mainloop and in subcalls.
If it was as simple as
/* Main loop */
for unit in Units:
target = unit.decideTarget()
unit.findPathTo(target)
/* Continue main loop */every time pathfinding was needed, then the theoretical speedup of a multithreaded for-loop would be O(N) since each thread would work on their own units only and not alter the world state save for their assigned units' paths.
If instead the pathfinder calls are sprinkled throughout the codebase, which given Toady's background is not unreasonable, then yeah, it would require a hellish rewrite of the code to get any worthwhile speedup. At the very least, the code will need to be restructured into a neat pipeline of stages.
-
I can only assume that the pathfinder is called in different sections of the mainloop and in subcalls.
If it was as simple as
/* Main loop */
for unit in Units:
target = unit.decideTarget()
unit.findPathTo(target)
/* Continue main loop */every time pathfinding was needed, then the theoretical speedup of a multithreaded for-loop would be O(N) since each thread would work on their own units only and not alter the world state save for their assigned units' paths.
If instead the pathfinder calls are sprinkled throughout the codebase, which given Toady's background is not unreasonable, then yeah, it would require a hellish rewrite of the code to get any worthwhile speedup. At the very least, the code will need to be restructured into a neat pipeline of stages.
There is a single instance of the pathfinder that uses a single, shared global structure to store the data required to implement the pathfinding algorithm. The code is not reentrant and cannot be called by two threads at the same time because they'd clobber each other's work on that shared singleton global structure. You'd just have to synchronize on entry to ensure that only one thread is using the pathfinder at a time, which defeats the whole point of multithreading.
This is the way it is with almost all the code in Dwarf Fortress. There are a tiny handful of places where small gains might be obtained by multithreading, but in actuality the overhead associated with synchronizing accesses that would need to be synchronized will completely obliterate any gains and might actually make the game slower. And the complexity of doing proper synchronization of multithreaded code means that the probability of bugs that cause either stochastic behavior or deadlocks goes way up.
There are lots of other ways to speed the code up that don't have these complexities (and I've had several fruitful discussions with Putnam about these ideas already) and it would make far more sense for Bay12 to pursue those rather than waste literally months of programmer time making the game capable of being multithreaded.
-
Tried. Game crashes due to the fact that two things tried to pathfind at the same time, which, yes, caused a crash. The problem is that most things that need to do pathfinding need to wait for the pathfinding, and if I'm using a mutex to control the pathfinder then you've suddenly got 8 threads all waiting on the pathfinder and... nothing changed at all.
I could have told you that, and I've never seen the source. The pathfinder stores the boundary data for A* in a statically allocated array, so two instances running at the same time will clobber each other's work. The pathfinder is not reentrant.
-
-snip-
There is a single instance of the pathfinder that uses a single, shared global structure to store the data required to implement the pathfinding algorithm. The code is not reentrant and cannot be called by two threads at the same time because they'd clobber each other's work on that shared singleton global structure. You'd just have to synchronize on entry to ensure that only one thread is using the pathfinder at a time, which defeats the whole point of multithreading.
This is the way it is with almost all the code in Dwarf Fortress. There are a tiny handful of places where small gains might be obtained by multithreading, but in actuality the overhead associated with synchronizing accesses that would need to be synchronized will completely obliterate any gains and might actually make the game slower. And the complexity of doing proper synchronization of multithreaded code means that the probability of bugs that cause either stochastic behavior or deadlocks goes way up.
I see. Then first you'd have to separate the "work" memory from the world state so each thread can allocate their own "work" memory. You'd still need to pipeline the code to get any practical speedup while ensuring the world state doesn't get changed by other calls (game objects moved or destroyed etc., perhaps avoidable with assumed target coordinations and fail-safes in case the target isn't there in the end). Even if you could avoid pipelining the code, you might end up with performance hits if these other world-state-changing calls have to wait for the pathfinder threads to finish.
There are lots of other ways to speed the code up that don't have these complexities (and I've had several fruitful discussions with Putnam about these ideas already) and it would make far more sense for Bay12 to pursue those rather than waste literally months of programmer time making the game capable of being multithreaded.
Agreed.
-
There is a single instance of the pathfinder that uses a single, shared global structure to store the data required to implement the pathfinding algorithm. The code is not reentrant and cannot be called by two threads at the same time because they'd clobber each other's work on that shared singleton global structure. You'd just have to synchronize on entry to ensure that only one thread is using the pathfinder at a time, which defeats the whole point of multithreading.
Two things, one I don't see why finding a path necessitates modifying globally shared state at all let alone concurrently, and two having a bunch of different threads doing pathfinding at the same time isn't what I suggested anyway; if pathfinding is a relatively rare but slow task, just have one thread for pathfinding while the main thread does the rest of the tick. Since pathfinding apparently doesn't happen very often, I'm assuming it probably isn't the case that normally you need two paths calculated in the same tick anyway. Maybe pathfinding takes so much longer than the rest of the tick that you don't see much difference, maybe it does, impossible to say without knowing how long pathfinding calls actually take.
I also don't agree that a little bit of time spent refactoring code to enable some limited applications of multithreading would be wasted time, as it would probably mean the code becomes neater and runs faster + will give ideas on other areas that can be so modified. We know that basically every fort a player plays that doesn't immediately die will succumb to FPS death, we know virtually every modern CPU can do about 8x more work than the game can currently utilize. Why not try and unlock that at all?
Not to say that other optimizations would be unwelcome whatsoever.
Congrats to Putnam on your new gig too btw
-
@Putnam, does this apply only to doors, and specifically for selectively locked, or for those locked to all as well? Does a locked hatch cause the same problem Presumably a constructed wall does not? Pathfinding simply ignores the path that existed before construction? Drawbridges? Retracting? And it applies only to pets?
-
The "tightly closed" door thing, besides being removed from the current version anyway, was strictly because pathfinding just... didn't handle that specific scenario correctly at all. As far as I could tell it would actually ignore the fact that the door was tightly closed until after the path was already... well, pathed, and then re-path after a check that identified the door as being in the way. Meaning that if an animal tried to path through a tightly-closed door, it would force pathfinding to run over and over and over again until a new destination were decided. Hence why it was removed.
I don't recall if you could even tightly close a hatch, but I imagine the same thing would happen there.
-
@Putnam, does this apply only to doors, and specifically for selectively locked, or for those locked to all as well? Does a locked hatch cause the same problem Presumably a constructed wall does not? Pathfinding simply ignores the path that existed before construction? Drawbridges? Retracting? And it applies only to pets?
I know you didn't direct the question at me but I'll try answer anyway:
The game maintains a set of regions which divide the map based on whether the tiles in that region are mutually accessible - a walking creature can reach every other tile in that region from any of them. A tightly closed door was considered passable so it wouldn't ever cut a region in two, which meant animals thought they could still path to things on the other side of this door. This is a problem because when they actually try to path to it, the path takes them through the 'accessible' door only for them to discover when they reach it, it's not passable, so they do the pathing all over again, only for the same thing to happen again and again as it still wants to go to the thing it's going to.
A locked door on the other hand is treated as an impassable tile, same as a raised drawbridge or wall or etc. A dwarf can be interrupted by say, a drawbridge being raised when he was on his way to go cut a tree outside, but because the drawbridge is seen as impassable he won't try and go cut the tree again because it'll be in an inaccessible region of the map (unless there's another path outside of the fort).
-
OK, thanks both of you. Matches what I was thinking, based on how invaders react to locking doors between them and the fortress heart. And lower cavern building destroyers when you close the hatches on the stairs. That didn't seem to cause insane lags. And neither did my poultry houses when I locked them tightly too all so I could hatch some eggs.
So it's just the special case of making a door non-pet passable? Any other of these kinds of conditions I should avoid?
-
We know that basically every fort a player plays that doesn't immediately die will succumb to FPS death, we know virtually every modern CPU can do about 8x more work than the game can currently utilize. Why not try and unlock that at all
1. We don't know that first thing at all, actually. BlindIRL's longdeath ran for something like 1000 years(?) and never suffered "FPS death", just the entropy of the game's hard cap of 3000 units before it stops bringing in migrants. It's not an inevitability as described, especially since the optimization in 50.05 was apparently way stronger than I thought because I didn't test it on a >=200 citizen fortress.
2. 8x the CPU time but not nearly so much gain in performance. Synchronization overhead is pretty dang onerous, actually.
Two things, one I don't see why finding a path necessitates modifying globally shared state at all let alone concurrently, and two having a bunch of different threads doing pathfinding at the same time isn't what I suggested anyway; if pathfinding is a relatively rare but slow task, just have one thread for pathfinding while the main thread does the rest of the tick. Since pathfinding apparently doesn't happen very often, I'm assuming it probably isn't the case that normally you need two paths calculated in the same tick anyway. Maybe pathfinding takes so much longer than the rest of the tick that you don't see much difference, maybe it does, impossible to say without knowing how long pathfinding calls actually take.
1. It doesn't and having separate pathfinders for each thread would be possible, yes.
2. One thread for pathfinding while the main thread does the rest is not possible because whatever the game needs a path for it uses immediately. You can't just foist it off onto another thread, the original ones needs that.
3. Pathfinding does in fact tend to take up a huge chunk of whatever tick it happens in and synchronizing it would remove a lot of the benefit.
I do think it's not unlikely that multithreading a lot of map block operations would be possible, which would have the benefit of making larger embarks much faster (!), but it would take such a major rewrite that it's still much better to go for smaller, "incremental" improvements. 50.05's optimization was commenting out 3 lines.
-
50.05's optimization was commenting out 3 lines.
Wow! So you are saying you could improve on THAT by 33% by simply commenting out one more line? ;)
-
Comment out the pathfinder -> No FPS loss due to pathfinding.
-
We know that basically every fort a player plays that doesn't immediately die will succumb to FPS death [..]
1. We don't know that first thing at all, actually. BlindIRL's longdeath ran for something like 1000 years(?) and never suffered "FPS death", just the entropy of the game's hard cap of 3000 units before it stops bringing in migrants. It's not an inevitability as described, especially since the optimization in 50.05 was apparently way stronger than I thought because I didn't test it on a >=200 citizen fortress.
That's actually pretty neat, but did he have to limit the population really low and avoid the cavern layers etc? I've never had a fort of decent length not have FPS be terribly low eventually, and apparently others are concerned with this too as the most popular (by far) item in the DF suggestions poll thread is performance related, as is #5.
2. 8x the CPU time but not nearly so much gain in performance. Synchronization overhead is pretty dang onerous, actually.
That's true certainly, you can never perfectly parallelize everything so you won't get 100% utilization of all cores all the time, but even getting 2x instead of 8x would be a huge boost. Soon the average desktop CPU will have 16 cores, eventually maybe 32. There's definitely something useful those cores could be doing in parallel I'm sure of it.
1. It doesn't and having separate pathfinders for each thread would be possible, yes.
2. One thread for pathfinding while the main thread does the rest is not possible because whatever the game needs a path for it uses immediately. You can't just foist it off onto another thread, the original ones needs that.
3. Pathfinding does in fact tend to take up a huge chunk of whatever tick it happens in and synchronizing it would remove a lot of the benefit.
I do think it's not unlikely that multithreading a lot of map block operations would be possible, which would have the benefit of making larger embarks much faster (!), but it would take such a major rewrite that it's still much better to go for smaller, "incremental" improvements. 50.05's optimization was commenting out 3 lines.
Two pathfinders on the odd occasion where you do have to do it twice in the same tick would be great seeing how long it can take so that's good I guess.
To your point two, how much does the game actually need the paths right then though? Seems like there's a lot that could be done in a tick that doesn't depend on knowing whether Urist wants to walk up down left or right.
And to point three, how much of a tick do pathfinding calls usually take exactly? If it's 50% that's actually basically ideal for punting it into its own thread, could cut the tick time in half. If it's more like 90% then probably you're better off looking for some other optimization like precalculating paths (incidentally precalculating paths is something that would be perfect for its own thread, since by definition the paths aren't needed right now).
Other expensive things like temperature and weather, item checks and whatnot could be other promising candidates.
In any case I'm extremely happy to hear optimizations are being made.
-
Moving pathfinding to another thread would not make the tick faster because the main thread would have to wait until the pathfinder is done to continue doing what it was doing before, is what I was saying there.
-
I get what you're saying but I'm asking why, basically, does the rest of the tick depend on knowing where Urist is going? The only thing that seems to obviously depend on a creature having a path is updating its position, which could be deferred until the end of the tick. If it's really really hard to update his state in a consistent way because of the deferment the creature could spend 1 tick not moving to the destination (considering the best path) and just start moving on the next frame.
The why is somewhat rhetorical as I know you probably can't go into specifics too deeply.
-
It's not quite that simple, @ayy1337, because to update a dwarf's position, you need to know at least roughly what direction he needs to head. And ideally, have the entire path already mapped out at least to the next choke point, because there's a huge difference between taking a straight path down a 100 long, 3 wide corridor and heading more or less that direction, zigzagging as you go. Worst case going more or less the right direction might turn the 100 long trek into 141.
Seems to me the simplest solution is to just let dwarves pass through one another on a path 1 wide that has already been charted for typical moves between points A and B. It would only need to be updated if doors get locked or bridges flip up or a forgotten beast is traipsing through, specifically NOT every time some dwarf is assigned a task that takes him down the same corridor. But self-evidently, that was not the vision for the game or that's how it would have been coded.
-
Seems to me the simplest solution is to just let dwarves pass through one another on a path 1 wide that has already been charted for typical moves between points A and B.
they already do this
It would only need to be updated if doors get locked or bridges flip up or a forgotten beast is traipsing through, specifically NOT every time some dwarf is assigned a task that takes him down the same corridor.
caching such things is a bit of a computational nightmare in and of itself. A default embark is 36864 tiles per Z. Storing the weights between two tiles for just one Z level is thus 679,495,680 stored paths.
Caching common paths is slightly less nightmarish.
The game does in fact have accessibility stuff that it recalculates all the time. Calculating that is what causes water to kill your FPS. It would take much longer if it were O(n^2) instead.
But self-evidently, that was not the vision for the game or that's how it would have been coded.
sometimes things really are harder than you think, actually
-
Seems to me the simplest solution is to just let dwarves pass through one another on a path 1 wide that has already been charted for typical moves between points A and B.
they already do this
Really? I've always run into issues with dwarves colliding with each other. Or I'm pretty sure that's what I saw. I never single-stepped through to watch, but I thought for sure going to 2 and 3 wide corridors and stairs fixed a lot of problems. Is that unnecessary, too? I'm seeing a lot of things that seem different since I last played.
It would only need to be updated if doors get locked or bridges flip up or a forgotten beast is traipsing through, specifically NOT every time some dwarf is assigned a task that takes him down the same corridor.
caching such things is a bit of a computational nightmare in and of itself. A default embark is 36864 tiles per Z. Storing the weights between two tiles for just one Z level is thus 679,495,680 stored paths.
Caching common paths is slightly less nightmarish.
The game does in fact have accessibility stuff that it recalculates all the time. Calculating that is what causes water to kill your FPS. It would take much longer if it were O(n^2) instead.
Gotcha. More or less what I meant. Once he has a path to go install the bed, that path remains the quickest path from beginning to end unless a door gets locked between here and there, or a bridge toggles, or an intervening wall constructed, or a new shortcut dug, or a handful of other circumstances.
Caching is another matter because the game would have to constantly update its list of optimal paths as new corridors are dug, or doors locked, etc. In my forts, it would not take very long before the cached path was obsolete.
-
Once he has a path to go install the bed, that path remains the quickest path from beginning to end unless a door gets locked between here and there, or a bridge toggles, or an intervening wall constructed, or a new shortcut dug, or a handful of other circumstances.
This is also how the game already works. They cache their entire path as soon as they make it and they just follow it until it's done unless they're explicitly stopped along the way.
People have a tendency to severely underestimate how optimized the pathing is in this game. It is unironically about as optimal as it can get right now. It's just that pathfinding on a graph this big is inherently slow and there is nothing that can be done about it besides reducing the amount of pathing actually being done, which is already done a lot in the game.
-
Speaking of path caching I actually had an idea about this that I think could reduce the cost of pathing through very spread out forts a ton. Basically treat staircases as nodes and index them by region and z-level. Cache pre-calculated paths between staircases on the same z-level and region, and from each of them to nearby destinations on the same z-level, so you have a weighted graph connecting the fort.
Then all a dwarf has to do to navigate a huge labyrinthine fort is find the nearest staircase and then search the graph for his destination.
Alternatively, if you don't want to precalculate the paths you could actually just record the paths when a dwarf makes a journey that connects two staircases or between a staircase and his destination. I think this option has some nice properties like not needing to do any extra work because the dwarf was already going to generate that path, and the most commonly used paths are the ones it's going to generate.
I know you're probably sick of hearing about pathfinding by now Putnam but if you had any thoughts on this I'd appreciate them :)
-
I have an idea:
Graph database (such as NebulaGraph) with quadtree space partitioning. Basically, on generating the map you partition the tiles according to passable or not, then store the partitions in a graph database. Then it's a matter of:
Urist wants tile X to tile Y.
Tile X is in Partition A.
Tile Y is in Partition Z.
Query Partition A's shortest path to Partition Z (graph databases are really good at this, and you can store info in the links between partitions such as "can walk here: yes", "can fly here: no"). So we can have dragons flying over walls. The actual path between tiles in a partition is just a straight beeline, because we know partitions are always made up entirely of passable tiles.
Cache query so Nith and Rith can follow Urist with no overhead.
The only time you have to recalculate is when a tile changes accessibility (drawbridge raising, magma flowing, Urist doing some mining etc), and then all you do is tell the tile's parent partition to do a repartitioning (possibly merging partition A B C and D into partition A if the last unpassable tile was cleared).
EDIT: I see other dogs are on the same bone here, and apparently pathfinding is as good as it gets already.
-
EDIT: I see other dogs are on the same bone here, and apparently pathfinding is as good as it gets already.
Pathfinding definitely isn't as good as it gets already haha, but I think the partition graph is definitely another possible solution. I think rimworld uses that. They don't have to go across z-levels but they do have a pretty large map.
-
This is also how the game already works. They cache their entire path as soon as they make it and they just follow it until it's done unless they're explicitly stopped along the way.
That's what I just said. It wasn't a suggestion. I figured that was how it was coded based on watching their movement.
But I am intrigued. Did I understand you correctly that there is no advantage in terms of pathing to having corridors wider than 1 tile? Is that new, or did I really flub the testing in (I think) .34?
@ayy1337, I've run forts where that would not work well at all. Maybe a couple short stairs in the whole fort, everything else ramps. I assume you can still gain a lot of efficiency with ramps over using stairs and hallways, though I have not bothered to confirm since .42 or so. But obviously I'd go back to stairs if the advantage to ramps disappeared.
-
I thought about implementing a sort of hierarchal pathfinding thing where each map block has 6 bits (one for each orthogonally adjacent map block), pathfinding starts by pathfinding backwards to the origin map block, storing the distance in map blocks for each block as it does, then adding the map block distance to the heuristic (multiplied by some generic constant, probably 4096 for same-Z distance and 256 for cross-Z distance, to keep it admissible hopefully), which would make things quite a lot faster... but still pretty slow, ha. Wouldn't make much of a difference, I think.
This is also how the game already works. They cache their entire path as soon as they make it and they just follow it until it's done unless they're explicitly stopped along the way.
That's what I just said. It wasn't a suggestion. I figured that was how it was coded based on watching their movement.
But I am intrigued. Did I understand you correctly that there is no advantage in terms of pathing to having corridors wider than 1 tile? Is that new, or did I really flub the testing in (I think) .34?
@ayy1337, I've run forts where that would not work well at all. Maybe a couple short stairs in the whole fort, everything else ramps. I assume you can still gain a lot of efficiency with ramps over using stairs and hallways, though I have not bothered to confirm since .42 or so. But obviously I'd go back to stairs if the advantage to ramps disappeared.
They started swapping instead of dropping to the ground in v50
-
I've definitely seen dwarves stop, step aside, and wait their turn before entering a narrow corridor in the current version.
-
I've definitely seen dwarves stop, step aside, and wait their turn before entering a narrow corridor in the current version.
So, dwarves have finally learned to behave in a civilized manner and not crawl over each other? :)
-
Wait, what? When you want to get past someone in a narrow passage you are actually not supposed to assume a crawling position and either crawl between their legs or leapfrog over them?
Ooohhhh that explains why people always look at me funny in trains and buses.
-
So does setting up traffic priority help with pathfinding?
-
In general, traffic priority doesn't help with FPS. When used for its intended purpose, it forces dwarves to take longer paths. Finding those paths would therefore require more pathfinding work.
It does, however, help with traffic management as well as keeping dwarves safe from dangers like thawing water, battlements, and drawbridges in certain airlock designs.
-
I believe to increase pathfinding one should wall off as much unused space as possible.
-
In general, traffic priority doesn't help with FPS. When used for its intended purpose, it forces dwarves to take longer paths. Finding those paths would therefore require more pathfinding work.
it actually has very little impact on the amount of work done by the pathfinder
-
I have a bold question. Would a full or partial rewrite of the code give a HUGE increase in performance? Is this one of the things you are determining by profiling the game?
-
I'm glad Putnam is now part of the team, because even though the Adams brothers are certainly talented and all, the game REALLY need some sanity check and clean up.
Some things I noticed with the steam release :
-coastal waves murder FPS when they land on ground. About 10-15fps loss while they do that.
-it seems the game keep track of the workshop every masterwork, possibly every item even, is from. I saw that because I lost some random masterwork and when I clicked on "show me", it showed me a clothier workshop (and a kitchen another time). Instead of the expected place of destruction. Which mean the game kept track of where the item was produced. Which is entirely pointless. And while it may not affect FPS, it will bloat saves for no valid reasons. Is it really important if my silk shirt is from this clothier workshop or that one ?
-10 years old fort. 1200 (!!) visible body parts according to the stocks. Countless corpses, bolts, arrows, weapons... lying in the caverns. I disabled underground civ due to possible save corruption (lost my first steam save that way), and also because they seem buggy and spawn indefinitely (IE kill a wave, another spawn immediately). At some point a FB was literally spawn camping a narrow path that was at the edge of the map, where creatures spawned. We really need a "decompose" thing for item lying around for too long outside stockpiles. Perhaps only affecting locked item or something. That's bloating saves for no reasons, and possibly affecting FPS.
-I have a rough gem burning somewhere. Been burning for 2years now. Not the first time I had gem burn for a ridiculous amount of time. Really need a sanity check to clean up item when they burn for too long.
-
-10 years old fort. 1200 (!!) visible body parts according to the stocks. Countless corpses, bolts, arrows, weapons...
Ha. How about almost 14000 spider webs in caverns precisely accounted by record keeper.
-
I have a bold question. Would a full or partial rewrite of the code give a HUGE increase in performance? Is this one of the things you are determining by profiling the game?
this is basically always true, especially of old-enough code
-it seems the game keep track of the workshop every masterwork, possibly every item even, is from. I saw that because I lost some random masterwork and when I clicked on "show me", it showed me a clothier workshop (and a kitchen another time). Instead of the expected place of destruction. Which mean the game kept track of where the item was produced. Which is entirely pointless. And while it may not affect FPS, it will bloat saves for no valid reasons. Is it really important if my silk shirt is from this clothier workshop or that one ?
the masterwork may have actually been lost in the workshop, and the game keeps track of where announcements happen, which are eventually cleaned out. Besides that, you can see for yourself what all is stored in items (https://github.com/DFHack/df-structures/blob/master/df.items.xml). Workshops aren't one, nor are they part of the historical event created whenever a masterwork is made. (https://github.com/DFHack/df-structures/blob/18446d51e4133a06271fd2672f5b816b8c56e937/df.history.xml#L2184) You're not looking at what you think you're looking at, in other words.
Besides that, "save bloat" is pretty dramatic, since if it were storing the building for every masterwork then your save would increase by a megabyte after making 250,000 of them.
-10 years old fort. 1200 (!!) visible body parts according to the stocks. Countless corpses, bolts, arrows, weapons... lying in the caverns. I disabled underground civ due to possible save corruption (lost my first steam save that way), and also because they seem buggy and spawn indefinitely (IE kill a wave, another spawn immediately). At some point a FB was literally spawn camping a narrow path that was at the edge of the map, where creatures spawned. We really need a "decompose" thing for item lying around for too long outside stockpiles. Perhaps only affecting locked item or something. That's bloating saves for no reasons, and possibly affecting FPS.
They're not spawning, they're jumping out of ambush. They were sneaking around before, and thus invisible to the player. This has been a feature in the game for 15 years, not sure why people are only noticing it now. Elves have been doing this since release AFAIK.
Items don't have a major effect on FPS, especially if they're just lying around in the caverns. I wouldn't worry about them too much.
-
I have a bold question. Would a full or partial rewrite of the code give a HUGE increase in performance? Is this one of the things you are determining by profiling the game?
this is basically always true, especially of old-enough code
Is this a serious option that is being considered?
-
No, because it would take forever, there are lower-hanging fruits, and the game does not run slow enough to do that.
Like... I am not terribly convinced that anyone who thinks this game runs unacceptably slow has ever played another game which is even mildly similar to this one in their life. Try playing Civilization IV sometimes, which is doing less simulation per tick and still takes multiple seconds. Or, hell, The Sims 3.
-
the masterwork may have actually been lost in the workshop, and the game keeps track of where announcements happen, which are eventually cleaned out. Besides that, you can see for yourself what all is stored in items (https://github.com/DFHack/df-structures/blob/master/df.items.xml). Workshops aren't one, nor are they part of the historical event created whenever a masterwork is made. (https://github.com/DFHack/df-structures/blob/18446d51e4133a06271fd2672f5b816b8c56e937/df.history.xml#L2184) You're not looking at what you think you're looking at, in other words.
Besides that, "save bloat" is pretty dramatic, since if it were storing the building for every masterwork then your save would increase by a megabyte after making 250,000 of them.
I may have been wrong. I did a test and it was showing me the place of destruction this time around. I rest my case^^
They're not spawning, they're jumping out of ambush. They were sneaking around before, and thus invisible to the player. This has been a feature in the game for 15 years, not sure why people are only noticing it now. Elves have been doing this since release AFAIK.
Items don't have a major effect on FPS, especially if they're just lying around in the caverns. I wouldn't worry about them too much.
I noticed the behaviour when I was standing close to the edge of the map. Really close. My fort was sitting on a corner already, and I went even closer to the corner for the gems "boxes". I killed a wave, then another, then another, then another.... It was not stopping. Yes, they were "sneaking" (invisible) until a dwarf could see them, but one of the warrior went literally at the edge of the map and I saw them spawn there.
I reloaded because the soldier would not back down (as they do), and was just staring there until a wave spawned, he killed them, then stood there, then another spawned....
I thought it was similar to the "agitated" creatures. As soon as you one "group" is gone (killed or leave the map) another spawn nearly immediately. Until it's some birds that get stuck up in the air and prevent more spawn because they don't come and die right away.
I didn't think those items had any major impact on FPS. But it does freeze the "stock" menu whenI open it on old-ish fortress. I assume that's because of the amount of stuff in said stock.
I still think we need some sanity cleanup. I don't need 1200items (and rising) lying around probably forever. I don't need a giant list of dead/missing that keep on growing. I can check legends for the important killing and all.
-
Like... I am not terribly convinced that anyone who thinks this game runs unacceptably slow has ever played another game which is even mildly similar to this one in their life. Try playing Civilization IV sometimes, which is doing less simulation per tick and still takes multiple seconds. Or, hell, The Sims 3.
In my case, it's because of the depth of the game of DF. You get past the first winter in Banished, and why bother continuing? The interesting parts of the game are all in the past.
With DF, it seems there's always something you can try to make this a better fort. The interesting parts are in the future.
I have no qualms saying, "That's good enough" and restarting Surviving Mars or The Planet Crafter to get back into the part of the game I enjoy. DF is different.
[EDIT]
And it really doesn't help that the things the dwarves love, like mist, are FPS hogs.
[/EDIT]
-
I don't need a giant list of dead/missing that keep on growing
I actually have the code for that implemented, with an in-game setting allowing you to adjust how many units are there before they start being culled, so that's good
-
And it really doesn't help that the things the dwarves love, like mist, are FPS hogs.
Yeah I'd be really curious to know specifically about plans to improve FPS around fluid contraptions or the mandatory 50 FPS drop that happens when you open the magma sea.
At this point I can easily run the game for decades at max pop and get no noticable slowdown, but those two things will always brutalize my framerate.
-
Never noticed the magma sea, but that may be because I beeline magma workshops and turn down the game speed once I hit magma to get everything set up. Cracking open the caverns, yeah, I notice that because I don't slow the game for that, just install a hatch and move the stairwell to wherever I can get around the caverns.
Probably same deal, right? Until you crack the magma, it doesn't spawn fire snakes and so forth? Guess that makes sense. Probably I'm blaming too much of the slowdown on cavern spores filling every open dirt instead of whatever is happening in the sea.
-
The thing with the magma sea though is that the slowdown is always immediate - it's always like a sudden pop as soon as I breach it. I have frequently had the experience of being pinned at 100 FPS for an entire fort history and then dropping down below 50 as soon as that channel gets dug.
Caverns may or may not be the real culprit in any of my slowdowns - I sometimes seem to notice a bit of a hit around that time in the game, but it is never so drastic and it's not immediate, so it could be something else happening. The game is doing a hell of a lot every tick and I am deeply skeptical of any anecdotal observations about framerate, even my own - but the relationship with large water features and the magma sea is just too immediate for me to ignore.
-
No, because it would take forever, there are lower-hanging fruits, and the game does not run slow enough to do that.
Like... I am not terribly convinced that anyone who thinks this game runs unacceptably slow has ever played another game which is even mildly similar to this one in their life. Try playing Civilization IV sometimes, which is doing less simulation per tick and still takes multiple seconds. Or, hell, The Sims 3.
indeed, as harsh as I can often be with regard to the parts of this game that are not optimally coded, in reality most of the code is good. it's just that, well, it can always be better. and i've long been impressed by how robust dwarf fortress is.
-
In a 1-wide corridor, dwarfs only will pass each other when there is no alternate route. If there is an alternate path, they will use it.
Here is a DFFD 50.05 example (https://dffd.bay12games.com/file.php?id=16348) with two rooms connected by two 1-wide corridors, and three stockpiles linked in a loop. It should load up with two dwarfs heading towards each other in one corridor. When they meet, one reverses direction to use the other corridor, and there meets another dwarf but because there is no alternate route, one dwarf goes prone so they can pass.
-
Here is a DFFD 50.05 example (https://dffd.bay12games.com/file.php?id=16348) with two rooms connected by two 1-wide corridors, and three stockpiles linked in a loop. It should load up with two dwarfs heading towards each other in one corridor. When they meet, one reverses direction to use the other corridor, and there meets another dwarf but because there is no alternate route, one dwarf goes prone so they can pass.
Maybe it's fatigue, but I cannot seem to find a stance indicator (if the dwarf is prone or not) in the new interface. I have downloaded your example, and got two dwarves in the same tile, but don't know which one is prone?
-
Run it at a lower FPS, you'll see the dwarf's icon change when they go prone.
The prime reason for that example is to show the problem with using 1-wide corridors when alternate routes exist.
-
In a 1-wide corridor, dwarfs only will pass each other when there is no alternate route. If there is an alternate path, they will use it.
That's what I thought was happening. Maybe I misunderstood this exchange?
Seems to me the simplest solution is to just let dwarves pass through one another on a path 1 wide that has already been charted for typical moves between points A and B.
they already do this
[EDIT]
Oh, I bet he thought I meant the behavior we all know about, lying down and letting the other guy go around him. I thought the easiest way to code it would be to path through the other dwarf as if he were not there. Then only objects the pathing would have to plan around are static objects like statues. Currently dwarves have not just the static objects to path around, but also the moving dwarves, which is inherently more time consuming.
[/EDIT]
-
Run it at a lower FPS, you'll see the dwarf's icon change when they go prone.
The prime reason for that example is to show the problem with using 1-wide corridors when alternate routes exist.
I honestly see no difference in their sprites if they are on the same tile.
Anyway, most of the time, if they are going in the opposite direction, they swap in one tick, without the intermediate step of being in the same tile. When they go the same direction, then for some ticks they are on the same tile (but I cannot tell if one of them is prone or not), when one of the dwarves is faster.
And when they would bump into one another going opposite direction, and there is alternate route, then one changes route to alternate - which is as it was in previous versions.
Isn't it as it is supposed to be?
-
Yep, it is the same as before, and it appears to be as it was intended to be. I also don't think it should be changed. But it can a nasty surprise when a mob of dwarfs find an alternate route through 300 tiles of the caverns because they were all using a 1-wide tunnel to haul stuff 30 tiles then you opened a second entrance into the caverns elsewhere while mining. Or, you have two staircases going into the depths but one goes through a heavy aquifer project that you lost control of and also created an alternate path through the pouring water (when you find a pile of dead dwarfs and wheelbarrows at the bottom of the stairs, you question why they chose that much longer and more dangerous route).
My reason for uploading the DFFD example is because pathing in 1-wide hallways was mentioned a bunch of posts earlier, but the "unless there is an alternate route" condition wasn't mentioned. I remember those forts every time I'm choosing how wide to dig a hallway.
-
Yeah, thanks. Agreed on that it's working as intended and as it should.
I used to run into that long alternate path stuff in my early days of trying to figure out forts that weren't just branching out from a central stair.
-
I read through most of this thread, and paid attention but didn't understand many of the parts when y'all got a bit more technical...
To put what I think I understand in layman's terms:
Every time a check is made to see what Dwarf Child A can see, it checks against every creature that has ever existed in the fortress, as opposed to only those that are still alive, present, and reasonable to consider.
Which means if you had 200 ducks, they'd slow down line of sight checks because the game is both checking to see if each of those ducks can see anything and everything else has to check to see if they can see each of those ducks.
Then, when you slaughter them it will help a bit (we no longer have to check if the 200 ducks can see anything) but would still leave a permanent dent because 50 years later Dwarf A (now an adult) will still be considering whether it can see each one of those 200 long-dead ducks whenever it checks to who it can see.
It sounded like there were several different options on how to fix this - from pruning the list of inactive creatures, to creating a new list specifically for these kinds of checks that only contains the active creatures from the original complete list - but right now, it sounds like having fewer creatures *ever* within your fortress is the best way to block FPS slowdown, rather than worrying as much about how many are there at any given time?
TBH it's not something I'm overly concerned about as I can't recall having any FPS-death forts aside from ones that were already dying from flooding :D
My forts usually 'die' because I embarked in a rather suicidal manner, screwed up something significant, or wanted to try something different before I even got that far.
But I am always curious about the reasoning behind these issues whenever I happen to be made aware of them :)
-
Every time a check is made to see what Dwarf Child A can see, it checks against every creature that has ever existed in the fortress, as opposed to only those that are still alive, present, and reasonable to consider.
No, it was actually explicitly skipping dead/caged/ghost units that was causing most of the slowdown. They're not being checked at all for most purposes.
It sounded like there were several different options on how to fix this - from pruning the list of inactive creatures, to creating a new list specifically for these kinds of checks that only contains the active creatures from the original complete list - but right now, it sounds like having fewer creatures *ever* within your fortress is the best way to block FPS slowdown, rather than worrying as much about how many are there at any given time?
Pruning the list of dead creatures is maybe in the pipeline, creating a new list that contains only the active creatures has actually already been done the whole time, which is why just removing the redundant check from the list was such a large performance improvement
-
Every time a check is made to see what Dwarf Child A can see, it checks against every creature that has ever existed in the fortress, as opposed to only those that are still alive, present, and reasonable to consider.
No, it was actually explicitly skipping dead/caged/ghost units that was causing most of the slowdown. They're not being checked at all for most purposes.
Ah, so rather than Dwarf A actually checking to see if he could see the long-dead ducks, it was Dwarf A deciding: "I don't have to check if I can see duck 1...200"?
It sounded like there were several different options on how to fix this - from pruning the list of inactive creatures, to creating a new list specifically for these kinds of checks that only contains the active creatures from the original complete list - but right now, it sounds like having fewer creatures *ever* within your fortress is the best way to block FPS slowdown, rather than worrying as much about how many are there at any given time?
Pruning the list of dead creatures is maybe in the pipeline, creating a new list that contains only the active creatures has actually already been done the whole time, which is why just removing the redundant check from the list was such a large performance improvement
Ah, so you already did the thing. Didn't catch that while reading through the thread. After looking back, I suppose that's the "Other fixes/tweaks: Sped up line-of-sight code" that I kind of missed in the changelog :)
Thanks for taking the time to answer!
-
In layman's terms there is an endless war for performance vs features. While programmers find creative ways to handle various scenarios and optimize their code and our hardware improve, in the end there the only way to stifle the end game lag in such games is by placing limits on what can be done.
How programmers do their magic is rather technical, one should have at least some background before assuming they know better than the person who actually sees the code. Otherwise, as player, while I find this curious at time, I usually care about what I can do improve my gameplay and sometime vent my frustration in silly ways :P
-
At some point you have to bound some aspects of what the simulation handles per tick, but that's not quite the same thing as saying that you have to bound what is possible.
There is a lot of trickery that you can get away with in terms of deferring processing or decreasing precision, as well as just "vanilla" optimizations to reduce the amount of work that gets done.
So as a professional I strongly disagree with the idea that the ONLY way to prevent lag is to limit the player - there's a big toolbox to draw from there. Also the idea.that FPS death is an inevitability with the game as it currently stands is totally ridiculous and abjectly false.
However, I completely agree that armchair software development is at best a futile effort - it's pretty arrogant to assume that you know THE solution to a problem without ever seeing the project source. I don't think there's anything wrong with theorizing possible causes of slowdown per se, but things like "oh well you really just need to use multithreading" is obtuse and condescending on a good day.
-
However, I completely agree that armchair software development is at best a futile effort - it's pretty arrogant to assume that you know THE solution to a problem without ever seeing the project source. I don't think there's anything wrong with theorizing possible causes of slowdown per se, but things like "oh well you really just need to use multithreading" is obtuse and condescending on a good day.
Is throwing more cores at a highly CPU bound problem really being obtuse or just a logical conclusion? Optimizations are always good but at a certain point your choices really are 'do less' or 'more compute'
-
Is throwing more cores at a highly CPU bound problem really being obtuse or just a logical conclusion? Optimizations are always good but at a certain point your choices really are 'do less' or 'more compute'
You're assuming it's CPU bound rather than memory bound.
-
Is throwing more cores at a highly CPU bound problem really being obtuse or just a logical conclusion? Optimizations are always good but at a certain point your choices really are 'do less' or 'more compute'
You're assuming it's CPU bound rather than memory bound.
It's more of an educated guess seeing as the utilization of one core is always 100% when playing the game.
In the interests of being thorough though I went and underclocked my CPU to 2ghz from 3.7ghz and my FPS went from 38 to 20
And then returning the CPU to normal underclocked my ram from 3200mhz to 1600mhz and found my FPS went back to 38
-
Oh yea, another check: in earlier versions, making the surface unpathable for wild animals, especially intricate operations of mining or large amounts of open magma, would cause lag. has that been fixed?
-
Is throwing more cores at a highly CPU bound problem really being obtuse or just a logical conclusion? Optimizations are always good but at a certain point your choices really are 'do less' or 'more compute'
You're assuming it's CPU bound rather than memory bound.
It's more of an educated guess seeing as the utilization of one core is always 100% when playing the game.
In the interests of being thorough though I went and underclocked my CPU to 2ghz from 3.7ghz and my FPS went from 38 to 20
And then returning the CPU to normal underclocked my ram from 3200mhz to 1600mhz and found my FPS went back to 38
underclocking your RAM that much isn't going to matter much when it takes well over 100 clocks to even get to the RAM in the first place (https://stackoverflow.com/questions/4087280/approximate-cost-to-access-various-caches-and-main-memory)
-
Is throwing more cores at a highly CPU bound problem really being obtuse or just a logical conclusion? Optimizations are always good but at a certain point your choices really are 'do less' or 'more compute'
You're assuming it's CPU bound rather than memory bound.
It's more of an educated guess seeing as the utilization of one core is always 100% when playing the game.
In the interests of being thorough though I went and underclocked my CPU to 2ghz from 3.7ghz and my FPS went from 38 to 20
And then returning the CPU to normal underclocked my ram from 3200mhz to 1600mhz and found my FPS went back to 38
During my tests in previous years the conclusion always was that the FPS rate is directly proportional to the CPU speed (single core), and in any given CPU doubling this speed doubles FPS. Effectively older CPUs with higher performance of single core were better than new ones. I even make decisions of upgrades of my platforms based solely on expected Dwarf Fortress performance :)
-
Is throwing more cores at a highly CPU bound problem really being obtuse or just a logical conclusion? Optimizations are always good but at a certain point your choices really are 'do less' or 'more compute'
You're assuming it's CPU bound rather than memory bound.
Or cache bound…
-
Is throwing more cores at a highly CPU bound problem really being obtuse or just a logical conclusion? Optimizations are always good but at a certain point your choices really are 'do less' or 'more compute'
You're assuming it's CPU bound rather than memory bound.
It's more of an educated guess seeing as the utilization of one core is always 100% when playing the game.
In the interests of being thorough though I went and underclocked my CPU to 2ghz from 3.7ghz and my FPS went from 38 to 20
And then returning the CPU to normal underclocked my ram from 3200mhz to 1600mhz and found my FPS went back to 38
underclocking your RAM that much isn't going to matter much when it takes well over 100 clocks to even get to the RAM in the first place (https://stackoverflow.com/questions/4087280/approximate-cost-to-access-various-caches-and-main-memory)
Doubling the amount of time you have to wait for a response from your RAM chip isn't going to make a difference to a task that's bottlenecked by RAM?
-
Is throwing more cores at a highly CPU bound problem really being obtuse or just a logical conclusion? Optimizations are always good but at a certain point your choices really are 'do less' or 'more compute'
You're assuming it's CPU bound rather than memory bound.
It's more of an educated guess seeing as the utilization of one core is always 100% when playing the game.
In the interests of being thorough though I went and underclocked my CPU to 2ghz from 3.7ghz and my FPS went from 38 to 20
And then returning the CPU to normal underclocked my ram from 3200mhz to 1600mhz and found my FPS went back to 38
underclocking your RAM that much isn't going to matter much when it takes well over 100 clocks to even get to the RAM in the first place (https://stackoverflow.com/questions/4087280/approximate-cost-to-access-various-caches-and-main-memory)
Doubling the amount of time you have to wait for a response from your RAM chip isn't going to make a difference to a task that's bottlenecked by RAM?
If you dispatch a porter who travels one mile per hour one mile away, it'll take 2 hours for a round trip.
If you dispatch 6 porters over the course of 1 hour, you'll get back 6 times as much shit, but your shit still won't arrive until 2 hours post dispatch no matter how frequently you are sending the porters.
Case in point, sometimes you don't get to decide WHERE to ask for information in RAM until after you get a response back FROM RAM, visa vi, if your bottleneck is latency, your bottleneck is latency, and clockspeed won't do shit for you (within sensible ranges).
-
Doubling the amount of time you have to wait for a response from your RAM chip isn't going to make a difference to a task that's bottlenecked by RAM?
If you dispatch a porter who travels one mile per hour one mile away, it'll take 2 hours for a round trip.
If you dispatch 6 porters over the course of 1 hour, you'll get back 6 times as much shit, but your shit still won't arrive until 2 hours post dispatch no matter how frequently you are sending the porters.
Case in point, sometimes you don't get to decide WHERE to ask for information in RAM until after you get a response back FROM RAM, visa vi, if your bottleneck is latency, your bottleneck is latency, and clockspeed won't do shit for you (within sensible ranges).
RAM latency is measured in multiples of its clock cycle time, i.e. lower clock speed directly translates to higher latency because a given operation will take x clock cycles. So yes increasing clock speed will do shit for you.
-
A clock speed of 3200 mhz means you get 3 billion operations in a second, but no force of nature can make electric potential travel from your CPU to RAM and back again in a third of a nanosecond, as that would violate general relativity.
When you talk about RAM latency, you're usually talking about the dead interval between send/receive, which is determined by clock speed as you say.
I'm a network guy, so when I say "latency" I mean signal latency, not time RAM spends waiting to communicate. Sorry for the mismatch in terminology.
Signal latency is hard locked here to the amount of time it takes charge to propagate from RAM to CPU - not sure on exact specifics but it'd take a photon about a nanosecond to round-trip so it's going to take an electron a fuck of a lot longer (as elementary particles measure such things, at least).
Upshot is that if you have a bunch of operations to execute in RAM in series, clock speed will make a massive difference, but if you have conditional shit that needs a round trip to CPU to decide what to do next there's an upper limit to how much clock speed can help.
-
A clock speed of 3200 mhz means you get 3 billion operations in a second
Sort of, actually DDR (double data rate) frequency quoted is twice the actual clock speed because it transfers data twice per clock cycle, so it's 1.6 billion clock cycles per second. But the actual operations like set row to read, read a column etc. take several clock cycles - let's say 15 because that's what mine takes. So it's about 10ns just in the latency for the ram chip to respond, which works out to around 33 clock cycles of my CPU unless I'm mistaken, so I'm thinking halving the memory clock would increase the inherent latency on the chip to a full 66 clock cycles.
But anyway, neither the RAM chip's latency or the delay waiting for the signal to carry through the little wires from RAM to CPU would be increased by underclocking the CPU so I don't see how a highly memory bound workload would show such a direct correlation with CPU clock speed.
-
So as a professional I strongly disagree with the idea that the ONLY way to prevent lag is to limit the player - there's a big toolbox to draw from there. Also the idea.that FPS death is an inevitability with the game as it currently stands is totally ridiculous and abjectly false.
I am talking bigger picture, evidently there is not a single such game where you don't have the late game lag issue, that why these limitations are baked in the design. As simply surmised by @ayy1337 : "Optimizations are always good but at a certain point your choices really are 'do less' or 'more compute'."
Also I said that there is nothing that can be done to prevent late game lag except placing limits (not that necessarily everyone will experience late game lag) you can test that simply by spamming unbound element that effect simulation. That why my fort designs are always conservatives though I would love to run wild with my imagination e.g. building floating islands in the deep with artificial magma/water falls falling between them, around huge statues and fountain alleys everywhere (not the FPS optimized version either), with crazy traps that constantly change map's connection and purify invaders by fire..
p.s. Player feedback and science is always good, the journey has often brought us much insights.
if your bottleneck is latency, your bottleneck is latency, and clockspeed won't do shit for you (within sensible ranges).
True.
-
I'll add my two cents to the limitation topic. As for me I also against it. But i believe the goal for the optimizations it to provide smooth game experience at hardest default settings. Settings that are achievable by clicking the default buttons. In our case it is LARGE world with 500 history and 200 adults + 20 kids. Anyone can create such a game and it should run smoothly. Anything above it could run at lower FPS because you as a player are willingly putting the game under stress.
-
That limiting options is the only thing that can prevent late game lag in such games is a statement of fact to address expectations of what is possible through optimization alone, not a suggestion nor endorsement to do so. The dev choices regarding simulation and game defaults are an example of said limits**, naturally if there were no hard limit on population the game would have run to a crawl as computation demands scaled with population size, and since there are several aspects of simulation that are not limited if you spam them you'd hit the same performance wall no matter the setting.
** Personally, I would prefer the devs to push the limits of simulation/mechanics, not aim for smooth game experience for the average hardware.
Anything above it could run at lower FPS because you as a player are willingly putting the game under stress.
In 'Distant worlds 2' the game checks your CPU and memory and warns against using galaxy settings that are bellow minimum requirements that would severely impact performance, maybe something to consider.
Note you can also set embark size to 6x6 in game.
-
A clock speed of 3200 mhz means you get 3 billion operations in a second
Sort of, actually DDR (double data rate) frequency quoted is twice the actual clock speed because it transfers data twice per clock cycle, so it's 1.6 billion clock cycles per second. But the actual operations like set row to read, read a column etc. take several clock cycles - let's say 15 because that's what mine takes. So it's about 10ns just in the latency for the ram chip to respond, which works out to around 33 clock cycles of my CPU unless I'm mistaken, so I'm thinking halving the memory clock would increase the inherent latency on the chip to a full 66 clock cycles.
But anyway, neither the RAM chip's latency or the delay waiting for the signal to carry through the little wires from RAM to CPU would be increased by underclocking the CPU so I don't see how a highly memory bound workload would show such a direct correlation with CPU clock speed.
Right, sorry, 3 billion distinct opportunities to request/return an operation per second, which is not the same thing as ops per second - my bad.
But we're talking like 100 ns for a round trip here. It's not "one hundred cycles" as Putnam threw out for a random example, it's certainly not 30 cycles as in your example, it's MULTIPLE HUNDREDS of cycles.
Op time and data transfer windows are tiny fractions of the total time the CPU spends waiting. Nobody talks about this part because there isn't dick anyone can do about it, because we haven't managed to make electron wave propagation any faster over those kinds of distances yet, but when you hear things like "accessing data in RAM is an order of magnitude slower than accessing data in the L2 cache" this is what they are talking about. Adjusting the RAM clock is a fractional percent difference here.
That kind of small optimization -really- adds up when you're performing tens of thousands of operations in series - I am not saying RAM timings do not matter for performance - but the moment that one operation depends on the next one to complete it becomes very meager difference. Not all memory I/O problems are created equal, hence me talking about 'latency' vs. 'bandwidth' in network terms.
Here's is how this relates to the CPU / Ram timing test:
Decrease CPU clockspeed - Program moves slower. But you have introduced other opportunities for bottleneck. A program that was not CPU bound before can now become CPU bound.
We have proven nothing with this test, save that there is a point at which CPU speed can be a limiting factor for DF performance, but this shouldn't really be a surprise to anyone.
Turn the CPU clockspeed back up, and adjust RAM timings - Program stays the same speed. But as we've established, if the RAM I/O problem you are having is one of data latency, and not one of bandwidth, adjusting the timings will have near 0 effect.
We have also proven nothing with this test, other than that our problem probably wasn't one of RAM bandwidth.
Hence, we have not proven that the program was CPU bound or memory bound - those observations are consistent with a scenario in which your problems with performance are a result of conditional execution against data in RAM. Given that Putnam has also talked a bit about how conditionals in RAM are a big problem for DF performance, I'm inclined to interpret that as the explanation until evidence to the contrary is presented.
-
But we're talking like 100 ns for a round trip here. It's not "one hundred cycles" as Putnam threw out for a random example, it's certainly not 30 cycles as in your example, it's MULTIPLE HUNDREDS of cycles.
Op time and data transfer windows are tiny fractions of the total time the CPU spends waiting. Nobody talks about this part because there isn't dick anyone can do about it, because we haven't managed to make electron wave propagation any faster over those kinds of distances yet, but when you hear things like "accessing data in RAM is an order of magnitude slower than accessing data in the L2 cache" this is what they are talking about. Adjusting the RAM clock is a fractional percent difference here.
Halving the clock still increases the total time from 100ns to 110ns, enough to make a measurable difference if this is the bottleneck imo.
Whereas it had no impact on FPS but CPU clock speed had a nearly 1:1 reduction in FPS.
If I could underclock my ram any more to get yet more evidence I would, but I think I'll try seeing how linked lists perform at 3200 vs 1600 instead since they are known to be ass slow because of the exact memory latency issue we're discussing.
Another thing to consider is that the unit list and other data structures in the game are afaik stored in vectors which are very apt to efficient memory prefetching when you're iterating it in order, so the latency issue isn't going to be pronounced.
-
But we're talking like 100 ns for a round trip here. It's not "one hundred cycles" as Putnam threw out for a random example, it's certainly not 30 cycles as in your example, it's MULTIPLE HUNDREDS of cycles.
Op time and data transfer windows are tiny fractions of the total time the CPU spends waiting. Nobody talks about this part because there isn't dick anyone can do about it, because we haven't managed to make electron wave propagation any faster over those kinds of distances yet, but when you hear things like "accessing data in RAM is an order of magnitude slower than accessing data in the L2 cache" this is what they are talking about. Adjusting the RAM clock is a fractional percent difference here.
Halving the clock still increases the total time from 100ns to 110ns, enough to make a measurable difference if this is the bottleneck imo.
Whereas it had no impact on FPS but CPU clock speed had a nearly 1:1 reduction in FPS.
If I could underclock my ram any more to get yet more evidence I would, but I think I'll try seeing how linked lists perform at 3200 vs 1600 instead since they are known to be ass slow because of the exact memory latency issue we're discussing.
Another thing to consider is that the unit list and other data structures in the game are afaik stored in vectors which are very apt to efficient memory prefetching when you're iterating it in order, so the latency issue isn't going to be pronounced.
1.6 vs. 3.2 billion cycles per second translates into each "gap" in communication taking 5/8ths of a nanosecond vs. 5/16ths of a nanosecond. I'm not really sure where you're getting '10 nanoseconds' from - I don't follow.
Regardless - Assuming you achieved a 10% difference in your primary bottleneck, that would make a measurable difference in a controlled benchmark - I don't know if that's going to reliably translate to a consistently measurable difference in a Dwarf Fortress FPS counter. My money would be on "no," because in my experience conducting proper benchmarks is hard and observation bias is a bitch.
The linked list vs. the flat vector is a a great case example and I would think that should illustrate the relative performance change in RAM I/O bandwidth vs. latency very clearly.
I would caution against attempting to reduce the problem space to 'oh but DF uses flat vectors so it can't fall victim to pathological cases involving a lot of blind pointer hopping' - this presumes an awful lot about the architecture of software that you don't have the source code for, and more to the point most of the shit I've heard Putnam say about this subject makes me extremely suspicious of that line of reasoning.
-
1.6 vs. 3.2 billion cycles per second translates into each "gap" in communication taking 5/8ths of a nanosecond vs. 5/16ths of a nanosecond. I'm not really sure where you're getting '10 nanoseconds' from - I don't follow.
It's not actually 1.6 vs 3.2 because the actual clock frequencies are half that; so 800mhz vs 1600mhz. And the 10ns come from the fact that the RAM chip can't respond as soon as it receives a request for data. Basic operations on the RAM chip entail several memory clock cycles of waiting before it can start sending data back. Reading a column of memory if the correct row is already open on my RAM takes 15 of its clock cycles. Opening a row if there isn't another one open already takes 15 clock cycles. So opening a row and then reading a column in that row takes 15 + 15 = 30 of its clock cycles from when it receives the request to when it can first starts replying with bits.
30 clock cycles at 1600mhz (DDR3200) is 18.75ns
30 clock cycles at 800mhz (DDR1600) is 37.5ns
If another row is already open the delay is even longer, 45 clock cycles.
You can look up memory timings to read more about it if you wanna.
-
Is throwing more cores at a highly CPU bound problem really being obtuse or just a logical conclusion? Optimizations are always good but at a certain point your choices really are 'do less' or 'more compute'
You're assuming it's CPU bound rather than memory bound.
It's more of an educated guess seeing as the utilization of one core is always 100% when playing the game.
In the interests of being thorough though I went and underclocked my CPU to 2ghz from 3.7ghz and my FPS went from 38 to 20
And then returning the CPU to normal underclocked my ram from 3200mhz to 1600mhz and found my FPS went back to 38
During my tests in previous years the conclusion always was that the FPS rate is directly proportional to the CPU speed (single core), and in any given CPU doubling this speed doubles FPS. Effectively older CPUs with higher performance of single core were better than new ones. I even make decisions of upgrades of my platforms based solely on expected Dwarf Fortress performance :)
Older CPUs have universally worse single-core performance, I have no idea where the idea that they're better comes from. You can run a 6 GHz Pentium 4 and the game will not run it well, not even remotely. It will crash and burn, literally, on both counts, but even if it didn't, it wouldn't run nearly as well as a modern CPU running at 2 GHz.
But we're talking like 100 ns for a round trip here. It's not "one hundred cycles" as Putnam threw out for a random example, it's certainly not 30 cycles as in your example, it's MULTIPLE HUNDREDS of cycles.
Op time and data transfer windows are tiny fractions of the total time the CPU spends waiting. Nobody talks about this part because there isn't dick anyone can do about it, because we haven't managed to make electron wave propagation any faster over those kinds of distances yet, but when you hear things like "accessing data in RAM is an order of magnitude slower than accessing data in the L2 cache" this is what they are talking about. Adjusting the RAM clock is a fractional percent difference here.
Halving the clock still increases the total time from 100ns to 110ns, enough to make a measurable difference if this is the bottleneck imo.
Whereas it had no impact on FPS but CPU clock speed had a nearly 1:1 reduction in FPS.
If I could underclock my ram any more to get yet more evidence I would, but I think I'll try seeing how linked lists perform at 3200 vs 1600 instead since they are known to be ass slow because of the exact memory latency issue we're discussing.
Another thing to consider is that the unit list and other data structures in the game are afaik stored in vectors which are very apt to efficient memory prefetching when you're iterating it in order, so the latency issue isn't going to be pronounced.
1.6 vs. 3.2 billion cycles per second translates into each "gap" in communication taking 5/8ths of a nanosecond vs. 5/16ths of a nanosecond. I'm not really sure where you're getting '10 nanoseconds' from - I don't follow.
Regardless - Assuming you achieved a 10% difference in your primary bottleneck, that would make a measurable difference in a controlled benchmark - I don't know if that's going to reliably translate to a consistently measurable difference in a Dwarf Fortress FPS counter. My money would be on "no," because in my experience conducting proper benchmarks is hard and observation bias is a bitch.
The linked list vs. the flat vector is a a great case example and I would think that should illustrate the relative performance change in RAM I/O bandwidth vs. latency very clearly.
I would caution against attempting to reduce the problem space to 'oh but DF uses flat vectors so it can't fall victim to pathological cases involving a lot of blind pointer hopping' - this presumes an awful lot about the architecture of software that you don't have the source code for, and more to the point most of the shit I've heard Putnam say about this subject makes me extremely suspicious of that line of reasoning.
DF doesn't use flat vectors. This isn't something only I have access to, DFHack exposes most of this stuff. (https://github.com/DFHack/df-structures/blob/4bd9fe468ce2ab9200372e5585dd907dccbea05f/df.world.xml#L854) DF uses vectors to pointers everywhere, to objects that are multiple kilobytes in size each.
-
Is throwing more cores at a highly CPU bound problem really being obtuse or just a logical conclusion? Optimizations are always good but at a certain point your choices really are 'do less' or 'more compute'
You're assuming it's CPU bound rather than memory bound.
It's more of an educated guess seeing as the utilization of one core is always 100% when playing the game.
In the interests of being thorough though I went and underclocked my CPU to 2ghz from 3.7ghz and my FPS went from 38 to 20
And then returning the CPU to normal underclocked my ram from 3200mhz to 1600mhz and found my FPS went back to 38
During my tests in previous years the conclusion always was that the FPS rate is directly proportional to the CPU speed (single core), and in any given CPU doubling this speed doubles FPS. Effectively older CPUs with higher performance of single core were better than new ones. I even make decisions of upgrades of my platforms based solely on expected Dwarf Fortress performance :)
Older CPUs have universally worse single-core performance, I have no idea where the idea that they're better comes from. You can run a 6 GHz Pentium 4 and the game will not run it well, not even remotely. It will crash and burn, literally, on both counts, but even if it didn't, it wouldn't run nearly as well as a modern CPU running at 2 GHz.
I didn't mean as old as Pentium 4, there's too much difference in technology (over two decades), but rather different generations of intel core.
-
older generations of intel core are also worse than newer ones, believe it or not, and the best CPU on the market for playing dwarf fortress is probably an 8-core AMD CPU, and, as of next month, a 16-core CPU with 32 threads... because it has 144MB of L2+L3 cache.
The most important thing for a CPU is single-core performance. The most important thing for single-core performance, at least for a game like DF, is cache size. Look at older Core cache sizes compared to newer ones.
-
When multi-core process first hit the market, many early adopters found that their upgrade preformed worse their older processor, the moral of the story is that newer isn't necessarily better. Single core performance also very between newer processors, and while clock speed can be used as rough indicator in family, it is better look up benchmarks to account for all variables.
-
older generations of intel core are also worse than newer ones, believe it or not, and the best CPU on the market for playing dwarf fortress is probably an 8-core AMD CPU, and, as of next month, a 16-core CPU with 32 threads... because it has 144MB of L2+L3 cache.
The most important thing for a CPU is single-core performance. The most important thing for single-core performance, at least for a game like DF, is cache size. Look at older Core cache sizes compared to newer ones.
I am salivating over how DF could run on Apple Silicon. Very fast single thread and large caches. On paper they look to be the best processor type to run DF. Even better if some of the compute could be offloaded to the dedicated “Neural Engine” co-processor. Not sure how likely that is or if DF uses calculations that could benefit from that processor but it is an appealing thought no?
-
I did another 3-minute profile on my 260-citizen fort, this time with the knowledge of the source. Percents are going to overlap some. Specific seconds are not.
The slowest thing was line-of-sight checks. Due to the fact that it was only counting the checks in the function itself, this was a total of 14.7% of CPU time. However, if you remove one specific thing from line-of-sight checks (more on that later), it's 8%, and thus faster than the next thing. 13.181s in the function itself.
The slowest individual thing in the fort was checking family relationships. This was mostly, so far as I could tell, called in the context of watching performances, probably to tell if they should be feeling love at their family members or whatever. This was 9% of CPU time. 15.537 in the function.
Next is getting glowtiles. This is required for line-of-sight tests, naturally. Glowtile'd creatures are visible from farther in the dark. 5.7%. This is the slowest part of line-of-sight checks, at least as far as stuff that's actually done. 11.749s.
#4 is the game's software rescale function. 4.3%, 7.440s
#5 is probably tile rendering. I think. I see a couple xmms in there and there's a lot of bizarre magic numbers that suggest a switch-case to me. 13.2%, most of which is in subcalls. 5.350s.
#6 is... uh, temperature stuff, I think? 6.3%, 4.888s.
...it just goes like this for a while.
The main point I'm getting to is that 1%, 0.687s, is pathfinding. 1%. 1%. I was wrong earlier and I apologize; pathfinding is not a cause of FPS death at all. It is completely irrelevant to the "slow, inevitable" FPS death people complain about.
-
Never expected family relationships to be so slow. Fascinating information!
I hope you can put it to good use. Fps death is no glorious end to a dwarven life.
-
I did another 3-minute profile on my 260-citizen fort, this time with the knowledge of the source. Percents are going to overlap some. Specific seconds are not.
The slowest thing was line-of-sight checks. Due to the fact that it was only counting the checks in the function itself, this was a total of 14.7% of CPU time. However, if you remove one specific thing from line-of-sight checks (more on that later), it's 8%, and thus faster than the next thing. 13.181s in the function itself.
The slowest individual thing in the fort was checking family relationships. This was mostly, so far as I could tell, called in the context of watching performances, probably to tell if they should be feeling love at their family members or whatever. This was 9% of CPU time. 15.537 in the function.
Next is getting glowtiles. This is required for line-of-sight tests, naturally. Glowtile'd creatures are visible from farther in the dark. 5.7%. This is the slowest part of line-of-sight checks, at least as far as stuff that's actually done. 11.749s.
That's all pretty interesting, if you don't mind me asking when exactly are line of sight checks being done? Is it once per frame every creature checks whether every other creature is in line of sight or something less frequent? And curious about the family relations stuff too. If it's performances does that mean if there's no taverns that just goes away?
-
I did another 3-minute profile on my 260-citizen fort, this time with the knowledge of the source. Percents are going to overlap some. Specific seconds are not.
The slowest thing was line-of-sight checks. Due to the fact that it was only counting the checks in the function itself, this was a total of 14.7% of CPU time. However, if you remove one specific thing from line-of-sight checks (more on that later), it's 8%, and thus faster than the next thing. 13.181s in the function itself.
Great to see numbers here, thanks!
I know 14.7% doesn't point to any massive optimization potential, but -- is the line-of-sight implementation more amenable to a concurrent/thread-pool approach than the pathfinding? I would not expect LOS to use global mutable state, but I wouldn't have expected that for pathfinding either, so what do I know.
-
I did another 3-minute profile on my 260-citizen fort, this time with the knowledge of the source. Percents are going to overlap some. Specific seconds are not.
The slowest thing was line-of-sight checks. Due to the fact that it was only counting the checks in the function itself, this was a total of 14.7% of CPU time. However, if you remove one specific thing from line-of-sight checks (more on that later), it's 8%, and thus faster than the next thing. 13.181s in the function itself.
The slowest individual thing in the fort was checking family relationships. This was mostly, so far as I could tell, called in the context of watching performances, probably to tell if they should be feeling love at their family members or whatever. This was 9% of CPU time. 15.537 in the function.
Next is getting glowtiles. This is required for line-of-sight tests, naturally. Glowtile'd creatures are visible from farther in the dark. 5.7%. This is the slowest part of line-of-sight checks, at least as far as stuff that's actually done. 11.749s.
#4 is the game's software rescale function. 4.3%, 7.440s
#5 is probably tile rendering. I think. I see a couple xmms in there and there's a lot of bizarre magic numbers that suggest a switch-case to me. 13.2%, most of which is in subcalls. 5.350s.
#6 is... uh, temperature stuff, I think? 6.3%, 4.888s.
...it just goes like this for a while.
The main point I'm getting to is that 1%, 0.687s, is path finding. 1%. 1%. I was wrong earlier and I apologize; pathfinding is not a cause of FPS death at all. It is completely irrelevant to the "slow, inevitable" FPS death people complain about.
Last time I had FPS issues however they were fixed by walling off the cavern. Unless something major changed with DF 50 vs 47 walling off the cavern made the game go from 4fps to 45... That is pretty significant change and that cant really be explained with what your encountering. Maybe there is some kind of edge cases where path finding does indeed consume more CPU then what your seeing here. I would probably gather some save files from community members that have FPS death and check this again.
-
older generations of intel core are also worse than newer ones, believe it or not, and the best CPU on the market for playing dwarf fortress is probably an 8-core AMD CPU, and, as of next month, a 16-core CPU with 32 threads... because it has 144MB of L2+L3 cache.
This might not be entirely true. The cpu cores in the upcoming 12 and 16 core 3D v-cache CPUs from AMD are split over 2 dies, and the increased chunk of cache is actually only present on one of those dies. Also critically for single threaded apps only cores on the die without the extra chunk of cache can boost up the max advertised frequency. Granted the faster cores can still access the big cache on the other die, but that's only after it's already checked it's own cache and at the penalty of increased latency. This higher cache latency might negate the clock frequency benefit to the point where the 8 core is just as fast as the 12 & 16 core in single threaded cache bound apps like DF. I'm also wondering if our OS's thread manager is going to be aware of these split-cache chips and will be smart enough to schedule threads onto the most appropriate cores. I guess we will have to wait until somebody has run benchmarks with these CPUs to see.
-
So what would that mean for a multi generational fort like Archcrystal? Does it only do a check for family members that are still alive? In the relationships window it will only show up to grandparents I think, although you can select and see their grandparents from that menu.
-
Has anybody ever thought about making dedicated hardware for running DF?
With access to source code, how feasiable would be to design DF optimized hardware? I know that modern processors, RAMs and motherboards are extremely complex to design and would take eons. But what if by using smaller processors like the ones on raspberry and using some clever memory channels on it, and with help of few dedicated FPGAs for some complex number crunching, would it be possible to make custom DF hardware that wouldn't take ages to develop?
It's been well over 10 years since I meddled with FPGAs and hardware design so my knowledge is a little bit rusty.
-
It's at least possible in theory, but I can't imagine that it would be possible to do in anything approaching a reasonable amount of time or effort. As Putnam has discovered, even multithreading parts of the game that are amenable to it has been difficult and not always worth doing. Offloading parts to dedicated hardware would be an order of magnitude harder, even with tools that try to do things like convert C code to Verilog or VHDL.
I'm pretty sure centralized memory access would always be the bottleneck in a system like that. As an example, Putnam mentioned that looking up familial relationships was a surprisingly big time sink in the game right now. That's almost certainly because of random memory accesses across GB of RAM. An accelerator board would mean the game has to pause at that step, shuttle the data over to the accelerator, let it do its job, shuttle the data back and then pick up where it left off. Isolating those bits of the historical figure data so only that has to be copied would help, but it's still a problem and adds complexities of its own.
I guess if you had a truly amazing FPGA with a modern x86 CPU attached that shared a memory bus, you might be able to build some FPGA logic that accelerated some parts of the game and get speedups from it. One advantage of an FPGA circuit is that at least you might not suffer penalties in places a normal CPU would with branch mispredictions, but it depends on the circuit design. Long, complex circuits are going to have terrible clock rates.
Actually, I'd really like to see just how much of DF's time is spent waiting on RAM. I haven't used a modern profiler in ages so I don't know if you can even get that information readily
-
Has anybody ever thought about making dedicated hardware for running DF?
Even assuming it were possible, would it make economic sense?
-
Has anybody ever thought about making dedicated hardware for running DF?
Even assuming it were possible, would it make economic sense?
Nice reply on a thread about the game where the main guy literally spent first 10 years of development barely considering economic sense.
Does everything need to have economic sense in this world or have we passed the time where people do things they actually enjoy?
-
So what would that mean for a multi generational fort like Archcrystal? Does it only do a check for family members that are still alive? In the relationships window it will only show up to grandparents I think, although you can select and see their grandparents from that menu.
Each person who is doing a "listen to story" or whatever is checking that the person they are listening to is their family member or vice versa, so it gets exacerbated massively by having highly populated, tightly-packed taverns (which I did in this profile). The search looks through every historical figure, in a binary search, i.e. it's O(logn), but if you take into account how many units do it it's sorta O(mlogn), which can indeed grow pretty fast.
Last time I had FPS issues however they were fixed by walling off the cavern. Unless something major changed with DF 50 vs 47 walling off the cavern made the game go from 4fps to 45... That is pretty significant change and that cant really be explained with what your encountering. Maybe there is some kind of edge cases where path finding does indeed consume more CPU then what your seeing here. I would probably gather some save files from community members that have FPS death and check this again.
There are multiple known edge cases. There was probably something stuck in some trees in the caverns that wanted to get into your fort or out onto the surface, and walling it off made the caverns completely cut off, thus making it stop trying to do that. Being stuck in trees makes things pathfind every tick or so, which is indeed extremely slow, but most of the time stuff just isn't pathfinding that much.
I did another 3-minute profile on my 260-citizen fort, this time with the knowledge of the source. Percents are going to overlap some. Specific seconds are not.
The slowest thing was line-of-sight checks. Due to the fact that it was only counting the checks in the function itself, this was a total of 14.7% of CPU time. However, if you remove one specific thing from line-of-sight checks (more on that later), it's 8%, and thus faster than the next thing. 13.181s in the function itself.
Great to see numbers here, thanks!
I know 14.7% doesn't point to any massive optimization potential, but -- is the line-of-sight implementation more amenable to a concurrent/thread-pool approach than the pathfinding? I would not expect LOS to use global mutable state, but I wouldn't have expected that for pathfinding either, so what do I know.
Technically yeah, could make a bunch of futures that fill out the line-of-sight info for each individual unit before they're used for the individual units, but the biggest intervention right now is probably just optimizing the "get glowtile" function lol
-
Wow, really cool stuff here. Never would have guessed this was playing such a big part in FPS death. Thanks for sharing!
-
Has anybody ever thought about making dedicated hardware for running DF?
Even assuming it were possible, would it make economic sense?
Nice reply on a thread about the game where the main guy literally spent first 10 years of development barely considering economic sense.
Does everything need to have economic sense in this world or have we passed the time where people do things they actually enjoy?
There’s a difference between someone sitting down and writing a program, and someone creating a microchip. One just requires time, dedication, knowledge, and a basic computer (at a minimum. It’s best to also have a decently recent computer to test it on, as well…). The other requires a lot of very expensive machinery. That machinery must be paid for somehow, which means selling the chips. My question is whether enough chips can be sold to offset the costs of producing them.
-
Has anybody ever thought about making dedicated hardware for running DF?
Even assuming it were possible, would it make economic sense?
Nice reply on a thread about the game where the main guy literally spent first 10 years of development barely considering economic sense.
Does everything need to have economic sense in this world or have we passed the time where people do things they actually enjoy?
There’s a difference between someone sitting down and writing a program, and someone creating a microchip. One just requires time, dedication, knowledge, and a basic computer (at a minimum. It’s best to also have a decently recent computer to test it on, as well…). The other requires a lot of very expensive machinery. That machinery must be paid for somehow, which means selling the chips. My question is whether enough chips can be sold to offset the costs of producing them.
Nobody said anything about creating a microchip. It's about buying already created microchips and developing board for them, and then programming them to suit your need.
I'm guessing you have no knowledge of how FPGAs work. They're not really expensive and you could start out with almost the same money it takes to buy a computer. There are already kits with FPGAs on them which are little more expensive, but almost the same money as a computer. The real way would be to design the PCB yourself, and still that's not expensive to produce either. You can get 100 pieces 200x200 mm 8 layer PCBs for the price of 7.4$ per PCB.
-
This message was posted by error.
-
So what would that mean for a multi generational fort like Archcrystal? Does it only do a check for family members that are still alive? In the relationships window it will only show up to grandparents I think, although you can select and see their grandparents from that menu.
Each person who is doing a "listen to story" or whatever is checking that the person they are listening to is their family member or vice versa, so it gets exacerbated massively by having highly populated, tightly-packed taverns (which I did in this profile). The search looks through every historical figure, in a binary search, i.e. it's O(logn), but if you take into account how many units do it it's sorta O(mlogn), which can indeed grow pretty fast.
Am I right in assuming then that the more historical figures there are (ie, the more history that has been generated) the bigger impact this has?
-
Has anybody ever thought about making dedicated hardware for running DF?
Even assuming it were possible, would it make economic sense?
Nice reply on a thread about the game where the main guy literally spent first 10 years of development barely considering economic sense.
Does everything need to have economic sense in this world or have we passed the time where people do things they actually enjoy?
There’s a difference between someone sitting down and writing a program, and someone creating a microchip. One just requires time, dedication, knowledge, and a basic computer (at a minimum. It’s best to also have a decently recent computer to test it on, as well…). The other requires a lot of very expensive machinery. That machinery must be paid for somehow, which means selling the chips. My question is whether enough chips can be sold to offset the costs of producing them.
Then you have no knowledge of how FPGAs work. They're not really expensive and you could start out with almost the same money it takes to buy a computer
I’m not talking about FPGAs. The question was whether dedicated hardware would make economic sense to produce. FPGAs can be reprogrammed. That means they are not “dedicated”. “Dedicated hardware” would mean something like an ASIC or perhaps even a dedicated CPU.
In any case, you may want to consider the case of the PhysX engine. It was originally developed to run on an FPGA board that it shipped with. Eventually, the company that made it was bought out by NVidia. Nvidia rewrote it using CUDA and ceased sales of the FPGA boards as all that was required now was a decently recent graphics card (note, of course, that this is all academic as I don’t consider GPGPU programming to be using dedicated hardware either…).
-
Has anybody ever thought about making dedicated hardware for running DF?
Even assuming it were possible, would it make economic sense?
Nice reply on a thread about the game where the main guy literally spent first 10 years of development barely considering economic sense.
Does everything need to have economic sense in this world or have we passed the time where people do things they actually enjoy?
There’s a difference between someone sitting down and writing a program, and someone creating a microchip. One just requires time, dedication, knowledge, and a basic computer (at a minimum. It’s best to also have a decently recent computer to test it on, as well…). The other requires a lot of very expensive machinery. That machinery must be paid for somehow, which means selling the chips. My question is whether enough chips can be sold to offset the costs of producing them.
Then you have no knowledge of how FPGAs work. They're not really expensive and you could start out with almost the same money it takes to buy a computer
I’m not talking about FPGAs. The question was whether dedicated hardware would make economic sense to produce. FPGAs can be reprogrammed. That means they are not “dedicated”. “Dedicated hardware” would mean something like an ASIC or perhaps even a dedicated CPU.
In any case, you may want to consider the case of the PhysX engine. It was originally developed to run on an FPGA board that it shipped with. Eventually, the company that made it was bought out by NVidia. Nvidia rewrote it using CUDA and ceased sales of the FPGA boards as all that was required now was a decently recent graphics card (note, of course, that this is all academic as I don’t consider GPGPU programming to be using dedicated hardware either…).
Okay sorry for giving you a disservice by distrusting your knowledge. English is not my native language and I guessed that what I meant by dedicated hardware was explained in the follow up in post which talked about FPGAs. Which the commenter above you promptly understood and gave me an answer I was hoping for and not wasting my time discussing what is meant by dedicated hardware, and also not giving me a stupid condescending answer like 'does it have any economic sense?' If you read my comment in whole you would understand that I was not talking about developing microchips. Thank you for conversation.
-
Each person who is doing a "listen to story" or whatever is checking that the person they are listening to is their family member or vice versa, so it gets exacerbated massively by having highly populated, tightly-packed taverns (which I did in this profile). The search looks through every historical figure, in a binary search, i.e. it's O(logn), but if you take into account how many units do it it's sorta O(mlogn), which can indeed grow pretty fast.
Now, I have no idea about the inner workings of DF, but checking every historical figure seems to be a bit overkill?
A dwarf will never meet their grandfather in your fort if their grandfather is not in the fort.
-
it gets exacerbated massively by having highly populated, tightly-packed taverns
so basically every tavern, unless citizens are heavily restricted in their movements via burrows ?
-
older generations of intel core are also worse than newer ones, believe it or not, and the best CPU on the market for playing dwarf fortress is probably an 8-core AMD CPU, and, as of next month, a 16-core CPU with 32 threads... because it has 144MB of L2+L3 cache.
The most important thing for a CPU is single-core performance. The most important thing for single-core performance, at least for a game like DF, is cache size. Look at older Core cache sizes compared to newer ones.
This is why we need an ARM native Mac version. The M2 should hands down be the fastest machine to run on.
-
So what would that mean for a multi generational fort like Archcrystal? Does it only do a check for family members that are still alive? In the relationships window it will only show up to grandparents I think, although you can select and see their grandparents from that menu.
Each person who is doing a "listen to story" or whatever is checking that the person they are listening to is their family member or vice versa, so it gets exacerbated massively by having highly populated, tightly-packed taverns (which I did in this profile). The search looks through every historical figure, in a binary search, i.e. it's O(logn), but if you take into account how many units do it it's sorta O(mlogn), which can indeed grow pretty fast.
Am I right in assuming then that the more historical figures there are (ie, the more history that has been generated) the bigger impact this has?
Yes, but logarithmically, i.e. if it takes 1 microsecond at one hist fig it'll take 10 microseconds at 1000 and 20 microseconds at 1,000,000
Each person who is doing a "listen to story" or whatever is checking that the person they are listening to is their family member or vice versa, so it gets exacerbated massively by having highly populated, tightly-packed taverns (which I did in this profile). The search looks through every historical figure, in a binary search, i.e. it's O(logn), but if you take into account how many units do it it's sorta O(mlogn), which can indeed grow pretty fast.
Now, I have no idea about the inner workings of DF, but checking every historical figure seems to be a bit overkill?
A dwarf will never meet their grandfather in your fort if their grandfather is not in the fort.
Might want to look up what a "binary search" is
-
A dwarf will never meet their grandfather in your fort if their grandfather is not in the fort.
How else are they supposed to know if their grandfather is in the fort?
-
A dwarf will never meet their grandfather in your fort if their grandfather is not in the fort.
How else are they supposed to know if their grandfather is in the fort?
You can do O(1) existence lookups, like say a hash table of creatures in the fort
-
older generations of intel core are also worse than newer ones, believe it or not, and the best CPU on the market for playing dwarf fortress is probably an 8-core AMD CPU, and, as of next month, a 16-core CPU with 32 threads... because it has 144MB of L2+L3 cache.
This might not be entirely true. The cpu cores in the upcoming 12 and 16 core 3D v-cache CPUs from AMD are split over 2 dies, and the increased chunk of cache is actually only present on one of those dies. Also critically for single threaded apps only cores on the die without the extra chunk of cache can boost up the max advertised frequency. Granted the faster cores can still access the big cache on the other die, but that's only after it's already checked it's own cache and at the penalty of increased latency. This higher cache latency might negate the clock frequency benefit to the point where the 8 core is just as fast as the 12 & 16 core in single threaded cache bound apps like DF. I'm also wondering if our OS's thread manager is going to be aware of these split-cache chips and will be smart enough to schedule threads onto the most appropriate cores. I guess we will have to wait until somebody has run benchmarks with these CPUs to see.
If I understand correctly the Milan-X (third+ gen AMD Epye with 3D cache) has up to 768MB of L3 cache. I've been saying for some time now that what we really want is a CPU with enough on-die cache to fit an entire save file on the die; and this might be getting close for the first time. (How much space is a 1x1 micro-fort these days?) Something like the Epyc 7373X, which has the highest *steady state* clock rate of the 768 MB L3 chips, would only set you back around $4k.
AMD is advertising it for "computational fluid dynamics (CFD), finite element analysis (FEA), electronic design automation (EDA), and structural analysis"; note that these scientific and engineering workloads are governed by many of the same sorts of many-to-many calculations that DF does.
There's a newer 4th generation 9000 series "Genoa" which have 12-channel DDR5-4800 which should help with main RAM <> socket transfer, but I'm not currently seeing one with more than 384MB L3.
Folks asking about specialized chips for DF... the good news is that if you're doing something like simulating the stress and heating on a spacecraft frame during reentry, you've got a very similar sort of workload pattern to DF, and those people have a lot more money than we do. The bad news is that technology still isn't quite up to what DF really needs, and we're looking at chips in the $4k to $12 range just for the CPU.
-
A dwarf will never meet their grandfather in your fort if their grandfather is not in the fort.
How else are they supposed to know if their grandfather is in the fort?
Shouldn't it be possible for the game to compile a list of who's in the fort, and then have dwarves only check that list? Hell, couldn't it also compile a separate list of everyone in a tavern when a performance starts, and then have the dwarves in the tavern only check that second? list
-
#4 is the game's software rescale function. 4.3%, 7.440s
Would implementing a "shader cache" sort of arrangement help here? Is this something you expect the SDL2 update to improve anyway?
-
So what would that mean for a multi generational fort like Archcrystal? Does it only do a check for family members that are still alive? In the relationships window it will only show up to grandparents I think, although you can select and see their grandparents from that menu.
Each person who is doing a "listen to story" or whatever is checking that the person they are listening to is their family member or vice versa, so it gets exacerbated massively by having highly populated, tightly-packed taverns (which I did in this profile). The search looks through every historical figure, in a binary search, i.e. it's O(logn), but if you take into account how many units do it it's sorta O(mlogn), which can indeed grow pretty fast.
Last time I had FPS issues however they were fixed by walling off the cavern. Unless something major changed with DF 50 vs 47 walling off the cavern made the game go from 4fps to 45... That is pretty significant change and that cant really be explained with what your encountering. Maybe there is some kind of edge cases where path finding does indeed consume more CPU then what your seeing here. I would probably gather some save files from community members that have FPS death and check this again.
There are multiple known edge cases. There was probably something stuck in some trees in the caverns that wanted to get into your fort or out onto the surface, and walling it off made the caverns completely cut off, thus making it stop trying to do that. Being stuck in trees makes things pathfind every tick or so, which is indeed extremely slow, but most of the time stuff just isn't pathfinding that much.
I did another 3-minute profile on my 260-citizen fort, this time with the knowledge of the source. Percents are going to overlap some. Specific seconds are not.
The slowest thing was line-of-sight checks. Due to the fact that it was only counting the checks in the function itself, this was a total of 14.7% of CPU time. However, if you remove one specific thing from line-of-sight checks (more on that later), it's 8%, and thus faster than the next thing. 13.181s in the function itself.
Great to see numbers here, thanks!
I know 14.7% doesn't point to any massive optimization potential, but -- is the line-of-sight implementation more amenable to a concurrent/thread-pool approach than the pathfinding? I would not expect LOS to use global mutable state, but I wouldn't have expected that for pathfinding either, so what do I know.
Technically yeah, could make a bunch of futures that fill out the line-of-sight info for each individual unit before they're used for the individual units, but the biggest intervention right now is probably just optimizing the "get glowtile" function lol
Hey there! Software engineer here. Have you considered just caching a pointer to or ID of or whatever data you access often of the dwarves family members inside whatever object represents the dwarf (assuming each hist fig has an ID or teh data you are accessing could be saved there) , so that you dont have to search through the hist figs every time? Do you think that would have a noticeable performance improvement?
Eg a dwarf might have a list of family member names etc, or their ids directly on them. That is updated the first time you check or whatever.
You dont need to include it in the save data, as you would simply cache it the first time you check after the game is loaded. And not check afterwards.
Also, the entire LOS system almost seems pointless. For LOS in adventure mode you could just do something seperate.
-
#4 is the game's software rescale function. 4.3%, 7.440s
Would implementing a "shader cache" sort of arrangement help here? Is this something you expect the SDL2 update to improve anyway?
An SDL2 update would be very appreciated. The Linux distribution I’m currently using doesn’t support the old SDL…
-
SDL2 update is mostly done, I didn't do terribly much in the way of optimization besides the inherent optimization you get from moving to the GPU; however, you can just turn off the rescale function, so at least that's going on.
There's already a texture cache for rescaled stuff, it's just invalidated rather often. A bit less often with SDL2, though.
-
Will a fort on a 5-year-old world run faster than a fort on 500-year-old world because there are less historical figures to check for familiar relations?
-
Yes, but negligibly, the main issue here is activities (storytelling, poetry etc.) with dozens or even over a hundred units involved
-
#4 is the game's software rescale function. 4.3%, 7.440s
Does playing the game at 100% scale help a lot with lowering this number? Then only 8x12 interface/text tiles would still need scaling.
-
#4 is the game's software rescale function. 4.3%, 7.440s
Does playing the game at 100% scale help a lot with lowering this number? Then only 8x12 interface/text tiles would still need scaling.
Yes, zoom out twice for 1:1 and it avoids this I think? Keep in mind that it is on the graphics thread and thus has little-to-no impact on FPS
-
Yes, but negligibly, the main issue here is activities (storytelling, poetry etc.) with dozens or even over a hundred units involved
Did you see what I asked?
-
In my first Steam Edition Fort back at the beginning of December'22 several actions that would spook the game, from strafing the map too quickly to saving the ###ing game
would result in Core 1 of 16 to be at 100%+ Capacity whilst the other 15 were 5-0%. On a 12600KF with 16GB 4000mhz RAM. It Struck me as a little excessive.
-
Fascinating results, and I'm currently playing a fortress that I suspect is demonstrating this perfectly. 120 citizens, all caverns+magma revealed (but sealed off), 250 year history, yet still sitting at my 50 FPS frame cap. What's different here? It's a reclaimed worldgen fort.
If the FPS issue was pathfinding, those should be awful - they're expansive and convoluted. But instead I think I'm benefiting from that. Spreading all the workshops and meeting areas through that convoluted space means there's rarely more than a dozen people in one place, and they can't see into neighboring areas at all. I wonder if it further helps that most of the fort was dug out for me already. I get all that space to spread out in, and even a huge surface building to block out the great outdoors, but not thousands of boulders for the game to track.
-
Yes, but negligibly, the main issue here is activities (storytelling, poetry etc.) with dozens or even over a hundred units involved
Did you see what I asked?
Yes. Putnam and other people have been talking about this for (approx) 5 years if not more.
Edit: to be more precise this usually was talked about in dfhack contexts (i.e. dfhack irc or discord)
-
Yes, I've talked a few times about rewriting basically the whole system to be more structure-of-arrays instead of array-of-structures, with more caching of things in a lot of places, but that's an ordeal. Like, it would take longer to implement than multithreading, albeit easier (a lot more work but it's far less likely to break for mysterious reasons)
-
A dwarf will never meet their grandfather in your fort if their grandfather is not in the fort.
How else are they supposed to know if their grandfather is in the fort?
You can do O(1) existence lookups, like say a hash table of creatures in the fort
Sure, why don't you get right on that.
-
SDL2 update is mostly done, I didn't do terribly much in the way of optimization besides the inherent optimization you get from moving to the GPU; however, you can just turn off the rescale function, so at least that's going on.
There's already a texture cache for rescaled stuff, it's just invalidated rather often. A bit less often with SDL2, though.
Kinda wish there was a Linux version of premium to be fair.. Running it in proton is buggy, workable but buggy and very slow for some reason then on native windows.
-
You can do O(1) existence lookups, like say a hash table of creatures in the fort
Sure, why don't you get right on that.
Sure mate just let me fire up my copy of the source code and write it in :')
-
SDL2 update is mostly done, I didn't do terribly much in the way of optimization besides the inherent optimization you get from moving to the GPU; however, you can just turn off the rescale function, so at least that's going on.
There's already a texture cache for rescaled stuff, it's just invalidated rather often. A bit less often with SDL2, though.
Kinda wish there was a Linux version of premium to be fair.. Running it in proton is buggy, workable but buggy and very slow for some reason then on native windows.
working on it, main issue right now is concurrency woes (the game does use multithreading, to an extent, and even the very minor extent it does use it is causing issues lol)
-
(How much space is a 1x1 micro-fort these days?) Something like the Epyc 7373X, which has the highest *steady state* clock rate of the 768 MB L3 chips, would only set you back around $4k.
Savegame memory is heavily dependent on world size and history length. The Irritan Anam succession game is a med world with 100 years of pregen history and 7 years of fortress play, and it's only 141MB. The Museum III generated 1000 years with a very large world, and by turn 78 (the one I have on hand) it has gone through a few extra centuries of multiple fortresses and adventurers. It's 766MB, just under the max load of that L3 chip.
-
SDL2 update is mostly done, I didn't do terribly much in the way of optimization besides the inherent optimization you get from moving to the GPU; however, you can just turn off the rescale function, so at least that's going on.
There's already a texture cache for rescaled stuff, it's just invalidated rather often. A bit less often with SDL2, though.
Kinda wish there was a Linux version of premium to be fair.. Running it in proton is buggy, workable but buggy and very slow for some reason then on native windows.
working on it, main issue right now is concurrency woes (the game does use multithreading, to an extent, and even the very minor extent it does use it is causing issues lol)
Glad to hear this is a Linux issue (and disheartened but good to hear it's on the radar to be addressed). I've had to abandon forts so early because of severe FPS drops with sub-100 populations even. My Windows version is running fine so far.
-
SDL2 update is mostly done, I didn't do terribly much in the way of optimization besides the inherent optimization you get from moving to the GPU; however, you can just turn off the rescale function, so at least that's going on.
There's already a texture cache for rescaled stuff, it's just invalidated rather often. A bit less often with SDL2, though.
Kinda wish there was a Linux version of premium to be fair.. Running it in proton is buggy, workable but buggy and very slow for some reason then on native windows.
working on it, main issue right now is concurrency woes (the game does use multithreading, to an extent, and even the very minor extent it does use it is causing issues lol)
Glad to hear this is a Linux issue (and disheartened but good to hear it's on the radar to be addressed). I've had to abandon forts so early because of severe FPS drops with sub-100 populations even. My Windows version is running fine so far.
I haven't tried running it with pure wine however so it may actually run a little better that way. I may try this when I get my gentoo install completed on my laptop.
-
(How much space is a 1x1 micro-fort these days?) Something like the Epyc 7373X, which has the highest *steady state* clock rate of the 768 MB L3 chips, would only set you back around $4k.
Savegame memory is heavily dependent on world size and history length. The Irritan Anam succession game is a med world with 100 years of pregen history and 7 years of fortress play, and it's only 141MB. The Museum III generated 1000 years with a very large world, and by turn 78 (the one I have on hand) it has gone through a few extra centuries of multiple fortresses and adventurers. It's 766MB, just under the max load of that L3 chip.
The main reason the museum world save is large is the ridiculous amount of player fortresses (60+) and the fact that the whole world has been explored/visited with people leaving a mess everywhere that needs to be saved. It's only a medium sized world if you account for the weird dimensions, worldgen was 700 years, but with very low populations because a zombie apocalypse happened.
-
Native Linux version seems to be working now, but thorough testing is quite difficult, so look forward to that. Mac version will need a setup to compile on.
-
Mac version will need a setup to compile on.
I'm happy to volunteer as a tester for early Mac builds. I have access to both Intel and Arm Macs.
-
So does this mean that helix rampcases don't incur any FPS improvements over a central up/down staircase, and that we can make our fortresses as rib-structured as we'd like? Or do these have improvements for LOS as well?
-
Helix rampcases without a central hole are significantly better than staircases, since dwarves can see up and down stairs
-
Actually this thread is kinda classic example about one old computer science proverb: optimizing before profiling is worst idea. Just as clear and perfect as it can be.
1%, my god, i can't belive in it.
-
Native Linux version seems to be working now, but thorough testing is quite difficult, so look forward to that. Mac version will need a setup to compile on.
Did you fix the concurrency issues? Are you getting a Mac mini or a MacBook Air? If you want to save some money, you might consider buying a Apple refurbished model. They look new, and I think they include the same warranty as if they were new. https://www.apple.com/shop/refurbished/mac
If you get a laptop, I recommend getting a model that includes MagSafe, such as the M2 MacBook Air. That feature has saved me a lot. I often forget to unplug it or accidentally put some force on the plug.
-
Native Linux version seems to be working now, but thorough testing is quite difficult, so look forward to that. Mac version will need a setup to compile on.
Did you fix the concurrency issues? Are you getting a Mac mini or a MacBook Air? If you want to save some money, you might consider buying a Apple refurbished model. They look new, and I think they include the same warranty as if they were new. https://www.apple.com/shop/refurbished/mac
If you get a laptop, I recommend getting a model that includes MagSafe, such as the M2 MacBook Air. That feature has saved me a lot. I often forget to unplug it or accidentally put some force on the plug.
Is DF being ported to run on MacOS on the Apple M-series processors? Any possibility of a general ARM port for Linux?
-
1. maybe
2. maybe
we're not using any hilarious architecture-specific intrinsics so you don't have to worry about that
-
Does the Beta branch currently available on Steam include the Linux build, or will it run the Windows beta via Steam Proton?
-
No and yes
-
> Helix rampcases without a central hole are significantly better than staircases, since dwarves can see up and down stairs
Do hatches block line of sight? Do glass hatches and doors block line of sight?
-
Pretty certain they block line of sight when closed, regardless of material.