Re: "Colo[u]rs"

[Stevie O]

At 02:26 AM 12/10/2001 -0500, Robert Love wrote:
>Cache color is how many indexes there are into a cache.  Caches
>typically aren't direct mapped: they are indexed into cache lines by a
>hash.  This means that certain memory values (of the 2^32 on your PC)
>will map to the same cache line.  This means only one can be there at
>the same time, and the newer one throws the old one out.
>
>Coloring of data structures is down to give random offsets to data such
>that they are not are multiples of the some value and thus don't map to
>the same cache line.  This is what Linux's slab allocator is meant to
>do.

(I'm not too familiar with how this caching stuff works, so if anyone could 
give me a URL describing it to a relative newbie, i'd be quite grateful)

So lemme see if I got this straight from what you and Larry have told me:

For the direct map deal:

For every byte (probably page?) in the CPU's cache, say byte(page) 0x31337 
can be used to cache the bytes(pages) at:
0x00031337, 0x00131337, 0x00231337, ... 0xfff31337

So, if a program ran, and happened to have its pages #0-4095 mapped to 
physical pages:
0x00031337, 0x00131337, 0x00231337, ... 0xfff31337

and the program went through an array and accessed each of those pages in 
sequence, every successive iteration would have to replace the previous 
page in the cache with the new one; i.e. exactly one of those pages would 
be in cache at any given time. Which would obviously make the program's 
performance suck majorly.

For the n-way associative deal:

Don't quite get it enough to make an example yet ;)

--
Stevie-O

Real programmers use COPY CON PROGRAM.EXE