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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Wed, Jun 26, 2002 at 04:27:33PM +0100, Gregory Berkolaiko wrote:
> 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.

Is it called with TM_NONE or with another value?

> 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.

Just treat the x and y values as two 16 bit values and pack them into
a 32 bit value.

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

Server, client and (not included yet) agents.

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

But I need an implementation for the agents.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  (On the statement print "42 monkeys"+"1 snake"): BTW, both perl and Python
  get this wrong. Perl gives 43 and Python gives "42 monkeys1 snake", when 
  the answer is clearly "41 monkeys and 1 fat snake".  
    -- Jim Fulton, 10 Aug 1999