Re: Page Colouring (was: 2.6.0 Huge pages not working as expected)

[Linus Torvalds]

On Fri, 26 Dec 2003, Anton Ertl wrote:
> Linus Torvalds <torvalds@xxxxxxxx> writes:
> >
> >And what you are seeing is likely the fact that random placement is 
> >guaranteed to not have any worst-case behaviour.
> 
> You probably just put the "not" in the wrong place, but just in case
> you meant it: Random replacement does not give such a guarantee.

No, I meant what I said.

Random placement is the _only_ algorithm guaranteed to have no 
pathological worst-case behaviour.

>							  You
> can get the same worst-case behaviour as with page colouring, since
> you can get the same mapping.  It's just unlikely.

"pathological worst-case" is something that is repeatable. For example, 
the test-case above is a pathological worst-case schenario for a 
direct-mapped cache. 

> Well, even if, on average, it has no performance impact,
> reproducibility is a good reason to like it.  Is it good enough to
> implement it?  I'll leave that to you.

Well, since random (or, more accurately in this case, "pseudo-random") has 
a number of things going for it, and is a lot faster and cheaper to 
implement, I don't see the point of cache coloring.

That's doubly true since any competent CPU will have at least four-way 
associativity these days.

> However, the main question I want to look at here is: Does it improve
> performance, on average?  I think it does, because of spatial
> locality.

Hey, the discussion in this case showed how it _deproves_ performance (at 
least if my theory was correct - and it should be easily testable and I 
bet it is).

Also, the work has been done to test things, and cache coloring definitely
makes performance _worse_. It does so exactly because it artifically
limits your page choices, causing problems at multiple levels (not just at
the cache, like this example, but also in page allocators and freeing).

So basically, cache coloring results in:
 - some nice benchmarks (mainly the kind that walk memory very 
   predictably, notably FP kernels)
 - mostly worse performance in "real life"
 - more complex code
 - much worse memory pressure

My strong opinion is that it is worthless except possibly as a performance
tuning tool, but even there the repeatability is a false advantage: if you
do performance tuning using cache coloring, there is nothing that
guarantees that your tuning was _correct_ for the real world case.

In short, you may be doing your performance tuning such that it tunes for
or against one of the (known) pathological cases of the layout, nothing
more.

But hey, some people disagree with me. That's their right. It's not 
unconstitutional to be wrong ;)

			Linus
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/