Print

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

[SmileyMan]

Simply putting the pathfinding code in another thread wouldn't solve the problem - your main thread would be blocking waiting for the pathfinder to return, unless your main game thread is also coded to know that the pathfinder will now return results asynchronously, and with the number of objects in DF that could very well cause memory issues.

[Geltor]

Simply putting the pathfinding code in another thread wouldn't solve the problem - your main thread would be blocking waiting for the pathfinder to return, unless your main game thread is also coded to know that the pathfinder will now return results asynchronously, and with the number of objects in DF that could very well cause memory issues.

ah, but you are wrong! (hopefully  ).
our goal is to speed up fraterate, and what hinders us is the pathfinding calculation. we only need to put the calculation itself on a different thread and wait for the output to the main thread. yes, you need to wait for an answer, but does that mean pausing the entire main thread? no, i say. just the individual dwarf. the only result, from my understanding so far in my vision, would be the dwarf pausing for 1-2 seconds (even less i dare say) before the calculation for his path is returned, and then he proceeds on his marry way in the main thread.

this all assumes, of course, the calculation is based on a predefined path, and not a constantly on-the-go recheck, which would be wasteful and i dont see any point to anyway.

regardless, what kind of memory issues do you foresee? i dont really see an issue with that yet

[SmileyMan]

ah, but you are wrong! (hopefully  ).

After 20 years as a commercial programmer, the only thing I am certain of is my own uncertainty

our goal is to speed up fraterate, and what hinders us is the pathfinding calculation. we only need to put the calculation itself on a different thread and wait for the output to the main thread. yes, you need to wait for an answer, but does that mean pausing the entire main thread? no, i say. just the individual dwarf. the only result, from my understanding so far in my vision, would be the dwarf pausing for 1-2 seconds (even less i dare say) before the calculation for his path is returned, and then he proceeds on his marry way in the main thread.

Here's the pseudocode for the current behaviour:

Code: [Select]

do_non_path_stuff()
if (dwarf_needs_path) {
  get_path (this_dwarf)
}
do_pathed_stuff()
Here's the pseudocode for a simple bit of multithreading (as per your suggestion):

Code: [Select]

if (dwarf_needs_path) {
  lock = call_get_path (this_dwarf)
}
do_non_pathed_stuff()
lock.wait_until_complete()
do_pathed_stuff()
If the code which doesn't need a path takes about as long as the pathfinding, then this is an excellent technique - it should deliver a 50% time saving. That seems a) unlikely to be true in most cases and b) given the premise that pathfinding is the big bottleneck then decidedly suboptimal

The way to really multithread would be as follows:

Code: [Select]

start_pathfinder_threads()
for_all_dwarfs {
  if (dwarf_needs_path) {
    put_in_pathfinding_queue(current_dwarf)
  }
}
for_all_dwarfs {
  do_non_path_stuff()
}
for_all_dwarfs {
  get_path_from_pathfinding_queue(current_dwarf)
  do_pathed_stuff()
}
You can (hopefully!) see that you're introducing a whole load of complexity that would be especially hard to put into old code and an absolute monster to debug.

[Geltor]

that is not how i intended to implement multithreaded pathfinding!

Code: [Select]

thread 1 - game main loop
dwarf.getPath(destination,dwarf) - adds this dwarf to a path waiting list ON THREAD 2!
dwarf.pause() - THIS SPECIFIC DWARF] waits for a return path parameter - (could be a string of directions? i dont know how df handles this)

thread 2  - can honestly split this into many threads - THIS IS ALWAYS RUNNING
for each pathList index{
  calculatePath(pathList[index].dwarf,pathList[index].destination)
  dwarf[pathList[index].dwarf].handle()  - sends the result, either removing the dwarf from the pathlist, sending error that path unreachable, or returning values that determine the steps he has to take to get to his destination
}

now from where im standing i see that theres one, BIG, issue that i got wrong according to your answers - DF handles pathing differently than what i imagined ... if that is the case, my entire point is moot 

HOWEVER, if this is feasible, the only slowdown youll experience (on the premise of pathing bottlenecking of course) is a slower response time from INDIVIDUAL DWARVES, they should be darting around at 100fps otherwise...

[SmileyMan]

In that, you're just executing a single execution path on two threads, so you'll gain absolutely nothing. One thread will always be paused while the other is active and vice versa. Until you start introducing some synchronisation structures, the only gain you might get is some improved efficiency in memory usage.

[Geltor]

In that, you're just executing a single execution path on two threads, so you'll gain absolutely nothing. One thread will always be paused while the other is active and vice versa. Until you start introducing some synchronisation structures, the only gain you might get is some improved efficiency in memory usage.

i am pausing the dwarf, not the thread!! i put some more effort into my pseudocode to make it more clear

