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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

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

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.

Best wishes,
G.