Print

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

[Stefrist]

Just a short reply for me to keep reading the thread. Takes too long, my boss might not approve :p
I'm going to use a current save for !!SCIENCE!! as well, but it wont have a scientific control group. (or the control group is the FPS drop itself).

I'll keep it posted, interesting subject here.

[NW_Kohaku]

Yes, I understand. The reason why I ask is, both the game waiting for memory becoming available and having to write to HD would probably result in exactly the game slowing down a lot.

I've actually been theorizing that that's the cause, because the game seems to run with excellent speed on my laptop with a SSD compared to another computer of similar processor and RAM but 5400 RPM HD. Unless I'm just imagining it.

Hard drive is never used, thankfully.  If Virtual Memory (using the hard drive instead of RAM) was ever used, you would know it. 

As far as I can tell, DF runs almost completely from memory during actual play with the exception of when it is tracking "off-board" units like historical figures, which it loads from the files in your save directory on the fly, and causes serious slowdown when it does.  This, and load/save time would be the only times hard disk speed would ever matter.

The thing is, memory is about a million times slower than the CPU, which is exactly why DF lags so much - it crunches so much raw data that it can't store anywhere but in RAM because there is so much of it, that something close to 99.9999% of the cycle time is spent waiting on memory fetches. 

Hard disks are significantly slower even than that, generally a hundred times slower, off the top of my head. 

Anyway, items in this game have a data storage space-saving feature in the form of only recording items as pointers.  This causes more waiting on memory fetches, but saves more memory overall, and is why the game is ever even capable of storing such huge amounts of items.  The game basically stores an item without much data attached to it as a pointer to a "shape", such as "boulder" or "goblet", and a "material", both of which are only a single instance in memory that every item of that type or material all point back to in order to get their information.

Pointers are small.  I always like to think of RAM as a giant filing cabinet system, each cabinet a number inside of a box which is labelled.  A pointer doesn't actually contain real information inside of itself, it just tells you what cabinet to look in to get the information you need.   This way, if it's a really large amount of information, you can just have everything point to the one large object, rather than storing a lot of data all over the place.  You also only have to update a single object if you just have pointers to a single piece of data, and the pointers will still be pointing to the right object with the new data. 

You would also need some extra pointers for special data, like how worn out clothes are, or decorations, and creator info, so any given individual object in memory would consist of only about 2-6 pointers (depending on how Toady set it up) in a container in this giant vector. 

