Print

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

[Shrugging Khan]

Cannot be done. As I said above, map layout could change between frames. So main loop must wait for finishing all pathfinding threads.

Why *must* it? Couldn't the game check whether FPS is low, and if so then reduce the frequency of pathfinding to every second or every third loop?

[Heavenfall]

It seems that pathfinding gets talked about a lot. It's even high in the "eternal suggestion" vote.

I usually start around 150 fps (that is, "game" fps, or ticks). Then it starts dropping below 150 fps around 30-40 dwarves, slowly reaching its low point around 50 when I have about 100 dwarves.
So this tantrum spiral kills off 60 dwarves or so, and I have 40 left. But the FPS stays at 50.

It SEEMS to me (no knowledge in these things) that the game building up thousands of items over time is causing a big problem. Or possibly other problems I can't think of. My point is that, even with 40 dwarves that should need only minor pathfinding, I am still finding my FPS dumped very low.

[3]

My understanding is that the issue is a combination of the two - every time a dwarf goes to find an item, the game parses through everything (or near enough) on the item list.

[Tormy]

I usually start around 150 fps (that is, "game" fps, or ticks). Then it starts dropping below 150 fps around 30-40 dwarves, slowly reaching its low point around 50 when I have about 100 dwarves.
So this tantrum spiral kills off 60 dwarves or so, and I have 40 left. But the FPS stays at 50.

Now that sounds weird...and what happens when you save/quit -> reload the game? Your FPS is still around 50, or is it back to 100-150?

[devek]

Doesn't matter. Assuming you make path finding (or any other threading call for that matter) truly asynchronous and the overhead of kicking off your pool thread is less than the work it's doing then you've saved work for the main thread.

