[Gllug] code optimisations

[Pete Ryland]

Hi Minty,

On Sun, Mar 20, 2005 at 12:04:26PM +0000, Minty wrote:
> 
> I had a coursework due that basically involved taking an existing
> chunk of C code and making it run as fast as possible on a platform of
> my choice.
> 
> *** approach **********
> 
> - First look at generic compiler optimisations
> - Then use gprof, identify key chunks of code to optimise.
> - Then (may be) tinker with the code

I would have thought this to be totally the wrong way around.

Your two biggest (and most cost-effective) optimisations will be:

1. Algorithm efficiency
2. Cache efficiency

By algorithm efficiency, I mean overall top-level effiency, not tweaking
small things (the compiler should deal with the small tweaks).

And by Cache efficiency, I mean things like organising memory usage to be
more sequencial if possible, e.g.:

for (i=0; i<1000000; i++)
  for (j=1; j<10000000; j++)
    a[i][j]++;

is *significantly* faster than:

for (j=1; j<10000000; j++)
  for (i=0; i<1000000; i++)
    a[i][j]++;

I don't think a compiler would optimise that type of thing.

There may be many small tweaks like moving constant things out of loops, but
these will not likely have as great an impact.

Basically, if you have a single function that is taking all the CPU time,
then instead of asking "how do I make that function more efficient?" you
should first ask "how do I make it call that function less often?" or if
it's memory-intensive "can I rearrange callings of this function to make
better use of the cache?".

My 2p,
Pete
-- 
Gllug mailing list  -  Gllug at gllug.org.uk
http://lists.gllug.org.uk/mailman/listinfo/gllug