Dwarf Fortress Bug Tracker - Dwarf Fortress
View Issue Details
IDProjectCategoryView StatusDate SubmittedLast Update
0005637Dwarf FortressTechnical -- Generalpublic2012-03-13 16:472012-03-21 15:07
ReporterNW_Kohaku 
Assigned ToFootkerchief 
PrioritynormalSeveritymajorReproducibilityalways
StatusresolvedResolutionunable to reproduce 
PlatformOSOS Version
Product Version0.34.05 
Target VersionFixed in Version 
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.
Relationships
Attached Files
Issue History
Date ModifiedUsernameFieldChange
2012-03-13 16:47NW_KohakuNew Issue
2012-03-13 17:41FootkerchiefNote Added: 0021453
2012-03-13 17:41FootkerchiefStatusnew => resolved
2012-03-13 17:41FootkerchiefResolutionopen => unable to reproduce
2012-03-13 17:41FootkerchiefAssigned To => Footkerchief
2012-03-13 17:43FootkerchiefNote Edited: 0021453bug_revision_view_page.php?bugnote_id=0021453#r8002
2012-03-15 01:51kentoIssue Monitored: kento
2012-03-18 08:08KogutIssue Monitored: Kogut
2012-03-21 15:07KogutIssue End Monitor: Kogut

Notes
(0021453)
Footkerchief   
2012-03-13 17:41   
(edited on: 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.