Which is what I have been saying, heh. Processors literately do billions of instructions per second, but only thousands of asynchronous work units per second(unless you're using an advanced operating system/arch like solaris). To understand why, you have to know how processors and operating systems work. On a desktop pc with windows each thread is an actual program, with all of the overhead of being started, scheduled, put into different run states, and the system calls(interrupts yay) to communicate with.

I'm not an ant, I see the big picture.
/archer

Agreed, but who cares? As I said if even one dwarf needs to pathfind then that's a potential savings for the main thread.

It will cost the main thread more time to dispatch the job and retrieve the result than it will to just do the job itself. Assuming your graph search algorithm is not worse than what we had in the 50s...

Most of my threading implementations get redesigned because half way through the client suddenly remembers that oh yeah there's this thing we forgot to tell you that completely changes how that's going to work. Or they work great for what they're designed to do but the locking scheme is totally incompatible with the new feature we're adding 6 weeks from now.

I don't know what platform you guys are on, but there are libraries that will force you to code in a way that prevent you from hitting those walls. http://software.intel.com/en-us/articles/buy-or-renew/ . Java has nice concurrent libraries, and lately I have been having fun with Qt's concurrent library (QT is so java like.)

I have absolutely zero concrete knowledge of how the DF internals work. Only a reasonable extrapolation of how they could in theory work. And based on that I gave a hypothetical example of how I'd do it after 2 minutes of halfhearted pondering.

And I still maintain that threading is a net gain for any given task if (number of concurrent tasks * thread execution time) > ((overall threading maintenance * main loop executions) + (thread spawn time * number of concurrent tasks)). Until you can refute that statement or explain how it does not hold true for pathfinding in DF then you've got no case as far as I can tell.

You can't see the contradiction there? You don't know how DF works, so you make your decision to thread based off your theory of how it might work. Then you ignore the people who write advanced utilities for DF and know a lot about how it works...

Toady is not some sort of programming god. He's a absurdly motivated programmer and there are a hell of a lot of things in DF that are done right. But there are also a hell of a lot of things done wrong.

There are very few programmers who have written something as complex and massive as Dwarf Fortress. Look at major games that come out these days, they may have millions of dollars of art assets but the internal game engine typically has nothing on DF. I've worked on some cool projects, but I was working with people. I've done some cool stuff by myself, but nothing close to being that large.

Considering that we are on version .31, I would like to know specifically what was done wrong. The game is in the "we can we do" cycle, so the fact it works as well as it does and doesn't crash is an achievement. There is nothing done wrong, there is just stuff that hasn't been done yet.

[MaDeR Levap]

Cannot be done. As I said above, map layout could change between frames. So main loop must wait for finishing all pathfinding threads.

Why *must* it?

After change of layout, previously calculated pathes can became invalid, but it is smallest issue. Biggest problem: when main loop starts pathfinding threads and wait to complete all of them before doing other things, it can be easily ensured that memory is in consistent state. Unexpected changes in memory during access from other thread can lead to Very Bad Things, from stucked dorfs to seemingly unrelated sudden crash half of hour later and all in between. 0.31.1 bugginess would be very mild in comparison. This is one of reasons why True Multithreading(tm) is pain in ass.

Couldn't the game check whether FPS is low, and if so then reduce the frequency of pathfinding to every second or every third loop?

Game should not change AI behaviour only because your computer is crap. FPS issues are unrelated to in-game things and should not influence them.

And for other comments - yes, pathfinding is only one issue that contributes to low FPS. For me, Toady worked sufficiently on pathfinding for now (we know he worked - some bugs was related to some arcane optimisations of pathfinding). Other issues... I really would like in stocks screen to read these 10000 stones somewhat faster. It is very visible that slowiness is not linear - reading 20k stones takes more than twice as long as 10k stones.

There is nothing done wrong, there is just stuff that hasn't been done yet.

Yes, there are many things done wrong. One example: very direct connection between UI and internal code. Ever wondered why notes and routes are in same menu? Why, it is because same code handles them, not because it is most convienent/sensible from perspective of user interface. Hell, UI itself is one thing that is total utter crap.

[devek]

The moment you're having to pay money to play DF, you can say parts are crap instead of not finished.

[MaDeR Levap]

The moment you're having to pay money to play DF, you can say parts are crap instead of not finished.

Non sequitur. Game is not free from criticism just because it is for free (no pun intended).

[devek]

That word doesn't mean what you think it means.

Calling the halfway finished Mona Lisa crap, is pretty ignorant.

Calling Vista crap when it was released, was pretty right on.

See the difference?

[zwei]

It seems that pathfinding gets talked about a lot. It's even high in the "eternal suggestion" vote.

I usually start around 150 fps (that is, "game" fps, or ticks). Then it starts dropping below 150 fps around 30-40 dwarves, slowly reaching its low point around 50 when I have about 100 dwarves.
So this tantrum spiral kills off 60 dwarves or so, and I have 40 left. But the FPS stays at 50.

It SEEMS to me (no knowledge in these things) that the game building up thousands of items over time is causing a big problem. Or possibly other problems I can't think of. My point is that, even with 40 dwarves that should need only minor pathfinding, I am still finding my FPS dumped very low.

It seems that game simply does not forget about any creature. Unit list slowly, but surely fills with pages and pages of units.

It would say pathing is least of issues and items are most influential of things you can do.

My recent example:

150 fps (hard cap) on embark, 10 game years later and 80 dwarves, FPS is 9.

Map has lots of fluids and fluid dynamics (four rivers meet there, two waterfalls, some moats). Fps after all water freezes in winter? still 9.

Dumping some goblin coprses to atom smasher raised FPS to 13.

Giving away all those hoof earrings to caravans and whatnot raised FPS to 15 which sometimes breaks 16.

Designating whole surface and underground for plant gathering and woodcutting resulted in FPS being at 11 because about ~100 items were just produced from thin air.

Using all logs laying around and building walls from them raised FPS to 13.

Lessons? Leave no stone unturned, use it to build something. Atom smash or trade away everything you do not want to keep. Best way to use cloth is to sew image to something because it turns two items into one. Steel is awesome because its production gets you rid of ten items. Butchering is evil because it turns animal into dozens of items and elves are right because cutting down tree creates item. Worst reactions in game are bolt, waterskin creation and mugs which turn one item into several. Giving away stuff worth hundred thousand dwarfbucks is worth it.

[Urist McDepravity]

Not really. With any loop you don't branch a thread off for each iteration of the loop because starting a thread is more expensive than calculating the path. What you do is make a pool of threads and send them work units.

You totally do. Fork-join is popular, and its the one which is automated in gcc, for example. Read on OpenMP or Graphite.
Pool/queue is not the only solution.

On a desktop pc with windows each thread is an actual program, with all of the overhead of being started, scheduled, put into different run states, and the system calls(interrupts yay) to communicate with

I dont know where did you get this idea, but threads are nowhere near processes in terms of overhead. Context-switching in this case is just switching to different stack.

[Heavenfall]

I usually start around 150 fps (that is, "game" fps, or ticks). Then it starts dropping below 150 fps around 30-40 dwarves, slowly reaching its low point around 50 when I have about 100 dwarves.
So this tantrum spiral kills off 60 dwarves or so, and I have 40 left. But the FPS stays at 50.

Now that sounds weird...and what happens when you save/quit -> reload the game? Your FPS is still around 50, or is it back to 100-150?

FPS stays low. Maybe a couple of FPS higher, but its hard to say. Certainly never above 55 fps.

[Shrugging Khan]

That word doesn't mean what you think it means.

Calling the halfway finished Mona Lisa crap, is pretty ignorant.

Calling Vista crap when it was released, was pretty right on.

See the difference?

Not quite the right take on that. Nobody here's calling DF crap. Only parts of it.

[devek]

I dont know where did you get this idea, but threads are nowhere near processes in terms of overhead. Context-switching in this case is just switching to different stack.

That is only true for a N:1 threading, but that type of implementation does not take advantage of multiple cpus but is the most efficient.

Linux uses 1:1 threading, and hinges the whole thing against _clone. The main difference between _clone and fork is that children share the same address space when you call _clone. Windows basically works the same way. Each thread is seen by the kernel and cpu as a process. 

There are other platforms which do it differently and you need to understand the platform you are using when deciding how to use threads. For Linux and Windows you want to use the least amount of threads as possible, usually 1 per cpu because threads scale horribly on those platforms. Our servers are work use Solaris, and we get... some more choices.

[Makaze2048]

Yes, exactly this assumption comes in play. DF is build around assumption that layout of map can and will change constantly. Tiles are dug out, fluids flow, there was some cave-in...

Pretty sure I covered that aspect. Any changes to pathable squares would be updated by the path threads in a separate and discreet set of path data via a queue updated from the main thread. There are of course a lot of other ways to do that, possible some that are much better, but blocking is about the stupidest way imaginable to do this. So long as the data the pathing threads are working off of is not volatile then they're fine.

Cannot be done. As I said above, map layout could change between frames. So main loop must wait for finishing all pathfinding threads.

Again why? There is no difference between a synchronous pathing call returning results that are invalidated by changes in the next frame and an asynchronous one whose results are invalidated by that same frame. Either way the paths must be recalculated and the main thread must be the absolute authority on actually moving things.

Which is what I have been saying, heh. Processors literately do billions of instructions per second, but only thousands of asynchronous work units per second(unless you're using an advanced operating system/arch like solaris). To understand why, you have to know how processors and operating systems work. On a desktop pc with windows each thread is an actual program, with all of the overhead of being started, scheduled, put into different run states, and the system calls(interrupts yay) to communicate with.

I think you seriously over estimate the overhead for a work thread. If pathfinding is taking up 5% or more of resources (and if it's not then why are we talking about it as a significant performance improvement?) then sorry but there is no way that kicking off threads is going to come anywhere near that kind of burden, especially not when as you suggest you can batch tasks to limit threads. You've also got some serious misconceptions about how threads in Windows work (1st hint, all that crap you mention is done by whatever thread and core the op system is running on not by the DF thread or core).

Also why does there need to be any kickoff? One assumes there would either be a thread pool or a single dedicated pathfinding thread that on event or via polling consumes requests and returns results. You overhead (for the main thread) is negligible.

Java has nice concurrent libraries, and lately I have been having fun with Qt's concurrent library (QT is so java like.)

Excuse me while I chuckle quietly at the thought of actually programming real commercial software in Java...

And let me openly laugh out loud at the thought that you can ever by any means imaginable, technological or otherwise, account for the fickle and ever changing requirements of a client.

You can't see the contradiction there? You don't know how DF works, so you make your decision to thread based off your theory of how it might work. Then you ignore the people who write advanced utilities for DF and know a lot about how it works...

Not really no. I'm speaking in generalities using pathfinding as an example. I've repeatedly asked for a reason why specifically DF pathfinding is a poor candidate for threading. So far all I've gotten back is a lot of hot air and the excuse that pathfinding is cheap and threading is expensive. Neither of which I believe. Threading (if done right) is not all all that expensive and if pathfinding is so cheap then why are we even discussing it as a point for improvement?

There are very few programmers who have written something as complex and massive as Dwarf Fortress.

Disagree completely. DF is quite the accomplishment, especially for a one man team. It is very detailed especially in specific areas, and I'll buy the argument that it's one of if not the most complex and massive game in terms of scope. But to think that it is more complex in terms of programming than a whole lot of other games or commercial software is simply naive.

Look at major games that come out these days, they may have millions of dollars of art assets but the internal game engine typically has nothing on DF.

I've got news for you. Their render alone is more complex than DF in terms of lines of code, operations performed, difficulty, virtually any metric you want to come up with. So yeah if you want to compare gameplay complexity DF is going to be own most anything. But if you're talking overall programming complexity then sorry but it's not much of a competition.

Considering that we are on version .31, I would like to know specifically what was done wrong. The game is in the "we can we do" cycle, so the fact it works as well as it does and doesn't crash is an achievement.

What does the version have anything to do with things? If you're looking at it as an excuse then no need. DF is a one man project with an incredibly ambitious scope and it's free. There is absolutely no need for excuses. There is also no reason not to suggest and reasonably discuss possible improvements.

As for what's wrong it's a big list. UI, flat config files, lack of encapsulation, UI, and lots more. Plus that's only the fraction that we can see indirectly, the code itself is likely a horror show of objectively bad programming brought on by expediency and the organic way in which DF was written. It's not wrong that things are wrong, rather it's an expected part of software development. But glossing over them and attempting to elevate the author to the level of infallible programming messiah is wrong.

There is nothing done wrong, there is just stuff that hasn't been done yet.

Hardly, there's lots of stuff that been done but been done in the wrong way. It might have been wrong when it was written and only revealed by hindsight or it may have become wrong over time. I guarantee you that if that question was put to Toady he'd say the same thing. But I think I will use that line at work sometime

Every single piece of code I've ever written has been relative crap the minute I finished it because having written it I could now do a comparatively better job. If that's not true then you're not learning. Trust me, there's a very long list of things that are wrong in DF if for no other reason than that.