Print

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

[UncleSporky]

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.

[SystemsTestCanary]

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.

[LuuBluum]

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.

[Putnam]

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.

[Mr Crabman]

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".

[Putnam]

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.

[Telgin]

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.

[LuuBluum]

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.

[Mr Crabman]

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?

[eerr]

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...

[Salmeuk]

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

[Putnam]

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.

[bloop_bleep]

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.

[Putnam]

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.

[PHLP_Neo]

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?