[rescue] Re: Re: OH YEA??? [was: Re: Ultra?]

[Francisco Javier Mesa-Martinez]

On Mon, 5 Aug 2002, Joshua D Boyd wrote:

> On Mon, Aug 05, 2002 at 02:00:47PM -0400, Dave McGuire wrote:
> >   Just as a side note, in my experience the worst cache-friendliness
> > offenders have been arrays whose sizes are even numbers, or even
> > worse, powers of two.  This is a very common programming practice that
> > blows most caches out of the water.  Many programmers "think" in terms
> > of powers of two, so instead of a 100-element array they'd make it 128
> > elements, when it should probably be something like 97 or 101.
> > Another big one is highly randomized array access.
> 
> Could you give a brief overview on why even numbers of elements are
> bad here?  If all I need is 100 elements, why would 101 be better?


This may be a function of the stride size to cache line ratio, depending
on how you access the array. Also people forget to take the TLB
performance into account when dealing with caching.... (i.e. is the cache
physically or virtually address, it makes a HUGHE difference)

I.e. sometimes is more important to know HOW you are indexing the array,
that how large the array is. This is very important to know, when trying
to map a specific code to a well known memory hierarchy.

i.e.  for (i=1; i<100; i++)
	for (j=1; j<100; j++)
	  a[i][j] = a[i][j]++;

will behave completely differently than...

	for the same loop with:
	   a[j][i] = a[j][i]++;

(you can also try the same by inverting the former for loops... etc.)

....using the same machine/memory hierarchy.

Also most people fail to note that TLB misses also affect the performance
as much as cache misses (actually they are more costly).