Print

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

[ab9rf]

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.

[Miuramir]

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?

[FutileSine]

I mean: https://store.steampowered.com/news/app/975370/view/3625992251248624682

Sped up line-of-sight code

Welp, think he's off to a strong start!

[Stimraug]

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

[ayy1337]

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.

[Putnam]

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.

[da_nang]

I can only assume that the pathfinder is called in different sections of the mainloop and in subcalls.

If it was as simple as

Code: [Select]

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

[ab9rf]

I can only assume that the pathfinder is called in different sections of the mainloop and in subcalls.

If it was as simple as

Code: [Select]

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

[ab9rf]

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.

[da_nang]

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

[ayy1337]

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

[Thorfinn]

@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?

[LuuBluum]

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.

[ayy1337]

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

[Thorfinn]

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?