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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Tue, Jun 25, 2002 at 07:43:27PM +0100, Gregory Berkolaiko wrote:
> On Mon, 24 Jun 2002, Raimar Falke wrote:
> 
> > On Sun, Jun 23, 2002 at 10:43:27PM +0100, Gregory Berkolaiko wrote:
> > > I experimented a bit with the lattice management model in my path finding 
> > > implementation.
> > > 
> > > notation: lattice = map = 2D array of nodes,
> > > node = location = position contains data about costs of getting to it etc.
> > 
> > Looks familiar ;)
> 
> You see my terminology changes from paragraph to paragraph ;)
> 
> > > I used 3 methods:
> > > 
> > > 1. allocate the whole lattice at once and fill (a potentially 
> > > small part in).
> > > 
> > > 2. allocate each node of the map as I reach it.  there is however a 
> > > preallocated array of pointers to the nodes
> > > 
> > > 3. fully dynamic allocation: the nodes are allocated as they are reached 
> > > and are stored in a hash table (mostly copied from Raimar's 
> > > implementation, introduced a few bugs, corrected them, in working order 
> > > now it seems). 
> > > 
> > > Then I made 1000 repeats of making full maps for about 6 units.
> > > The results (in secs, using clock()/CLOCKS_PER_SEC), averaged over 3 or 
> > > more tries:
> > > 
> > > 1:  9.6
> > > 2:  11.84
> > > 3:  21.89
> > > 
> > > Also the original generate_warmap:
> > > 
> > > 2.73
> > > 
> > > There is some optimization that could be done to the code, but it won't 
> > > reduce the time 4-fold.
> > > 
> > > Draw your own conclusions, I'm too tired and hungry today.
> > 
> > Can you make a test like 1. but with static allocation? This would be
> > similar to the current code.
> 
> Yes I can.  No it won't.
> 
> In actual fact the comparison to the current code is not good as the new 
> code is designed to do more and will therefore eat more.

The test was to measure how much overhead the new allocation
requires. The static allocation conflict with the new interface.

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

> Also, I run more tests, the results vary from compilation to compilation, 
> but they stabilize eventually.  It seems that the results I gave in the 
> first email were from compilations with different flags.  The refined 
> figures are:
> 
> 0. Static lattice:  11.0
> 1. Lattice allocated in one chunk: 11.4
> 2. Lattice allocated in one chunk only contains pointers
>      to cells allocated as we progress: 15.7
> 4. Cells allocated as we progress and stored in hash: 21.7
> 
> The above comparison is fair: only the parts of the code corresponding to
> the lattice allocation were changed.  Additional improvement might be done
> through static allocation of the queue structure (frontier in Raimars
> code), inlining cost functions etc.

> My conclusion: the lattice should be preallocated, but not static.
> Static lattice brings a slight improvement in speed and significant 
> reduction in usability.  And you still have to initialize lattice every 
> time.

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

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Any sufficiently advanced technology is indistinguishable from magic."
    -- Arthur C. Clarke