[Freeciv-Dev] Re: [RFC] Path finding implementation.

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Tue, 25 Jun 2002, Raimar Falke wrote:

> > I didn't expect it to eat _so_ much more, but I knew it is not going
> > to be faster.  So the comparison with the current code serves one
> > purpose: to show that it shouldn't be just thrown away, it should be
> > kept for the tasks which do not require fancy and flexible solutions
> > provided by the new code.
> 
> So the question is which features of the new interface/implementation
> require more time?! The callbacks? The memory allocation (we
> eliminated this)? The turn calculations? Others?
> 
> What does a profile of a test run without inlining show? Which
> functions are at the top? Queue management, movement test, movement
> cost calculation, callbacks, ...?

I'll send you the whole profile, but here is the most important bit with 
my comments:

-----------------------------------------------
                4.91    8.77 3212784/3212784     time_path_finding [1]
[3]     58.5    4.91    8.77 3212784         pf_iterate_map [3]
                4.21    0.00 3212784/3212784     pf_get_from_queue [4]
                1.42    0.00 7798194/7798194     adjust_cost [8]
                1.02    0.00 12257730/12257730     normal_move_unit [10]
                0.62    0.00 25702272/25726248     get_xy_from_x_and_y [13]
                0.51    0.00 12257730/12257730     server_get_known [14]
                0.51    0.00 3188808/3188808     pf_add_to_queue [15]
                0.34    0.00 3188808/3188808     get_x_from_xy [16]
                0.14    0.00 3188808/3188808     get_y_from_xy [19]

get_from_queue is quite a surprise to me.
I'll look into it.

adjust_cost is also quite surprising -- it changes the cost according to 
the Turn Mode.  It should be inlined.

normal_move_unit is the move_cost callback
server_get_known is is_known callback

get_*_from_* are (x,y) <-> xy converters.  They can be optimized by 
setting MAX_[XY]SIZE to a power of 2.

> Ack.
> 
> In general: if the new implementation is 4 times slower than the
> current and the goto code uses 20% (this is backed up with profile
> data) of the total runtime. This would make the runtime of the server
> 60% longer in total. Not nice but we could remove 2 of the 3 goto
> implementations and improve the quality for the existing users (think
> trireme).

What do you mean by 3 existing implementations?
Clinet-side, warmap and find_the_shortest_path?

I am not so eager to replace warmap completely.  It can still be trusted 
with some dumb cases where any reasonable approximation will do.

G.