Print

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

[NW_Kohaku]

Operation FPS bomb has shown that memory and FPS issues seemingly get 99% fixed when you save and reload.
It's like everything you do ingame causes increasing memory usage and lag which gets cleared when refreshed.
We haven't found the cause of fort ending lag yet though.

No, actually, that's not what it shows.

You can create and destroy millions of items, and the game actually reacts to it fairly well without needing to save and reload.  I ran a fortress for 10 game years straight without reloading, which took two real-life days of running constantly in the background (granted, alot of that spent paused while I was doing silly things like sleeping), and it was back at essentially its initial memory usage when I had essentially the same number of items in the game. 

DF is actually surprisingly very robustly not memory-leaky considering its degree of complexity.


Creating 10,000 items in a reaction in one of my test forts consumes 5 megs of RAM.  (500 bytes per item.)  This is done mostly by the fact that every type of item is in multiple types of vectors. 

Keep in mind that there may be other factors involved - there is the pathfinding connectivity map, the jobs list (considering that this may create more hauling jobs),

All tiles, revealed, unrevealed, etc. already take up several bites of space.  This is already compressed using bitmasks, so that, for example, water and magma depths are treated as 3 bits that determine depth (from 0 to 7) and a single bit that is a flag that determines whether that is magma or water.  Magma and water turn to obsidian to prevent a conflict, and no other fluids are supported.  There are bitmasks used to determine basically everything else about the status of a tile, as well, but generally, you find things like flags used to declare the identity of a workshop or furniture, while a mere flag bit and a pointer are used for tile map purposes.

To compress data, it's basically one giant array of arrays of arrays that is required to be completely static for the game to work properly, so no data is added to this, and it can run at top efficiency.

Revealed and excavated tiles do take up more memory, however, and slow the game down significantly, simply for being revealed.  Simply recording the dirt on the floor takes up some memory, and there's all sorts of pointers that have to point to something that get created for that.

To that guy who said something about flyweight - this already occurs, each "item" in the game is nothing more than a pair (or more) of pointers - a pointer to an item "shape" type, and a pointer to a material type.  Certain types of items have more pointers.  Art objects, for example, have descriptions and quality types and other properties that need more pointers and consume more memory.

With that said, Toady is using C++ STL vectors, and I do think there could be some general responsiveness gains if he made custom vectors that were specifically designed for randomly removing objects from a list thousands if not millions of members long.

[runlvlzero]

Operation FPS bomb has shown that memory and FPS issues seemingly get 99% fixed when you save and reload.
It's like everything you do ingame causes increasing memory usage and lag which gets cleared when refreshed.
We haven't found the cause of fort ending lag yet though.

No, actually, that's not what it shows.

You can create and destroy millions of items, and the game actually reacts to it fairly well without needing to save and reload.  I ran a fortress for 10 game years straight without reloading, which took two real-life days of running constantly in the background (granted, alot of that spent paused while I was doing silly things like sleeping), and it was back at essentially its initial memory usage when I had essentially the same number of items in the game. 

DF is actually surprisingly very robustly not memory-leaky considering its degree of complexity.


Creating 10,000 items in a reaction in one of my test forts consumes 5 megs of RAM.  (500 bytes per item.)  This is done mostly by the fact that every type of item is in multiple types of vectors. 

Keep in mind that there may be other factors involved - there is the pathfinding connectivity map, the jobs list (considering that this may create more hauling jobs),

All tiles, revealed, unrevealed, etc. already take up several bites of space.  This is already compressed using bitmasks, so that, for example, water and magma depths are treated as 3 bits that determine depth (from 0 to 7) and a single bit that is a flag that determines whether that is magma or water.  Magma and water turn to obsidian to prevent a conflict, and no other fluids are supported.  There are bitmasks used to determine basically everything else about the status of a tile, as well, but generally, you find things like flags used to declare the identity of a workshop or furniture, while a mere flag bit and a pointer are used for tile map purposes.

To compress data, it's basically one giant array of arrays of arrays that is required to be completely static for the game to work properly, so no data is added to this, and it can run at top efficiency.

Revealed and excavated tiles do take up more memory, however, and slow the game down significantly, simply for being revealed.  Simply recording the dirt on the floor takes up some memory, and there's all sorts of pointers that have to point to something that get created for that.

To that guy who said something about flyweight - this already occurs, each "item" in the game is nothing more than a pair (or more) of pointers - a pointer to an item "shape" type, and a pointer to a material type.  Certain types of items have more pointers.  Art objects, for example, have descriptions and quality types and other properties that need more pointers and consume more memory.

With that said, Toady is using C++ STL vectors, and I do think there could be some general responsiveness gains if he made custom vectors that were specifically designed for randomly removing objects from a list thousands if not millions of members long.

I suspected as much, but I had not the experience, skill, or vocabulary to make it clear =) It's pretty awesome. You did a fantastic job describing all that.

[expwnent]

Thirding the "probably this" with the caveat that "bad memory design" might actually mean "optimized to use more memory and less processor." There are plenty of techniques that trade off memory usage for speed,  like keeping paths or path segments cached, unrolling loops, and so forth. I think anyone speculating about performance should be required to disclose their skill level in computer science. If you would just start your speculations with something like "I've never programmed a computer before, but..." or "My name's George Broussard..." it would really help. For example, I've been using computers since I was six, in 1976, programming since I was nine, and working in systems administration since I was nineteen. With my level of expertise, and no access to the source code, this is as much as I'm willing to speculate.

