Well, here is my comment on pathfinding . Its almost impossiable to benchmark using the standard methods. Sure you can do it, but then you run into the problem that on a slower system it runs like shit compared to your super box! Instead look at the number of instructions and stack depth required to perform a path calculation that is at least 1000 movements long. Now if you take that against your typical bsp search (0.25n if I remember properly) calculation of 250 and consider that you will still have to calculate a depth first search (500) and you come up with it taking 750 stages in an ideal search.

Now, to give you an idea, the path finding algo I pointed you at will perform as follows:
1st itteration it will take 1250 average steps to locate the path (not to ungodly bad, but not good)
2nd itteration (along all known and found on the inital) will result in 2 steps (ungodly in terms of speed).
2nd itteration with a new path that crosses an existing and known will result is average 250 (very good).

Reading over my own post it looks and sounds very confusing, but I hope you can gleam something out of it.