Print

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

[G-Flex]

I think one problem here might be how jobs are created.

I know that jobs are generated by items looking for jobs, so it's possible that every single loose stone is looking to be hauled constantly, or at least checking to see whether or not it can be.


I wonder if forbidding them would help at all.

[Footkerchief]

I wonder if forbidding them would help at all.

Anecdotally, yes:

I've found forbidding stones does help with the lag. Took me from unplayable to mildly annoying when I went to the stock screen and forbid my copious stone piles. Having to unforbid every workshop and construction that used the stone was irritating though.

I doubt it helps as much as not having them at all, though.

[The Architect]

The way I understand objects' impact on lag is as follows, and of course it is purely theoretical. But like any good theory, it is based on solid observational data. It is partially discounted by G-Flex's statement, but let's revise and correct it after it's been hypothecized:

DF, as we know, only assigns a certain amount of some jobs based on the total number of dwarves with that labor enabled. With other jobs, it places them in a que so that they are not constantly performing checks. Examples follow, and I will arbitrarily give them names in order to facilitate reference:

Type A
Hauling labors: if you have 20 dwarves with all hauling labors enabled and no others with any, you'll see up to 20 of each hauling labor in the job que. How labors are assigned and how frequently checks are performed would determine the impact these jobs have. For instance: When is the job assigned, is it a result of cycling through a dwarf's labors or list of total active labors every time a related (or unrelated) dwarf completes a job, are job objects selected based on dwarf location or destination in each instance, (etc.)? Dumping labors seem to bridge the gap between Types A and C, possibly sharing problems with either or both.

Type B
Workshop labors, which will go into the que but (supposedly) only be active and performing checks in order in each workshop, and only when it is active. The biggest drag here, and likely only a small one in sum, is that each time a dwarf takes up a workshop labor a check must be performed for the most appropriate material. Toady has not implemented a pre-task designating feature, overt or otherwise, in this one category alone for multiple obvious reasons. It's a good thing that objects are only "tasked" when a job becomes active.

Type C
Construction labors, which are qued from front to back as they're designated and only perform checks in order of their que. However, unlike workshop labors these jobs designate the material(s) as a fixed point and store that data most likely as a tag on the object. The possible sources of lag here should be self-evident once that is understood.

Type D
This can be used to describe any miscelaneous labors or labors which do not fit the existing arbitrary classifications.

So, that understood, it's easy to see that the number of dwarves, jobs and objects go hand in hand creating lag. If we can use this as a jumping-off point to provide suggestions and data to help the Adams brothers "fix" the lag, that would truly be wonderful.

Notes:

1) When viewed this way I don't think that you can come to a meaningful conclusion about the relevance of pathfinding vs object presence by doing the experiment suggested above, which was to test a few dwarves and a large number of objects in one fort, and a few objects and a large number of active dwarves in another fort.

2) While I believe the biggest drag is probably the tasking feature, it seems to be more of a stopgap preventing truly show-stopping lag than a problem. And other problems such as the one suggested by Blacken (multiple unnecessary iterations) are likely to exist concurrently.

3) Even pathfinding ties into this, as every time a dwarf begins a job and must find an object (often designating the object based on the dwarf's proximity) the game must check the distance of multiple objects. However this is done, whether as a check radiating outwards until a suitable object is found or as a check cycling through objects to find the closest, it's bound to be an obscene processing hog.

4) Other RTS and resource-dependant games preempt the task problem by counting the total number of a resource and allowing you to designate jobs out of that number, a secondary count being displayed to interface involving the number that is not currently designated to a task. Once the secondary number is exhausted, you can't designate more tasks for that resource. However, rather than designating and tagging specific objects the way DF does, materials are selected only when they are actually needed and then (if they have a physical presence, as they do in few enough games) they are moved to site (in our case, it would be by dwarven labor as now).

Toady could significantly benefit by following this procedure, but it would require rewriting DF's object processing from the ground up. This, readers, is what is called a critical flaw. And it's so imbedded that I would dare say it will not be changed before 1.0 is completed. As long as it remains, we will not be solving DF's lag problems. However I did (in my ignorance, as it turns out) think that we might have a chance of coming up with a method to alleviate lag if we put our heads together, and something to present to Toady which he might be willing to help along or do himself, as it must necessarily involve the source code.


So you see: while I might know little to nothing about programming, there's nothing wrong with my logical reasoning. Having examined the problem more carefully and with the help of enlightened individuals, it is obvious that we can't proceed. If this analysis of the labor system sticks and can be corrected and amended well enough, it should be passed on to Toady for consideration when he does finally tackle the speed issue.

[Kilo24]

So... finding prime numbers sounds like it would have two fundamental stumbling blocks:

