Messages in this thread | | | Date | Fri, 26 Dec 2003 15:28:04 -0800 (PST) | From | Linus Torvalds <> | Subject | Re: Page Colouring (was: 2.6.0 Huge pages not working as expected) |
| |
On Fri, 26 Dec 2003, Anton Ertl wrote: > Linus Torvalds <torvalds@osdl.org> 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@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |