Print

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

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

I'm quoting myself above because I'd like to follow up. I started dumping and sorting the garbage on the screen, and my fps slowly started to rise again. From 50 FPS at 32 dwarves, I now sit at 65 fps with 55 dwarves. I'll edit the post with an update as I have cleaned the whole map.

Edit: 90 dwarves, 65 fps. At least it seems to have helped a bit.

[devek]

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.

If a thread is blocked, it has to be scheduled to run again. Your program can not do this without operating system and CPU support. When you call a system call, control passes to the kernel and the thread that called it does not run. This overhead varies between platforms but is never negligible. You can avoid that by having the pathfinder thread sit on a spin lock, but that means it would run all of the time using cpu time regardless of if it had work to do (useful in server programming, but not desktop).

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.

Maybe if your shop was more professional, you wouldn't have these problems with your client.

Yes, there are ways to deal with unpredictable and changing requirements. Java isn't the end all(right tool for the job yada yada), but to laugh at it shows you totally missed out on the last 20 years of advancements in computer science. Pick up a copy of the mytical man month, and work forward through all of Knuth and in a few months you should be in the right mindset to know what to do from there.

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.

I never write bad code, even when I do not know what I am doing. I literately started learning QT(and C++ lol) July 24th, and by the 25th I had my first QT program out and released. There are changes that get made as I learn more about the apis, but most of the original code survives in one form or another. Each piece of code is generic as possible, has a specified notation, and follows a pattern which is tested as a unit to verify it works as advertised. Sure, I was able to clear a few lines when I learned about QStringBuilder and I ran into a few c++ gotchas, but that doesn't mean the code before that was crap since updating it only took a few min. When I decided to decouple item types in the game from job types, the functional difference of my program was huge but the refactoring(modern word for cut/paste combined with search and replace) was easy because the code was good.

[devek]

I'm quoting myself above because I'd like to follow up. I started dumping and sorting the garbage on the screen, and my fps slowly started to rise again. From 50 FPS at 32 dwarves, I now sit at 65 fps with 55 dwarves. I'll edit the post with an update as I have cleaned the whole map.

I've been playing with your theory today actually.

I've been writing a program to help you delete items/creatures. So far it doesn't seem to be helping, but I think I know why. Will let you know what happens.

[Makaze2048]

This overhead varies between platforms but is never negligible.

We have different versions of the word negligible then. Considering thread switching time on moderns processors is measured in nanoseconds in the benchmarks I've seen for both Windows and Linux. We'll go ahead and round that up to 1 microsecond for the sake of argument and assume that all costs are born by the main thread. Now, also assuming the exaggeration of us needing 1000 paths found per second and that we're stupidly making each and every one run in its own thread then we're still only looking at using up 1% CPU utilization in thread switching costs. If path finding is not taking more than that then once again why are we even having this discussion?

And we haven't even discussed bound threads which basically eliminates much of the overhead associated with a context switch (no register swapping, no cache thrashing, etc.) and essentially reduces it to a run flag set call.

You can avoid that by having the pathfinder thread sit on a spin lock, but that means it would run all of the time using cpu time regardless of if it had work to do (useful in server programming, but not desktop).

Are you sure you don't mean a strawman lock? Sleep or wait it.

Maybe if your shop was more professional, you wouldn't have these problems with your client. Yes, there are ways to deal with unpredictable and changing requirements.

Thank you for proving to me that you have little to no real world professional experience.

Java isn't the end all(right tool for the job yada yada), but to laugh at it shows you totally missed out on the last 20 years of advancements in computer science.

Name me a major commercial application or game written in Java. You can't cause there aren't really any. Admittedly that's due less to any fault of Java (though there are certainly some) than to the entrenchment of C++ and MS pushing .NET (and it being surprisingly good all things considered). But the point remains that no one does serious commercial or game dev in Java.

Pick up a copy of the mytical man month, and work forward through all of Knuth and in a few months you should be in the right mindset to know what to do from there.

Read it about 15 years ago now, good book. Lots of useful advice. But understanding that something should be done differently does not necessarily make you empowered to actually do it differently. Welcome to corporate America.

I never write bad code, even when I do not know what I am doing.

Congratulations! You're either the worlds best programmer by an order of magnitude or arrogant and naive, I'll leave it to you to decide which is more likely.

[Makaze2048]

Flat config files are a problem? Why?

Mostly referring to the raws, the init files are fine in my opinion. I also meant that they're not something more like a hierarchical XML based format as opposed to the weird implicitly closing scope based on the next tag name thing going on now. No problems with them being in plain text files.

[MaDeR Levap]

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

I assure you I know what non sequitur means. This does not follow. Being free program is not excuse from crappiness.

Calling the halfway finished Mona Lisa crap, is pretty ignorant. Calling Vista crap when it was released, was pretty right on. See the difference?

Unfinished? UI? More like placeholder (DF is riddled in these). And this placeholder user interface is crap. It is like putting partially painted Mona Lisa in shitty pink thin wodden frame with badly stucked-in nails and more holes than swiss cheese. In other words, eyecancer. Worst thing, this crap will stay long, because Toady (and most of players) does not show any interest in better UI any time soon.

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?

Already answered in response to Shrugging Khan:

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.

[Makaze2048]

Already answered in response to Shrugging Khan:

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.

Agreed, that would be a problem IF you did nothing about it. But as I explained there are ways around that. One method among several available being to have a separate set of pathing data that is updated on pathfinding thread startup based on data in a queue populated with any changes from the main thread. The data the pathfinding threads are utilizing cannot be modified by the main thread and so there is no danger from data volatility. That data may be a frame or two old (at most) by the time pathfinding completes but who cares? That situation is identical to a synchronous pathfinding call whose results are invalidated 1 frame later. So yet again I ask why is it not possible?

[Soralin]

Well, you're making computers more efficient but there is still a wall that will be reached.

Once 100% of the power/energy that goes into a computer is used for computations, you can't go further

The good news is, that computer wouldn't require a heatsink or any cooling...

Actually, you could go further. There's always MOAR POWER

http://en.wikipedia.org/wiki/Matrioshka_brain 

I take it you've read Accelerando?

Indeed.

What if a dwarf's pathfinding takes him through an unbuilt wall, the pathfinding takes a couple of frames to complete, the wall is finished while the pathfinding is going on, and that dwarf walks headlong into it? Changes in situation, changes in terrain, burrow alerts, raised drawbridges... Right now, the game *knows* that the pathfinding can't take it through any solid objects, so it doesn't need to do any extra checks of "did I just walk into a wall" when it does move-dwarf.

Exactly the same thing that already happens when a dwarf has a path that becomes invalid. He'll walk into the wall, flash a ?, and search for a new path.  You can try it out yourself, lock a door while a dwarf is in the middle of following a path that takes them through it.  That situation is already covered, those extra checks already exist, they'd have to, because all of the problems you're saying could happen with something changing mid-calculation, will also happen for changes that happen post-calculation, after a dwarf has it's path and is following it, and something changes before they reach their destination.  A dwarf won't recalculate it's entire path every step, that would really take up cpu time, instead they just calculate it a single time, and then follow it, and calculate a new path if it turns out they can't follow the path they took for whatever reason.

Ok, there are a few extra race conditions that could happen, but for the situations I've been able to think of, those should be fairly minor.  I mean, you might have a situation for example with a pair of drawbridges, where one is opening, and the other closing, and the dwarf sees them both as open and attempts to path through that way, but as soon as they bumped into one of them, they'd just find a new path, since the situation of something blocking a dwarf's path is already covered.

[Makaze2048]

Because the pathfinding data might be really, *really* obviated by changes in terrain.

Right now, the game *knows* that the pathfinding can't take it through any solid objects, so it doesn't need to do any extra checks of "did I just walk into a wall" when it does move-dwarf.

On the contrary, that's making the assumption that a path is found from scratch for each and every moving object on any frame that there's a world update that would affect pathing. That would be highly inefficient and it's far more likely that paths are either calculated on a rolling periodic basis with tests for next movement validity each frame or that there is a way to invalidate and recalculate existing paths when that path becomes obstructed due to a world change. We know for certain that it's already doing upon movement checks for mobile obstructions like other dwarves and modifying the paths around them accordingly. Either one (or some 3rd option) would work, it's just a matter of which is more efficient.

