Coloring usually means the laying out of data such that the data will
not collide in the cache, usually the second (or third) level cache.
Data references are virtual, most caches are physically tagged. That
means that where data lands in the cache is a function of the physical
page address and offset within that page. If the cache is what is called
direct mapped, which means each address has exactly one place it can be
in the cache, then page coloring becomes beneficial. More on that in
a second. Most caches these days are set associative, which means there
are multiple places the same cache line could be. A 2 way set associative
cache means there are 2 places, 4 way means there are 4, and so on. The
trend is that the last big cache before memory is at least 2 way and more
typically 4 way set associative. There is a cost with making it N-way
associative, you have to run all the tag comparitors in parallel or
you have unacceptable performance. With shrinking transistors and high
yields we are currently enjoying, the costs are somewhat reduced.
So what's page coloring? Suppose we have a 10 page address space and
we touch each page. As we touch them, the OS takes a page fault, grabs
a physical page, and makes it part of our address space. The actual
physical addresses of those pages determine where the cache lines
will land in the cache. If the pages are allocated at random, worst
case is that all 10 pages will map to the same location in the cache,
reducing the cache effectiveness by 10x assuming a direct mapped cache,
where there is only one place to go. Page coloring is the careful
allocation of pages such that each virtual page maps to a physical page
which will be at a different location in the cache. Linus doesn't like
it because it adds cost to the page free/page alloc paths, they now have
to go put/get the page from the right bucket. He also says it's pointless
because the caches are becoming enough associative that there is no need
and he's mostly right. Life can really suck on small cache systems that
are direct mapped, as are some embedded systems, but that's life. It's
a tradeoff.
----- Larry McVoy lm at bitmover.com http://www.bitmover.com/lm - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/