Then I'm sure you know that while memory access times have been decreasing, they have not been keeping pace with processor speeds. It is becoming less and less often worthwhile to store extra memory to use less processor time. It is very difficult to accurately speculate on which is faster in any particular case, but the very general tendency is that it's best to use less memory.

I am a graduate student in computer science.

Starting memory usage: ~380,000K and wobbly
After reveal: the same
After digging out a z-level: 397,000K and wobbly

How about you run a control world, spending the same amount of time without digging out a Z-level? Try making two or three small stockpiles that feed from each other to keep your dwarves busy, and put one dwarf into a custom workshop appearifying a Z-level's worth of stone in the meantime.

I have. The results were comparable. I was cheating mercilessly with SPEED:0 so the time to dig out a z-level was only a few minutes. Dwarves did not eat or drink or sleep or do any other jobs in the meantime, and nobody entered or exited the map.

----

Suppose, for each tile, you keep the following information. I am going to make an attempt at an upper bound. This is obviously speculative.

x:4 (bytes)
y:4
z:4
material:30
how much is dug out:2
water amount:1
lava amount:1
vector of things in it:50
vector of creatures in it:50
misc: 3000 (aggressive upper bound I'd say but fine)
the last 10 paths that go through it: Assume average path of length 100. That's 100 coordinates of points. That's 100*12 = 1200 bytes. 10 of those is 12K.

That adds up to 15146 bytes. This upper bound is about half of what I measured.

Am I doing something wrong? What else could be stored?

[Subjektiv]

It should perhaps be noted that the Windows task manager doesn't show you how much memory an application uses, it shows how much memory the OS has assigned to the application and a memory allocation request by the application will either result in no increase in percieved memory use (If there allready is enough free continuous memory assigned to the process) or an increase of X pages, (each page tends to be 4KiB on x86), frequent use of new/delete (or malloc/free) will cause memory fragmentation leaving the process with multiple pages that cannot be filled completely slowing down future allocations and increasing the amount of memory the OS has to assign to the process. (vectors can be a real nightmare for this if you don't reserve a decent sized block when they're created)

This also means that you cannot use the task manager to accuratly detect memory leaks (as the amount assigned to the process tends to grow slightly over time and only really drops down when the program frees everything that resides in a single page)

If performance degrades over time and reloads fix it it is quite likely caused by memory fragmentation rather than memory leaks. (as fragmentation is alot harder to avoid)

[expwnent]

True. This is a very coarse measure of memory usage. However, for large x, if the program needs x more bytes of memory, then the amount of memory that the operating system allocates it should increase by roughly x. A granularity of 4KB shouldn't matter at this scale.

[kaenneth]

I believe the water/lava level is probably stored in 4 bits; 1 bit for if it's water or lava; 3 bits for the depth.

The vector of cell occupants should just be a pointer (4 bytes) to a linked list.

What most assuredly happens is the continual shuffling of items between lists leads to memory fragmentation; which is cleared up by a save and reload cycle.

The question I have is does a cell keep track of which items are in it; or do items keep track of which cell they are in; or (I would guess) both.

[NW_Kohaku]

I just said the part about 4 bits for fluids

Anyway, there is an item vector for each 16x16x1 region of tiles, plus a global item vector plus a few other item vectors that are more specific.

Each one is of pointers, as, again, all references to any material are just references to a single definition of that material, and all item "shapes" are just references to a single definition of some Plato-style perfect "form" of a chair. 

Also, the DF Hack guys basically broke apart the way that all this is put into memory, and it's up on the web on github, so there's no real point in speculating.

[MarcAFK]

TLDR i stand corrected, but basically while your ram use may increase alot it doesn't nessicarily mean lower FPS.
The 8x8's i was playing on an old dual core which sometimes had rather high fps even with 1.5 gb memory use. Lots of objects that were in memory but not really doing much.
I haven't tried very large embarks with this i7 but i'm sure the faster ram would be the main speed increase.

[kaenneth]

TLDR i stand corrected, but basically while your ram use may increase alot it doesn't nessicarily mean lower FPS.
The 8x8's i was playing on an old dual core which sometimes had rather high fps even with 1.5 gb memory use. Lots of objects that were in memory but not really doing much.
I haven't tried very large embarks with this i7 but i'm sure the faster ram would be the main speed increase.

Best hardware change to speed up DF would be a huge on-die CPU cache probably. But those cost $$$ for a reason. The hardest part of making software run fast is making sure the CPU has the data it needs to work on at the moment. The biggest possible speedup to DF might be to profile and re-engineer it's memory structures for cache line alignment; if done well, it could be bigger gains than making it multithreaded; it also is much harder to do it better than the compiler/CPU predictive fetch does.

Think of it this way; a modern CPU runs a 3Ghz; that's 3,000,000,000 cycles per second.
 
The speed of light is 'only' around 300,000,000 meters per second.

Which means, in one clock cycle light (and electrical signals) can travel a whopping 10 centimeters.

A typical DDR memory stick is 3 centimeters tall, and 8 centimeters wide, and at least a few centimeters from the CPU.

So even if the CPU/Memory interface was perfectly fast at requesting and receiving data, it could be idle for 2 out of 3 cycles waiting for data from your super-fast ram.