The real issue is that you're looking at a possible lag time between when a path is requested and when one is delivered. That dwarf will stand there until the path is found (which might be in the same frame or in a future frame). It might actually happen faster in real time but has the possibility of happening slower in dwarf time. As opposed to when it's done synchronously where he'd get the frame "instantly" in dwarf time. That behavior and the potential for it making the simulation not 100% deterministic (assuming it is now...) may be undesired to the point of making any potential performance gain moot. Of course dwarves do seem to just stand around and do nothing for a while upon receiving a task so I'm not sure that we'd notice a frame or two of lag especially if those frames are coming faster.

The other option to maintain determinism is to always have X frames of delay when calcing paths, even when they're ready sooner. If the paths are not done by the time the Xth frame is ready for them then it blocks till they are. There is still a net gain even when blocking as it will be for a shorter time than the main thread would have taken to do the calcs itself and everything else it needs to do.

But assuming for the moment that you're right and that all paths are completely recalced on a world obstruction change and that asynchronicity is untenable then having a separate thread that blows through all the paths needed while the main thread does the other available tasks for this frame, synchronizes, and then executes paths seems a perfectly valid situation.

[Eugenitor]

Actually, I suspect it's even more inefficient than that. I think that the pathing is recalculated every frame regardless of how much the situation changes. This would explain the bottoming-out of FPS once HFS is breached and then walled in (something I just did in my fort). HFS keeps trying to path out no matter how many times it's failed to do so. Nope, guys, that wall's still there. Nope, still there. Sorry, it's still there...

[Makaze2048]

I have a feeling based on informal observation (and not actual knowledge of the code) that paths are updated on a rolling periodic basis ie. each mobile object with a destination recalculates it's path every X frames or X seconds with the various units spread evenly accross the X run times. With X being hard coded, determined by the number of mobiles, or by FPS. Each of those has pros and cons but all of them are reasonable solutions that help eliminate hitching, explain why some dwarves sit around for a few frames before heading off to a job, and explain why breaching the HFS and adding more pathing units causes slowdown.

At the same time the HFS slowdown could just be related to more units and items being added to the lists and slowing things down due to the almost obligatory several N² operations on these lists.

[Urist McDepravity]

At the same time the HFS slowdown could just be related to more units and items being added to the lists and slowing things down due to the almost obligatory several N² operations on these lists.

Trapped dorfs and animals are known to cause slowdown as well, so its not just item count.

[Tormy]

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.

I'm quoting myself above because I'd like to follow up. I started dumping and sorting the garbage on the screen, and my fps slowly started to rise again. From 50 FPS at 32 dwarves, I now sit at 65 fps with 55 dwarves. I'll edit the post with an update as I have cleaned the whole map.

Edit: 90 dwarves, 65 fps. At least it seems to have helped a bit.

Interesting stuff!

[devek]

We have different versions of the word negligible then. Considering thread switching time on moderns processors is measured in nanoseconds in the benchmarks I've seen for both Windows and Linux.

This is where your lack of understanding fundamentals is hurting you. How in the hell do you plan on starting or dispatching a thread by switching to it? I already told you, when a thread is in the blocked state it isn't being scheduled by the processor and will never be switched to. I made a joke about how you could avoid that with polling and you really gaffed that one up...

You can avoid that by having the pathfinder thread sit on a spin lock, but that means it would run all of the time using cpu time regardless of if it had work to do (useful in server programming, but not desktop).

Are you sure you don't mean a strawman lock? Sleep or wait it.

What? Lol. A strawman lock is a joke. It essentially means... while(true) if (a == 0) { a = 1; break; } It doesn't work because more than one thread could acquire the lock and this is an example that is taught to computer science students...