As I (a lowly non-mathematics major) understand it, there are a number of tricks to figure out large prime numbers, but the only way to guarantee that you know all the prime numbers from 1 to N means that you need to factor each number from 1 to N.

The basic problem with optimizing for multiple cores,  as has been harped on repeatedly, is that we don't have the source code.  We can't isolate the separate systems very easily then, which is needed for multithreading.  There are still a few things that can be done which are relatively easy to separate out (the original hack by the guy who helped with the 40d# releases is one, the Pathfinder project in tweaking an algorithm is another, and there are sure to be a few more things that Toady would bemusedly accept unsolicited help with.)  Multithreading is not one of them.  But we could try to think of things that are decently easy to work with.

Something to keep in mind with any optimization is that it may be wasted when new systems that affect it are added.  This is a huge danger in this stage in DF's development.

And in any case, even if we had access to the source code (which is impossible at this point for reasons that I agree with) we'd still need to spend a lot of time figuring out how the code works.  Toady cares about his game and his community, and I'm pretty sure he'll address our concerns on optimization eventually.  The best solution is to have patience.

I'm curious: what experimentation has been done to prove that pathfinding is the main draw on the computer's resources?  It probably is, but assuming that might cut out other routes of optimization.

[The Architect]

I'm curious: what experimentation has been done to prove that pathfinding is the main draw on the computer's resources?  It probably is, but assuming that might cut out other routes of optimization.

Pathfinding is only a major drain when the computer can't find a path and continually rechecks.

To demonstrate: the pet-impassible door bug and the one-way entrance bug. Since available paths are checked from the job to the dwarf then assigned from the dwarf to the job, you can set up a one-way path and dwarves will continue to attempt to do a job and find "no path". These instances are the only ones I have ever encountered where pathfinding was a major issue. Sure, it's inherently a large draw, but the real draw is (in my belief) the job/stock system as described above. Somewhat streamlining pathfinding will not fix that problem, and will not enable larger fortresses. Perhaps a few more non-dwarf creatures, but the jobs system and the way it is integrated with objects/stocks will still bog down a fortress as it grows.

Does anyone have anything to add to the job/object analysis? I would appreciate correction and ammendation.

[Rysith]

Does anyone have anything to add to the job/object analysis? I would appreciate correction and ammendation.

I'd need to go run some analysis of my own, but you've definitely made some assumptions about the internals of the system that I suspect won't hold up.

From my experience, older forts get slower, accessing things in the stocks with large (2-3K) numbers of items (you're right about stacks) is slow, having hidden creatures pathing is slow, and there is a significant slowdown just after designating large numbers of jobs (such as mass-dumping after a goblin siege). I'd suggest the following tests, with FPS as the benchmark, and may try to run them this weekend if I have time:

1) Seven dwarves, 2x2 flat embark, no liquids, few items (likely just seven picks, for the next step)
2) As above, but mine every single mineable square on the map.
2a) Designate all of the rocks for dumping
3) Seven dwarves, 5x5 flat embark, no liquids, few items
4) As above, but completely mined out
4a) Designate all of the rocks for dumping
5) Seven dwarves, 2x2 flat embark, major river, few items
6) Seven dwarves, 5x5 flat embark, major river with at least 5 region tiles, few items
7) Seven dwarves, 2x2 mountainous embark. Record number of z-levels
Completely mine out the embark from 7
9) Create 200-dwarf 2x2 fortress
10) Save, then split into two timelines:
10a) Take 9, destroy half the items using atom smashers
10b) Take 9, destroy half the dwarves

That seems like it will provide a relatively good picture of what in particular is causing the performance hit.

[The Architect]

~Useful test ideas~

That seems like it will provide a relatively good picture of what in particular is causing the performance hit.

I do think you'll get some useful data, but I seriously doubt we will be able to determine what effect pathing has. From what I have seen, job assignment and the number of items are so interlaced that changing these factors won't give you a clear enough picture.

Liquid flow needs to test flow across z-levels as well. A chasm would be appropriate, or a simple waterfall if you can find one. I'm told a waterfall is a huge drain, and a magma pipe also a huge drain relative to running water. From what I've heard, a brook or river is hardly a drain at all in comparison. I certainly haven't found undisturbed running water to be problematic.

