View Issue Details

Jump to NotesJump to History
IDProjectCategoryView StatusDate SubmittedLast Update
0005637Dwarf FortressTechnical -- Generalpublic2012-03-13 16:472012-03-21 15:07
ReporterNW_Kohaku Assigned Touser6 
PrioritynormalSeveritymajorReproducibilityalways
Status resolvedResolutionunable to reproduce 
Product Version0.34.05 
Summary0005637: Large quantities of objects appear to degrade FPS even after they are removed from the play area
DescriptionFrom this thread: http://www.bay12forums.com/smf/index.php?topic=104450

Observed behavior from people attempting to maintain a high FPS seems to indicate that permanent FPS bleed occurs whenever caravans appear, even when most items are sent off the map. Likewise, heavy dwarven industries tend to drag down the FPS, even when the total number of items in the game map are kept low.

This implies that items are somehow having a lingering effect upon game engine performance long after the items themselves are destroyed, and points to a probable cause as being an artifact of the means by which items are tracked on the map.

While this is purely speculative, I believe the most likely form of data structure Toady is using to track all items on the map is some form of vector, or custom-built extensible-array-containing-object with vector-like properties. This would account for the apparent lingering effect of items in the list of items - vectors are basically never sorted, even when the pointers they contain are eliminated, because sorting a vector is a massive time-sink.

However, because so many items are so routinely added and subtracted from this giant vector, it eventually leads to a giant vector where a tremendous number of the actual data points are dummy pointers, and the lag that occurs occurs because the game has to routinely iterate through these dummy pointer slots in the vectors to get to the slots in the vectors containing valid pointers.

In order to prevent a form of entropic decay of fortress FPS, a periodic sorting of this vector would be necessary. Because sorting of vectors is highly time-consuming, the best time to put this would likely be a "spring cleaning" that occurs annually alongside all the other seasonal cleaning, possibly only once every two years, depending on how much entropic vector decay routinely occurs in a given fortress. This would give the benefits of the cleaning while putting the burden of the time the cleaning takes on something that already is a "just give up on waiting and go cook yourself dinner" length of time process, anyway.

Since there's no need for the data fields to have any sort of order, you could simply have a pair of pointers, one starting at the front of the vector, and stopping when it hits a dummy pointer that can be filled with a valid pointer to compress vector space, and the other starting at the end of the list, working backwards, and stopping at and transferring any memory field that has data (and garbage collecting completely emptied arrays).

However, that would depend on the ability for you to actually be able to traverse the list backwards somehow, whether by double-linked list or by giving the second pointer a memory of how it got to where it is (by having a linked list of pointers to the individual arrays contained within the vector-like structure).
Steps To ReproduceHave naked (as in remove clothing from the raws) dwarves with as limited a set of loose items on the map as possible, and wait for caravans or invaders to come in. FPS experiences permanent drops even when all items leave the map.

For a more dramatic difference, attempt to change the cargo-capacity of wagons and beasts of burden by an order of magnitude or two. Even after all items are off the map or atom-smashed, there is permanent decay in FPS.
Additional InformationI have no idea whether DF actually uses vectors, or vector-like custom data structure, but it seems that the potential to save quite a few references by simply making a custom data structure whose array size you can dictate (since making arrays of 10,000 as a baseline is not at all an extravagant gesture for the amount of data DF crunches) would entirely justify the cost of reinventing the wheel in this case.
TagsNo tags attached.

Activities

user6

2012-03-13 17:41

  ~0021453

Last edited: 2012-03-13 17:43

 We need evidence. The bare minimum for reports of decreasing in-game performance is before/after saves. To demonstrate the problem, the saves need to control as well as possible for extraneous factors, such as population, flows, and items that are still present on the map.

Evidence from memory hacking would be preferable for confirming the specific algorithmic hypotheses e.g. dummy pointers.

When evidence become available, please reopen this report.

Issue History

Date Modified Username Field Change
2012-03-13 16:47 NW_Kohaku New Issue
2012-03-13 17:41 user6 Note Added: 0021453
2012-03-13 17:41 user6 Status new => resolved
2012-03-13 17:41 user6 Resolution open => unable to reproduce
2012-03-13 17:41 user6 Assigned To => user6
2012-03-13 17:43 user6 Note Edited: 0021453