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

["Ross W. Wetmore" <rwetmore@xxxxxxxxxxxx>]

At 10:09 PM 02/07/01 +0200, Raimar Falke wrote:
[...]
>> Again this shows that if you leave the index computations to the 
>> compiler/optimizer and don't do known bad things that destroy its
>> effectiveness, it will find the best solution in a given context.
>> 
>> Indexed (linearized) arrays are just as effective as static unless
>> you introduce type differences in the index/bounds values that
>> defeat optimization.
>
>Ok and another time. Repeat please: the variable map of type struct
>civ_map is a global one. The compiler have to assume that the value
>has changed for every call of a function foo.

Ok, to repeat one last time ...

If you know that the loop limit/array bounds values are not going to
change, then you should store them into local variables before entering
the loop, and access the local variables. 

If you *insist* on doing things in ways that defeat optimizations, then
also do this for your precomputed array so that it needs to be accessed
rather than cached in the inner loop as well.

The effect is now to move the leal (computation) and movl (lookup) 
operations into the inner loop and kill performance in comparable ways.

If you make a "fair" comparison, then the (computed) index will almost 
always win as the memory access is far more damaging than the computation. 
This should be obvious from the example, even if you want to dispute the
environmental conditions in general cases.

The memory access also causes cache line flushes and cache capacity issues
that internal or local variable register/stack values don't.

>Also note that the user of this code isn't a tight loop but something
>like this:
>
>bool pf_get_next_location(pf_map_t pf_map, pf_location_t * location)
>{
>...
>  adjc_dir_iterate(current_cell->pos.x, current_cell->pos.y, x1, y1, dir) {
>    struct cell tmp, *possible_neighbour = &tmp, *neighbour;
>    int extra_cost2;
>...
>    neighbour = &pf_map->cells[x1][y1];
>
>The last line is the only time the cells array is accessed except in
>built-up and tear down. The compiler can do clever things in tight
>loops but not in one like this. 

Actually it can ... as long as you don't actively seek to defeat it.

>Well except if you can change the way
>the map is stored and so adjc_dir_iterate becomes a simply loop.

The code to optimize adjacent iterations has been around for a year now.
It doesn't involve any changes to the map storage.

>       Raimar
>-- 

Once you get past the performance aspects, there are still the bad coding 
practice issues from using an array of refernces to simulate a doubly 
indexed array.

Cheers,
RossW
=====