Jump to content

Question on pathfinding call graph


Recommended Posts

In a small callgrind run, I've seen that the fixed point integer square root function consumes quite some time in path computation. The attachments show three cases of CCmpPathfinder_Tile::ComputePath recorded through a CALLGRIND_START_INSTRUMENTATION and CALLGRIND_STOP_INSTRUMENTATION in the function itself (otherwise valgrind was too slow for me to use).

Has the isqrt64 been benchmarked against the "normal" lm function? I don't have much time, but some initial tests seem to suggest that a casted sqrt is faster than the custom function in my case, even when casting from u32 to double and back. Or do I miss some other reason for this function?

And out of curiosity, is the CProfiler2 stuff visible in two of the graphs required for some kind of runtime performance adaptation?

The callgrind run is from saturday mornings SVN iirc, in case something was changed recently.

post-15059-0-93088300-1355158813_thumb.p

post-15059-0-54308100-1355158815_thumb.p

post-15059-0-80478100-1355158816_thumb.p

Link to post
Share on other sites

If the sqrt is being used to compute distance, it may be an acceptable approximation to get rid of it completely.

There's a built-in profiler, accessible with F11 in-game. I never thought to check.. but please don't tell me it's running always, even in the Release builds!?

Link to post
Share on other sites

And out of curiosity, is the CProfiler2 stuff visible in two of the graphs required for some kind of runtime performance adaptation?

Looks here (and in the following posts) for information about the profiler:

http://www.wildfiregames.com/forum/index.php?showtopic=15270&st=20#entry228237

At the moment the html output seems to be broken somehow (it doesn't output anything) but I'm trying to fix it.

Link to post
Share on other sites

Has the isqrt64 been benchmarked against the "normal" lm function? I don't have much time, but some initial tests seem to suggest that a casted sqrt is faster than the custom function in my case, even when casting from u32 to double and back. Or do I miss some other reason for this function?

Floating point arithmetic isn't safe in the simulation code due to hardware and compiler differences, it must produce identical results for each player in a multiplayer game.

Link to post
Share on other sites

If the sqrt is being used to compute distance, it may be an acceptable approximation to get rid of it completely.

Yes, but an approximation should be faster, not slower.

There's a built-in profiler, accessible with F11 in-game. I never thought to check.. but please don't tell me it's running always, even in the Release builds!?

This is not it I think. There seem to be different generations of profilers.

Floating point arithmetic isn't safe in the simulation code due to hardware and compiler differences, it must produce identical results for each player in a multiplayer game.

Ok, thanks for the hint. I'll have to think about this.

Link to post
Share on other sites

You so clever. Look up Manhattan distance.

I was not trying to be clever. I don't know why you start getting like that. I was stating a simple fact. Why would you use an approximation if you're slower? Makes no sense.

And I know fully well what the manhattan distance is. It is not an approximation, that is for sure.

Link to post
Share on other sites

One of the profilers is always running.

Nothing in inherently an approximation by itself, an approximation is required to have an associated exact version which it is approximating. So the manhattan distance can certainly be an approximation for the euclidean distance (quite a bad one since it can be 41% out), an equivalent of the manhatten distance which allows diagonal moves as well (8 possible directions) is perhaps a better sped/accuracy tradeoff.

Since in theory the pathfinder should be getting a complete rewrite spending too much effort on the current one does not seem worthwhile.

Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...