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

[Dave McGuire]

On August 5, Joshua D Boyd 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?

  I described array sizes when I meant array ELEMENT sizes...(I just
woke up, still half asleep).  Envisioning the way a data cache works,
it's pretty obvious that unit-stride memory references will generally
provide the best hit rates.  You access a memory location, a cache
miss occurs, a cache line gets loaded from main memory, and then every
access in that cache line becomes a hit.  But with larger data
structures that line up integrally with cache lines, if you index
around that array skipping elements, it's possible to invalidate cache
lines on every access.  Odd-sized array elements can increase the
chances of cache hits because the worst case "full alignment" (for
lack of a better term) between non-unit-stride memory references and
cache lines can't happen.

  It could be argued that a particular compiler may enforce alignment
constraints for certain processors, causing things to be aligned on
even numbered addresses anyway...but since most data alignment occurs
on boundaries a good bit smaller than cache line sizes, this still
works.

  And for even larger structures, the TLB misses incurred can be another
significant performance penalty.

  Anyway, sorry for my verbosity, I'm having a kinda "off day" mentally
and have explained it in the best way I can.  Definitely grab the book
I mentioned in my last message; it explains all this stuff much more
clearly than I can.

          -Dave

-- 
Dave McGuire                     "I haven't worn pants in 14 months!"
St. Petersburg, FL                                   -Pete Wargo