0005637: Large quantities of objects appear to degrade FPS even after they are removed from the play area

View Issue Details [ Jump to Notes ]

[ Issue History ] [ Print ]

Project

Category

View Status

Date Submitted

Last Update

0005637

Dwarf Fortress

Technical -- General

public

2012-03-13 16:47

2012-03-21 15:07

Reporter

NW_Kohaku

Assigned To

Footkerchief

Priority

normal

Severity

major

Reproducibility

always

Status

resolved

Resolution

unable to reproduce

Platform

OS Version

Product Version

0.34.05

Target Version

Fixed in Version

Summary

0005637: Large quantities of objects appear to degrade FPS even after they are removed from the play area

Description

From 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 Reproduce

Have 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 Information

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

Issue History
Date Modified	Username	Field	Change
2012-03-13 16:47	NW_Kohaku	New Issue
2012-03-13 17:41	Footkerchief	Note Added: 0021453
2012-03-13 17:41	Footkerchief	Status	new => resolved
2012-03-13 17:41	Footkerchief	Resolution	open => unable to reproduce
2012-03-13 17:41	Footkerchief	Assigned To	=> Footkerchief
2012-03-13 17:43	Footkerchief	Note Edited: 0021453	View Revisions
2012-03-15 01:51	kento	Issue Monitored: kento
2012-03-18 08:08	Kogut	Issue Monitored: Kogut
2012-03-21 15:07	Kogut	Issue End Monitor: Kogut

Notes
(0021453) Footkerchief (manager) 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.

Relationships