Print

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

[MaDeR Levap]

One hundred thousand inert rocks should have no effect on FPS.  The game has no need to examine them each frame.

Game do have need to examine them each frame. While there are ways to optimize it, I do not see Toady give it much attention. You can check it for yourself: stock screen, stones, if you have highest precision. You will notice lag. This lag gets unproportionally longer with more rocks. 20k rocks will lock up DF for much longer than 2x time needed for 10k rocks. I would be surprised if other stone (or anything)-handling code is written much better.

Unfortunately, this is all I can say, I do not know how exactly Toady stores item data in DF.

[Vulcanius]

No amount of multithreading or OS optimization is going to fix a horrible algorithm. If I had it my way I'd see http://www.bay12games.com/dwarves/dev.html replaced with simply, "Refactor", for about two or three months. I love having new features and all, but giving a troll new clothes, make-up, and hair plugs doesn't change the fact that it's still an ugly f'ing troll.

Oh, you know, you should go to these morons who use clusters for physics/astro/bio simulations and tell them this. Wasting all those petaflops on something that could be 'refactored', eh...

I'm guessing you're just trolling, because that honestly has nothing to do with this situation.

No amount of multithreading or OS optimization is going to fix a horrible algorithm.

I do not think pathing is that bad (obviously it could use more work, but what thing wouldn't use more work?). I think that other FPS-killing things was neglected, mainly effective management of game object (these tens of thousand rocks...).

Though I suppose pathfinding is the most visible issue I'm actually referring to algorithms in general.

refactor

Oh, this would be Fun. And no, I do not think two or three months would be enough for whole game. And refactoring is unrewarding job: you change code to make it easier to change or extend it in future. So after refactoring, after few months all will work same for player (except plethora of new bugs). This will not fly with this particular fanbase. I see only one solution for this for Toady: take lessons learned while making DF to heart, when (not if, when) he will start Chapter III. I predict abandoment of DF around 0.45 due to multiple issues reinforcing each other in tangled mess.

On related note, I really hope he uses his secret end-month project as opportunity to learn about things like proper multithreading. In other case (and I have very real fear that is case)... lets be blunt: he just waste time.

I'm not sure you fully understand the concept of refactoring. My point of refactoring in the context of Toady and DF is to improve previously written code which obviously suffers from atrocious scalability issues (e.g. it works fine when you have 1,000 items, but fails horribly with 100,000). The pathfinding algorithm is very likely only a small portion of the problem. You correctly said that the functionality of the game would remain the same, however, the performance could be significantly improved. I'm guessing that the majority of DF players would love for that to happen.

Multi-threading at this point would be a horrible mistake. It would be the same bad code with the added detriment of concurrency/syncing issues. I cannot emphasize enough how painful of a process it is to convert a pre-existing codebase from single to multi-threading. The number of bugs introduced with this would be an order of magnitude or two larger than simpy refactoring the code. I think Makaze's A* comment is relevant here, you can't just wave the magic multi-threading wand and gain performance improvements.

[tps12]

Except when a mason needs a rock the game paths to each and every rock out there to determine the nearest one of each type.

The rock to retrieve is determined based just on absolute distance, not pathing. That's why you'll see a mason go on a long meandering journey to get the rock directly below the workshop by 1 Z-level, even though her path takes her past hundreds of other available rocks. So there's just the one path find once the target rock is chosen.

Though in this case I think it's actually looping through all squares and accessing each item in a square which is actually slower if it has to then go find the item by index in an unsorted item list.

There's already a list of items in memory, so I would imagine the game loops through that.

[Makaze2048]

My point of refactoring in the context of Toady and DF is to improve previously written code which obviously suffers from atrocious scalability issues (e.g. it works fine when you have 1,000 items, but fails horribly with 100,000). The pathfinding algorithm is very likely only a small portion of the problem. You correctly said that the functionality of the game would remain the same, however, the performance could be significantly improved. I'm guessing that the majority of DF players would love for that to happen.

I think the point he was trying to make is that refactoring is a boring and generally unrewarding task. Adding a new feature has a lot of wow factor and a big sense of accomplishment at the end. Where as making something run 10% faster and have easier to read code is comparatively unfulfilling (for most people) to do. So regardless of whether or not it's logically the right thing to do it's not likely to get done by a one man team whose primary motivation is finding what he is doing interesting.

And that refactoring will tend to break core aspects of the game. Right now when a new feature is added the new bugs only tend to show up in relation to it, they're easier to track down or avoid as a result. Doing a refactor of something like how items are stored and looked up in memory may be a performance boost but is also likely to touch (and therefor break) large sections of the codebase. And the results tend to be underwhelming as they're more felt indirectly through the absence of negative experience as opposed to the active positive experience of a shiny new feature. So again, even if refactoring is logical, public response to it will not be as favorable as if the time was spend piling in more crap.

Multi-threading at this point would be a horrible mistake. It would be the same bad code with the added detriment of concurrency/syncing issues. I cannot emphasize enough how painful of a process it is to convert a pre-existing codebase from single to multi-threading. The number of bugs introduced with this would be an order of magnitude or two larger than simpy refactoring the code. I think Makaze's A* comment is relevant here, you can't just wave the magic multi-threading wand and gain performance improvements.

Depends. Threading out big chunks like trying to make drawing or input run in it's own thread, damn straight. Doing as I suggested above and having pathfinding run completely asynchronously, damn straight. But tossing off a few read only threads at points in the main loop when data is guaranteed to not be volatile to do something like pathfinding seems like a cheap way to pick up a little bit of performance. Just have to be careful that the threads never ever write anything anywhere for any reason and that you're in a section of the main loop that is either blocked while the threads run or not changing any world data (ie. pathing while doing the calcs for offscreen civs in the main thread).

You definitely can't wave a wand (my comment was more trying to express that, while there might be room for improvement, DF pathfinding is likely a lot slower than generic uniform cost A* because it's doing a lot more), you've got to plan it out carefully and you're not going to suddenly double your speed. But I think you can pick up some performance gains fairly easily by threading simple predictable tasks. Of course it's still largely a bandaid. If the performance on your algorithm is decaying at a geometric or exponential rate as more items are added then running it on linearly more cores is only going to temporarily stave off the inevitable.

