Question on pathfinding call graph

[scroogie]

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.

[myconid]

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!?

[Yves]

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.

[historic_bruno]

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.

[scroogie]

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.

[myconid]

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

You so clever. Look up Manhattan distance.

[scroogie]

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.

[quantumstate]

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.

[scroogie]

I see, thanks for the info! As I said, I was just wondering about the integer square root.

[historic_bruno]

I see, thanks for the info! As I said, I was just wondering about the integer square root.

For what it's worth, the new pathfinder may avoid that entirely. See the work-in-progress very old patch here.