A spin lock on the x86 is implemented with the CMPXCHG machine code. It is one instruction that compares a memory address with eax, if it the same it replaces it with a given value. It is impossible for two threads to acquire a lock that way. It is useful for things like malloc, where a lock is required but it is never held very long. It is faster for the thread to spin on the lock for a few cycles while the other thread finishes malloc than it is for the thread to block and wait for the operating system to wake it up when malloc is available. You wouldn't spin on something like.. do I need to do pathfinding now because that would totally waste a lot of cpu. Polling like that on desktop applications is rude. That being said, we do use spin locks on servers.

Now, to finish that rant.... Sleep or wait blocks. I won't touch sleep right now.. but come on dude. Once your thread enters a wait condition(on windows/linux 1:1 implementations) it requires the operating system to make it work again, fact. This is what I keep trying to explain to you, but you don't get it.. I don't know what else to say.

And we haven't even discussed bound threads which basically eliminates much of the overhead associated with a context switch (no register swapping, no cache thrashing, etc.) and essentially reduces it to a run flag set call.

Bound threads do not exist in windows or linux because they do not have M:N threading. Where do you get your information? I made a point to complain about those platforms only having 1:1. (Technically all userland threading libraries for windows/linux would contain bounded threads... but as I said earlier.. userland = 1 cpu).

Congratulations! You're either the worlds best programmer by an order of magnitude or arrogant and naive, I'll leave it to you to decide which is more likely.

I'm second tier. I wish I had been able to afford to come to America and go to Berkeley or something.. oh well. Maybe someday...

[Makaze2048]

How in the hell do you plan on starting or dispatching a thread by switching to it?

Scheduling was included in that benchmark actually as the test was comparing a few Linux kernel optimizations and Windows was in there just for comparisons sake, it was not a strict hardware test. Another benchmark I've seen shows waits, the slowest method, eating up only ~1.6 microseconds per call (200,000,000 WaitOnes took ~325 seconds). And that was back on a 2004 processor, it should be down into nanosecond territory these days. Sleeping was about 3x faster...

Kernel mode transitions are slow, 1.6 microseconds is a big chunk of time in processor land. But their cost is a drop in the bucket when compared to real work costs. Each one is only using up 0.00016% of a cores time each second. How many of these threads do you realistically think we're going to be popping off over the course of a second? You severely overestimate thread scheduling costs vs. work costs, and offer no evidence to back up your claim.

I understand to some degree why you feel the way you do. At some point someone told you or you read that context switches, kernel mode transitions, etc. were bad and slow and you took that to heart. It's true in a lot of situations. Networking for example, when you've got a set of sockets receiving a packet from a user every 2ms and 1000 users then you're looking at 500 * 1000 * 0.00016% = 80% of your CPU being used up just in thread costs, clearly unacceptable in this case the overhead is way too costly and a better way should be found.

But when you're talking about a beyond worst case scenario of 200 paths needed EVERY frame at 50 FPS and EVERY one stupidly in it's own thread it's still a far more reasonable 200 * 50 * 0.00016% = 1.6% CPU utilization. But if you can write an algorithm that will calc 10,000 paths faster than that then I withdraw my argument.

What? Lol. A strawman lock is a joke.

Heh It is indeed a joke... one that went way over your head.

Once your thread enters a wait condition(on windows/linux 1:1 implementations) it requires the operating system to make it work again, fact.

No one is arguing against this. The disagreement is about whether the cost of doing that is greater or lesser than the cost of doing a unit (or multiple units) of pathfinding work.

Bound threads do not exist in windows or linux

SetThreadAffinityMask called and would like to have a word...

Now, as to whether this would actually be a good case for that is highly debatable. Depends on how many CPUs you've got, level of background processes, how often pathfinding is going to run, cache amounts vs. required, etc. I suspect that it's probably a slight performance boost on some machines and a drag on others and not worth doing overall.

I'm second tier. I wish I had been able to afford to come to America and go to Berkeley or something.. oh well. Maybe someday...

Being a decent programmer has little to do with higher education. The classes themselves often border on useless and certainly don't contain anything you couldn't learn on your own. The one truly beneficial thing that it does provide you though is an environment with like minded people hard at work and it is through interactions with them that the real learning can happen. But that scenario is far from exclusive to big name American universities.