And even if I am an advocate for threading if there's room for improvement in the core algorithm then it should be done there before threading is contemplated as an inefficient function now is still going to be inefficient when running on multiple threads.

[tps12]

Since the only thing rocks can do is melt in magma, why not just check the squares magma is in (or next to)?  Why does the temp of every rock on z-1 need to be checked every frame when the magma is on z-50?

They can also spontaneously melt or sublimate, I think, if you gen a hot enough world or mod rocks to melt at lower temperatures. So magma melts stuff because it's hot, not because it's magma.

[Makaze2048]

The rock to retrieve is determined based just on absolute distance, not pathing.

I stand corrected, you're right.

There's already a list of items in memory, so I would imagine the game loops through that.

Of course there's an item list in memory, the question is how, how often, and why it's being accessed. Is temperature data stored in the world tiles or only on the items or both? If in the squares then it doesn't make sense to loop through the item list.

Real question is how the item list is being indexed into by various portions of the game. Do the squares contents array have real pointers to the item or a key to look it up in the list? Or are squares directly unaware of their contents with items maintaining their position information thus requiring a lookup?

Dunno, lots of ways to do things, lots of ways to do it so that things slow down non-linearly as counts increase.

[Vulcanius]

And even if I am an advocate for threading if there's room for improvement in the core algorithm then it should be done there before threading is contemplated as an inefficient function now is still going to be inefficient when running on multiple threads.

QFT. This is basically the whole point I was trying to make... in my round-about sort of way.

I'd also like to address more of what you've said about refactoring however. Refactoring may not be a glamorous process, but in the case of DF it's basically a necessity in my opinion. All of these new features which Toady is adding on a regular basis are only complicating the current mess.

Refactoring code should never break the functionality of a product. It should still pass all of your unit tests with flying colors. In the example you use for instance, modifying the way the data is stored should not ever affect the rest of the code. The reason being that the other various parts of the program should be accessing that data through clearly defined interfaces (e.g. get() and set() methods for example). If you modify those interfaces, they have to remain backwards compatible so that they don't affect your codebase as you've described. If the only way to improve your code is by breaking backwards compatibility it's likely that you have WAY bigger problems.

As for threading, you are correct in saying that it can help improve performance, but will it right now? No. In the future what you have described, 'threading simple predictable tasks', would likely result in some minor performance gains. But guess what is going to be required before that can be done? Refactoring. I can guarantee with 99.999% certainty that Toady will not be able to implement any useful form of multi-threading without first rethinking and reworking many of the ways he does things right now. I wish I could emphasize more what I said before, that converting from a single to multi-threaded codebase is an extremely difficult process, I'd rather have my teeth pulled out with rusty pliers.

[Urist McDepravity]

I'm guessing you're just trolling, because that honestly has nothing to do with this situation.

It does.
This 'game' is intended to be 'fantasy world simulator'. And any complex simulation is CPU-bound, no matter how much you optimize/'refactor' it.
And the only known solution for this is to utilize parallel calculation over multiple computing nodes.

Moreover, I find it amusing that you talk about 'refactoring' and 'poor algorithms' while you have never seen the sources and have no idea what algorithms does Toady use. You cannot provide ANY kind of estimates on worthiness of your 'refactoring' w/out analyzing sources first, while parallel computing is guaranteed to be both 1) worth the effort, giving back significant performance increase, 2) something that would have to be done sooner or later anyway. There is just no way to keep increasing complexity w/out utilizing more resources.

[devek]

