[Freeciv-Dev] Re: (PR#6182) remove some static map-sized arrays

["rwetmore@xxxxxxxxxxxx" <rwetmore@xxxxxxxxxxxx>]

There is absolutely no difference in optimized code between an
array and a linear implementation - provided you make sure the
"variable" used in multiplication is "constant" for the code
block in question. Loading it into a local variable that is not
further updated in the loop/block, or making the global struct
elements const usually suffices to satisfy these conditions.
These are relatively trivial fixes.

This is where Raimar made all his mistakes in testing - he did
not compare apples with apples. In counter examples provided,
where this was done, the assembly code was usually identical,
which strongly implies no execution difference :-).


The case where indices are precomputed and cached turns out to be
not only more complex codewise, but more expensive under these
conditions. Thus the memory lookup of cached values is far worse
than the single indexed instructions used for array access, that
are used either with static arrays, or optimized indexed macros.

When you start to see sequences with imul rather than fast lea
instructions, this can be reversed, but generally this is a sign
that the code is more complex than it needs to be, and not being
fully optimized, or the variables are not properly localized,
again bypassing the compiler optimizations.

Memory lookups are *very* slow vs computation in most cases and
cause a lot of pipeline rearrangements that usually result in
slower sequences.


This is a case where one should go with the chip and compiler
makers that have spent a lot of time and effort improving array
accesses (either linear or double indexed) and not clutter code
with complex attempts to repeat this function. Learn what one
needs to do to *not* break the optimizations and modify the code
in minmal ways to follow the rules they have set.

Cheers,
RossW
=====


Raimar Falke wrote:

 > On Thu, Sep 18, 2003 at 09:15:10AM -0400, Jason Short wrote:
 >
 >> Gregory Berkolaiko wrote:
 >>
 >>> On Thu, 18 Sep 2003, Bursig Rafal wrote:
 >>>
 >>>> Sorry this msg was rejected by RT then I sent it to list
 >>>
 >>> I remember there was a big discussion on this with Ross and Raimar very
active participants.  IIRC there was no verdict as there were argument both for
and against using array[x][y] vs array[x * size + y]
 >>
 >> I prefer the array[x][y] form.  Except that it breaks under gen-topologies
and consumes more memory.
 >
 > The difference is a multiplication with a non-constant vs a memory
 > access. Which one is faster depends heavily on your architecture. The
 > determining thing is what Jason mentions above: gen-topologies needs
 > the 1D array.
 >
 >     Raimar