Because pointers are small, and you only need a couple pointers, it might only take 4 bytes of memory to store these things.  Because this is a 32-bit system, the hard limit (that most computers have more than) of memory in this game is 2 GB of RAM... so we have roughly enough space for half a billion objects... and my extreme case test was only a million.  (And it effin' killed FPS with the number of pointer traces it had to do, already.)

For reference, I kept Task Manager up when things really got going on the tests.  Just running DF normally?  350 megs of RAM.  (Remember, map data takes up a LOT of data, as it records around five million tiles in a standard embark, each taking up several bytes.) Running DF with a million boulders clogging the system? 550 megs of RAM.  So, basically, 200 bytes total per item (across all the data structures and pointers that would be used) when you have a ceiling of 2 billion bytes of RAM.  Of course, clothing items would take up more than a boulder, as has already been mentioned in this thread.

[Hotaru]

snip

Excellent. Thanks for explaining it. And... I had forgotten to check completely! The computer that gets smoother DF performance has DDR3 1333 MHz ram while the older one has DDR2 667 MHz, despite having the same amount. Maybe that explains it.

So... at this time you know items on the map as well as empty space on the map lead to slowdown, and that the game does sort the hypothetical main item vector. Where can you go from there?

[blue sam3]

The accessibility of space has no noticeable effect.

What exactly do you mean here? Your data dump mentioned nothing about walling off the huge swaths of empty space you dug out. If you meant what I think you mean, then I have a fort that directly counters that statement. A large area of sand was dug out to train some new miners and FPS bombed. When I installed and locked doors to seal off the dug out space, FPS recovered.

Sorry, forgot to put that in the data dump. When I was collapsing the areas, I first channelled around the edges, leaving them supported by a single pillar in the centre, and there was no impact on FPS. It could just be that the shear scale of all of the other effects involved completely blanked it out, I guess. It is also possible that the fact that there was no reason to path through those areas (or anywhere else, really, since all that ever happened was me digging stuff out, and that massacred FPS even on a small scale) and the relatively small population reduced the effects.

Hell even if Toady does squat, we'll know exactly what to avoid.


And open space that isn't pathable definitely contributes to framerate issues. Make two identical worlds/embarks, with the sole exception of the z-levels above the surface. Even only having 1 z level gives me a noticeable bump at high framerates (got 1300 at the start of my latest embark, woo).

That's different.  Available Z levels are known to cause issues, but the number of total levels is static.  If you have a layer of solid stone and a layer of totally mined out stone, it's still a layer.  The difference is, if the dwarf can path through it or not.  If they can, you incur pathing lag atop of world size lag.  If they cannot, you only have standard lag.

Not true, actually. Large inaccessible areas had almost identical effects on framerates for me as large accessible areas, and large channelled out areas were actually worse. (No flyers in game).

[NW_Kohaku]

snip

Excellent. Thanks for explaining it. And... I had forgotten to check completely! The computer that gets smoother DF performance has DDR3 1333 MHz ram while the older one has DDR2 667 MHz, despite having the same amount. Maybe that explains it.

So... at this time you know items on the map as well as empty space on the map lead to slowdown, and that the game does sort the hypothetical main item vector. Where can you go from there?

Yeah, as I said, DF has to routinely check through tens of megabytes of data in memory before it can complete the computations for a single frame, which means the overwhelming bottleneck of DF is in waiting on memory fetching.  As such, RAM latency is probably more important than your CPU in determining how fast DF actually runs.

What I'm trying to do, however, is find the ways in which this vector breaks down.  DF appears to really just use a C++ STL (standard template library) vector in order to handle all the heavy lifting in this regard.  There are two ways to go with this...

One, there is always the possibility that the cleanup routines are not being properly invoked in every instance - which is why I am testing things like atom smashing, and will try testing out magma dumping.  This is the primary reason I started this thread, because there are so many people out there who talk about having "unavoidable FPS decay" when they run long-term forts.  I am trying to isolate why that FPS decay occurs, so that if there are any errors in the maintenance of the vector, they can be fixed.

Two, that the stl vector itself might be better of replaced with a custom-built data type.  Standard vectors are not really well-suited for the removal of data from any point in the vector except the last element of data put into them.  Especially in the cases that I am talking about, where I stuff a million items into that vector, and then start eliminating them from the vector, it basically takes 5 hours to resolve one single instance of the removal process. 

STL vectors, and STL stuff in general is made to be as versatile as possible, but that comes at a cost of not necessarily being as fast in specialized circumstances, so when there's a data structure that's going to do some very heavy lifting at the core of your most significant bottlenecks, like this global item index vector, it can pay to have custom-built methods that are optimized for the task at hand, like handling large-scale and very frequent element removals from the arrays.  As far as I can tell, when I order the destruction of 10,000 boulders, the game has to re-sort that vector one by one for every single boulder that is removed from that vector, leading to nightmarish lag.

Of course, at the same time, it might just be the game is also searching through a million objects in a vector for other reasons, like trying to pathfind to the closest boulder of one million ten thousand separate times, which causes lag on its own.

Either way, though, this is potentially an area for significant optimization, even if it is a rather heavily construed situation I put the game in to make the point.

[Hotaru]

Okay. That sounds really good, but just to be practical, since you will need to contact Toady with the results anyway, wouldn't it be easier to do it with the idea asap? Of course that would detract from the awesome, but... slowdown is the worst "bug" of all (not that I've polled). It's one most players face eventually and it does tend to kill the best forts.

[Girlinhat]

Toady reads the forums, rest assured.  I'm fairly sure that FPS drag over a long time is on his list of "issues of not very significance." but if someone gave him a sheet of paper that said "do this to fix EVERYTHING" then he'd have a lot less work to do and could easily knock out that issue.

[wierd]

One thing he might consider doing is to make his application multiprocessor aware.

There is a *lot* of concurrency in DF, being shoehorned into serial execution. (Or rather, there are a lot of computations that would benefit from parallel processing.)

The ram speed bottleneck is unavoidable, but toady can limit the amount of actual time wasted waiting bay processing several things at once.

For instance, the movement of the bluejay 3 zlevels away is not dependent on fluid calculations.

I understand that parallelism is hard, but he could still simply multithread with some glue.

Getting another core in on the action, even if it is spending most of its time waiting for ram like the main thread's cpu, could speed up actual game time by reducing the size of the process queue. Other tricks might be creatively using 64bit cpu registers on multiple cores, since you can read a register way faster than a fetch from ram. (Eg, you allocate a dummy thread on other cores, just so you can make use of registers on those cores. The communication never leaves the chip dye, so access will be very fast. 64bit registers can hold a surprising amount of data. Not several megabytes.. no... but for things like a flag, or a temporary holding point for pointers, and a location for an accumulator... registers beat ram any day of the week. Course, toady would probably need inline assembler to do that.)


I really think DF would benefit insanely from splitting the main thread into independent subthreads, and pushing them on different cores if available.

[Hotaru]

