Re: [Freeciv-Dev] Some performance issues

[Rizos Sakellariou <rizos@xxxxxxxxxxx>]

> 
> 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. [*]

Another possible problem with a static max_size array is that
it may increase the likelihood of cache misses who are also
expensive and painful to estimate. I would set for the lookup
array option as the most cost-effective solution and easier
to implement.

--rizos