Re: [Freeciv-Dev] Some performance issues

[Mitch Davis <mjd@xxxxxxxxxx>]

David Pfitzner wrote:
> 
> Mitch Davis wrote:
> > Rizos Sakellariou wrote:
> 
> > >  As a solution,
> > > i suggest to replace all occurrences of y*map.xsize with something like
> > > an array ymult[y] whose elements (from 0 to map.ysize) are precomputed
> > > at the beginning of each game.
> >
> > Having a lookup table is a good idea.  We could either have a
> > table with a well-known name, or a function to do a lookup.  On
> > compilers such as gcc, the function could be made inline.
> >
> > Hmm, the table sounds neater...
> 
> If we wanted to optimise for speed at the expense of some
> memory, we could make map.tiles a static 2-d array with the
> maximum map sizes.  Presumably that would help optimisation.
> (Probably talking around up to 100k memory waste, is my
> guestimate, depending on the actual map size.)
> 
> Or otherwise a table should be ok.  I think it should be
> possible to have this stuff all localised within common/map.c

Usually, the calculation is of the form y*map.xsize + x.  It's
not the + that's expensive, it's the *.  So it's not necesary to
have a table of the whole map; just the y offsets will be enough.
And this would be significantly smaller than 100k.

One other problem with a 2D array:  With a 1D array, the compiler
can emit code which uses a register as an index into the array.
But with the 2D array, the compiler may emit a hidden
multiplication to get the array offset, and we're
back to square one. [*]

Regards,

Mitch.

[*] Making our own "virtual 2D" array with dynamically allocated
memory and pointers may not require the multiply, but will be
complicated.
--
| mailto:mjd@xxxxxxxxxx       | Not the official view of: |
| mailto:mjd@xxxxxxxxxxxxxxxx | Australian Calculator Opn |
| Certified Linux Evangelist! | Hewlett Packard Australia |