Of course there's an item list in memory, the question is how, how often, and why it's being accessed.
...

Real question is how the item list is being indexed into by various portions of the game. Do the squares contents array have real pointers to the item or a key to look it up in the list? Or are squares directly unaware of their contents with items maintaining their position information thus requiring a lookup?

If you were a real programmer, you could take steps to answer these questions.

And even if I am an advocate for threading if there's room for improvement in the core algorithm then it should be done there before threading is contemplated as an inefficient function now is still going to be inefficient when running on multiple threads.

QFT. This is basically the whole point I was trying to make... in my round-about sort of way.

Ya, but you're having the discussion with people who think it takes a nanosecond to start or dispatch a thread. In their world, four threads will run something four times as fast as one thread.

The fact remains that there would never be any performance gains from threaded pathfinding. There isn't a (established) pathfinding algorithm more expensive than a windows or linux thread.

[tps12]

Do the squares contents array have real pointers to the item or a key to look it up in the list? Or are squares directly unaware of their contents with items maintaining their position information thus requiring a lookup?

I think it's the latter. Temperature is stored with the tiles, so each item's location is used to index into the tile structure and find its temperature. (And what devek said, basically; you can actually infer quite a bit how things are done by looking through the dfhack source.)

[Beeskee]

There's a lot of useful programming tips in this thread. Unfortunately there's also a lot of ego stroking and... er  .... measuring contests.   (Also a lot of posts don't really contribute at all, like this one.) It would be nice if we could condense the thread down to useful information for Toady to read.

[devek]

There is nothing useful for him to read in this thread. It isn't like he is just learning to program, lol.

[Beeskee]

I didn't think he was, but even the most experienced programmer can learn new things.

[Makaze2048]

Moreover, I find it amusing that you talk about 'refactoring' and 'poor algorithms' while you have never seen the sources and have no idea what algorithms does Toady use. You cannot provide ANY kind of estimates on worthiness of your 'refactoring' w/out analyzing sources first

One can make an educated guess based on the organic way that DF has grown, current performance, and past bugs and refactor efforts. That guess is that the internals of DF are understandably a friggin mess.

If you were a real programmer, you could take steps to answer these questions.

Or maybe I'm someone with a real job who doesn't have time to muck about with DFhack and just comes here during compiles. Who knows...

Ya, but you're having the discussion with people who think it takes a nanosecond to start or dispatch a thread. In their world, four threads will run something four times as fast as one thread.

NanosecondS in the plural. As in 700-950 of them. And I've yet to hear from you an actual argument as to why exactly it takes longer than that to do a kernel mode transition and have the scheduler set a flag.

And I never said that 4 cores would run anywhere close to 4 times faster. There are significant overheads to contend with. The cost of context switching, cache hits, and competing with the other ~400 threads windows is running at any given time all mean you're never going to see performance increase linearly with core count. But all of those costs (and they are big costs) I just mentioned are paid by those additional cores, not the one running DF that took <1 microsecond to lift a wait.

The fact remains that there would never be any performance gains from threaded pathfinding. There isn't a (established) pathfinding algorithm more expensive than a windows or linux thread.

Ignoring for the moment that that statement is completely pointless since you have not defined the set of pathing data or heuristic...

First of all I don't believe that, there are a lot of games out there that have multithreaded pathfinding. Do you really think they all implemented it without ever benchmarking to see if it was faster? But even if it were true in the case of DF I don't care. The issue here is not total work to be done (and I have no illusions, threading creates additional total work) but rather work that needs to be done by the main thread. It's perfectly fine even if we double our total workload for pathfinding once costs are factored in but are running them across 3 cores. It's still a net gain. Not to mention you can batch all the requests for each frame up and only make 1 thread per free core. If there are not that many path requests and/or they're as cheap as you say then why do we care about pathing as a performance issue at all?

There is nothing useful for him to read in this thread.

On the contrary, if you read the latest podcast transcript he pretty much implies that he's not all that up on threading. I'll say it again, Toady is not an infallible programming god, he's just a man with a disturbing level of obsession for simulating dwarves. Which I appreciate very much, but do not deify him for.

[Makaze2048]

Refactoring code should never break the functionality of a product.

What something should do and what something will do are often not the same thing. In this case I feel pretty confident that any significant refactor will introduce a torrent of new bugs. Not to say that it shouldn't happen anyway, just that's it's not actually likely to.

I wish I could emphasize more what I said before, that converting from a single to multi-threaded codebase is an extremely difficult process, I'd rather have my teeth pulled out with rusty pliers.

Oh, been there done that. It's 10 times worse when it's someone else's code too  It's also a matter of degrees though. I've spent months breaking UI away from business/data logic and into its own thread praying for a meteor to hit the building just so it would end. Or just an hour popping some I/O constrained operation off on its own. Everything just depends on what you need to do and how good the code is (and how well it's documented) before you begin. But yeah, doing that to DF would likely be a nightmare.