It's something those of us with 64bit multi-cores would really appreciate, but my understanding is that it's been discussed before and it's generally understood it would take so much effort that he does not consider it economical. Of course if you can present a simple way to do it, maybe it would be different?

[Girlinhat]

Go up to the search bar and type "multi-core" or "multithreading" or any variation there of.  There's a literal endless flood of threads over "baww it needs multithreading!"

You're not the first to think of it, although everyone seems to think they are.  Every week or so you get someone who's like "I've got a great never-before-seen idea that's totally unique!" and then you look and it's like "we should multithread" or "dwarves should wear clothes" or "prepared meals are too expensive".

[NW_Kohaku]

Go up to the search bar and type "multi-core" or "multithreading" or any variation there of.  There's a literal endless flood of threads over "baww it needs multithreading!"

You're not the first to think of it, although everyone seems to think they are.  Every week or so you get someone who's like "I've got a great never-before-seen idea that's totally unique!" and then you look and it's like "we should multithread" or "dwarves should wear clothes" or "prepared meals are too expensive".

I doubt he thinks he's the first to say it, and he does have a point - avoiding the wait on memory fetches is the reason threading exists in the first place.  There have also been well explained arguments on ways in which multi-threading of pathfinding could be implemented without causing too many conflicts (as entirely different creatures pathfinding need not wait on the results of the other creature pathfinding), although these still have problems of waiting on conflict resolution and raise the question of just how many pathfinding operations take place concurrently in an average fort.  (Pathfinding checks don't necessarily take place every frame.)

It's also not that Toady has categorically said that he would never do 64 bit ever, and he's basically tacitly admitted he would try to get around to it, eventually, but that he's putting it off for now.

There is a reason to believe that keeping the topic alive and trying to argue the reasons for something like that, while also explaining the easiest ways to approach it to help Toady approach the subject from the right angle might eventually meet success.

For the time being, however, I'm focusing in on optimizing with what we already have, and looking at ways in which the current system might be buggy.


I'd like to ask once again for someone to try out on their own computer the results of one of my last experiments - http://dffd.wimbli.com/file.php?id=5906

Play with the "FPS Bomb - Small Contraction Experiment - Control" and "FPS Bomb - Small Contraction Experiment - End State" and compare the FPS you get on the two without really doing anything, just letting the game run. 

I think there might be a difference in the FPS lag in that, but want to get some second opinions before I go off with that.

[Hotaru]

It's downloading. But if you don't mind, could you maybe upload it to mediafire or similar? That file server is absurdly slow. Waiting 15 minutes for it to arrive is very disenchanting.

[Hotaru]

So yeah - 64bit Windows 7, intel core i7 2667m, 4 gigs DDR3 1333 MHz ram - both are running steadily 5 minutes into the test and hovering between 55,000 FPS and 53,000 FPS. I can see no difference between them.

Update: 15 minutes into the test, they're still hovering seemingly randomly between 55,000 and 53,000 FPS both. I can see no difference between them, it's more like watching random motion. I think I'll shut this down unless there's a reason to continue, and focus on home security instead

[bombzero]

@multithreading... i have a 64 bit system, you may have one, but what about people with 32 bit? switching to multi-threading would strain 32 bit processors. Also, switching the entire game code would take forever, and introduce a slew of bugs. So long term gain, yes. but with the cost of a portion of the fanbase who have older computers, and a few years of development time, which would drive off another portion of the fanbase.

mostly the calculations need to be optimized, which Toady is trying very hard at, and what NW's experiment could potentially help with.

Also, it is better to improve a single thread process' algorithms then it is to make that process multi-threaded.
having 2,4,6, or even 20 cores with 1 thread a piece wont improve the framerate of the game if the same code issues are dragging it down.

tl;dr: would screw the last few 32 bit users, wouldn't help till the code bugs are fixed, would introduce many new bugs.

@Hataru, im breaking into your house and stealing your computer, just thought id let you know in advance.

[NW_Kohaku]

It's downloading. But if you don't mind, could you maybe upload it to mediafire or similar? That file server is absurdly slow. Waiting 15 minutes for it to arrive is very disenchanting.

I'm actually trying the contraction experiment again, this time with a "medium contraction" of a quarter million items.  I'm still going through the destruction phase, however, and it will continue to "bake" for what appears to be about another hour.

The length of time it takes to destroy all these items, however, definitely displays some geometric complexity growth.  I could run the whole small contraction test in roughly 5 minutes, and I estimate the large contraction test would have taken several days to complete.  This is the difference in time it takes when you are destroying 130,000 objects compared to 1,040,000, so a factor of eight times as much data takes around a thousand times as much time to complete. 

The medium contraction test I am running right now is double the number of boulders of the small, and is looking like it will take about two hours (I should have marked when I started...)


here's a mediafire link: http://www.mediafire.com/?t2n236cdd3sdxo5