[Lightman]

No one on this thread knows how DF is written and what would be the easiest (or best) optimisations for it.  Spending your time writing pseudo-code and making vague guesses at its internals probably isn't the best use of your time.

The topic here is hardware performance.  In my humble opinion, it would be more helpful to work on a test suite.  By 'test suite', I mean working out a way to collect some reasonably reliable performance data across different systems.  Maybe a Linux USB image that boots into DF and has a saved fortress ready to go, with a background script to collect FPS?

You could always log some good bugs, too

[Thief^]

In that, you're just executing a single execution path on two threads, so you'll gain absolutely nothing. One thread will always be paused while the other is active and vice versa. Until you start introducing some synchronisation structures, the only gain you might get is some improved efficiency in memory usage.

i am pausing the dwarf, not the thread!! i put some more effort into my pseudocode to make it more clear

Most languages don't work that way, and definitely not C/C++ (which dwarf fortress is written in). Everything (on one thread) happens one thing after another. If you pause you pause everything on that thread.

What you would need to do is what SmileyMan wrote.

(I'm a professional game developer, trust me that I know my shit here)

[Livingdeath]

I wonder how feasible it would be to run the external world stuff on a seperate thread.  The timing checks don't have to be super precise, or at least it doesnt seem to me to be so critical, so there is a certain amount of leeway that might be possible.

I do think Toady has a pretty big scaleability problem going on with his game right now.  As he keeps adding cool things his fps has been steadily dropping, which means we have to resort to mods and reducing our embark site size and/or number of dwarves.

Meanwhile modern CPUs are not giving him any performance gains (my 5 year old laptop runs the game almost as well as my top of the line desktop).  This will have to be addressed pretty soon.

[Geltor]

In that, you're just executing a single execution path on two threads, so you'll gain absolutely nothing. One thread will always be paused while the other is active and vice versa. Until you start introducing some synchronisation structures, the only gain you might get is some improved efficiency in memory usage.

i am pausing the dwarf, not the thread!! i put some more effort into my pseudocode to make it more clear

Most languages don't work that way, and definitely not C/C++ (which dwarf fortress is written in). Everything (on one thread) happens one thing after another. If you pause you pause everything on that thread.

What you would need to do is what SmileyMan wrote.

(I'm a professional game developer, trust me that I know my shit here)

jesus christ.. please read my post again. have i said i am pausing the thread..? you sound very condescending

No one on this thread knows how DF is written and what would be the easiest (or best) optimisations for it.  Spending your time writing pseudo-code and making vague guesses at its internals probably isn't the best use of your time.

no argument there..but cant a guy dream?

[Thief^]

jesus christ.. please read my post again. have i said i am pausing the thread..? you sound very condescending

I am being condescending

More seriously, you can't pause just one object/function/dwarf. There's no such function in C. There is a proposal adding "resumable functions" to C++17 (2017), which would be able to do something like this, but nothing currently. It would also prevent the dwarf from doing anything else (at all!) while he waited for a new path.

No, what you really want is for the dwarf to not be paused, but for his code to be written with the understanding that he may not have a path or may have an outdated path, with code being able to choose to either use the outdated path (may cause him to walk towards a locked door for a few frames, for example) or stand still (flashing a "thinking" question mark icon?).

Alternatively the pathfinder could be replaced with one which finds a partial path, rather than a full one, which is *much* faster. This would result in dwarfs getting lost if there's no direct path between two areas, but that's probably quite realistic!

[Geltor]

jesus christ.. please read my post again. have i said i am pausing the thread..? you sound very condescending

I am being condescending

More seriously, you can't pause just one object/function/dwarf. There's no such function in C.

im sorry for my poor choice of words then. replace "pause" with "skip", that is what i mean essentially: to NOT process a dwarf waiting for a path, as such:

Code: [Select]

for_all_dwarves{
  if(!dwarf.waiting_for_answer AKA PAUSED  >:(){
     process_dwarf   - an unprocessed dwarf just waits. environmental things still apply to him (hunger, death,etc) but this is irrelevant since he wont be waiting for more than a second even at 200+ dwarves
  }
}
imagine my frustration when i read your post. "WHY THE HELL CANT YOU DO THAT IN C?"

[miauw62]

so if a dwarf is pathing he does not get hungry, sleepy, bleed, etc?

[Geltor]

so if a dwarf is pathing he does not get hungry, sleepy, bleed, etc?

it would still apply, the only thing it does is dump the time it takes to come up with a path onto another thread, and that time is translated into that specific dwarf literally waiting (hence the "paused") for an answer. its not like hes frozen in time

[Thief^]

And nobody has yet got a solution for how to compute paths on another thread in a world which changes at the slightest action... Except for cloning the entire world, which may be a tad too slow to do every frame.