To test pathing, I suggest animals with simple behavior patterns. Placing Dwarves on patrol with ridiculous numbers of moronic pets following might serve the purpose, although some pets have very limited pathing. (They are told to path to a destination then left alone until they arrive, at which point the game checks for proximity to owner and then either designates a new path or leaves em alone. You won't see as much constant pathfinding as you might like to for experimental purposes.) You can mod various animals to all be trainable if that will help pet assignment. I really, really don't see pathing itself to be the issue. I think it's job assignment and stock processing. But we'll see, if you test with animals and not dwarves performing jobs.

[Asmodeous]

I learned a great deal from this thread, though it spawned a question:

Does Win7 have the thread-thrashing issue that was discussed on Page 4 as bad as WinVista did? And if so is there any sort of workaround that I can do to combat that in places where it is more damage than good (i.e. when it is not balancing the load of a slew of programs around and is just moving one really intensive program around) other than simply assigning affinity in the OS or in that program Blacken linked?

[Nadaka]

I learned a great deal from this thread, though it spawned a question:

Does Win7 have the thread-thrashing issue that was discussed on Page 4 as bad as WinVista did? And if so is there any sort of workaround that I can do to combat that in places where it is more damage than good (i.e. when it is not balancing the load of a slew of programs around and is just moving one really intensive program around) other than simply assigning affinity in the OS or in that program Blacken linked?

The "thread thrashing" issue is a heat management feature. By evenly switching heavy loads from one core to another it causes the chip to warm and dissipate heat more evenly and reduces wear on the chip. It does have a performance cost in that the cache will be missed more often, but its still generally a good idea.

[eerr]

The lag is from the crossing of paths.

As it is, the dwarves who head incoming and leave outgoing will eventually pass each other. As it has previously been established, when two creatures are on the same tile only one can move. All creatures avoid pathing collisions with others, even if it means not reaching their destination. Goblins cause the most serious lag when groups try to path through a small vulnerability, usually a tunnel. As far as I can tell, they can sometimes fail to path for the entire siege duration! Pathfinding lag is caused when paths are truncated/blocked/ dealt with however Toady stops collisions.

Ordinary pathfinding happens near instantaneously with no other creatures nearby. Pathfinding that plans around moving creatures that only appear at a given spot in a given time is O(distance + )

In order to lag a computer so, that must reach some incredible price, as if all crossed paths are simultaneously reprocessed for collisions, or perhaps line of sight.
No matter how big the fortress is, visible pathing lag is impossible without pathing "collisions". a tiny pause may appear for an entire army/fortress changing direction(which should statistically cause a large pause from collisions anyway)

[bombcar]

Can't a profiler be run against the code even if we don't have the source? If we can identify a portion of the code that is taking a long time, we can poke it with a stick, even if we don't know what it is.

[Nadaka]

Can't a profiler be run against the code even if we don't have the source? If we can identify a portion of the code that is taking a long time, we can poke it with a stick, even if we don't know what it is.

using poke to alter the memory where executable code resides is generally a really bad idea...

But no, for any program of sufficient size, and dwarf fortress qualifies, you wont be able to make a difference.

[Vicomt]

Can't a profiler be run against the code even if we don't have the source? If we can identify a portion of the code that is taking a long time, we can poke it with a stick, even if we don't know what it is.

you can, but it's pretty pointless. most modern profilers use program databases which are generated as a by-product by the compiler/linker (the programs that turns code into executables). The profiler then reads these databases, maps the function entry points to proper names (as defined by the code) and hooks into the executable to watch where it's going.

without the program databases (pdb's in visual-studio speak) the profiler only has mangled (processor readable, not human readable) names and symbols to work with, and although it'll work, you won't be able to understand what the results are as you don't know which symbolic name maps back to the source code.

[The Architect]

I don't find circumnavigating Toady's ban on the source code to be an edifying topic. Let's not go there again. (not pointing fingers; I'm well aware that many people are just answering questions)

[Asmodeous]

I learned a great deal from this thread, though it spawned a question:

Does Win7 have the thread-thrashing issue that was discussed on Page 4 as bad as WinVista did? And if so is there any sort of workaround that I can do to combat that in places where it is more damage than good (i.e. when it is not balancing the load of a slew of programs around and is just moving one really intensive program around) other than simply assigning affinity in the OS or in that program Blacken linked?

The "thread thrashing" issue is a heat management feature. By evenly switching heavy loads from one core to another it causes the chip to warm and dissipate heat more evenly and reduces wear on the chip. It does have a performance cost in that the cache will be missed more often, but its still generally a good idea.

I know that it's a heat issue, but my system rarely moves above 30degrees on all its heat sensors. Unless I'm playing something way video intensive and my GPU goes up to 35... And that's without the cooling system kicking into high gear, so I was thinking of setting it just for DF before anyway. The scheduler does a fine and dandy job in MOST software, but DF is far more lag-sensitive than any other game I've played. (Years start to drag out to take hours in DF, in other games I just drop some frames now and again, nbd there).

Is setting the affinity in the OS alone good enough for that?

All around this has been an interesting thread that reminded me of why it is I stopped learning coding. Ahh! My lack of patience, hehe.