Skip to contentSkip to conversation

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

DISCUSSION Anton Ertl 2 participants 2 messages Dec 26, 2003 1 message not in the archive

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

Anton Ertl

author
#1 lore raw
Quoted 6 lines · Linus Torvalds

And the thing is, using huge pages will mean that the pages are 1:1 mapped, and thus get "perfectly" cache-coloured, while the anonymous mmap will give you random placement.

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

Quoted 6 lines

In particular, using a pure power-of-two stride means that you are limiting your cache to a certain subset of the full result with the perfect coloring.

This, btw, is why I don't like page coloring: it does give nicely reproducible results, but it does not necessarily improve performance.

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.

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.

I.e., it is more frequent that you access stuff spatially close to a recent access (where page colouring has a 0 chance of conflicting, whereas random mapping has a non-zero chance of conflicting), than to access stuff that is exactly a multiple of the cache-size away (which is the worst case for page colouring). Fortunately, set-associative caches in the machines I use most of the time reduce the impact of the missing page colouring in Linux.

The most frequent case where random mapping gives better performance than page colouring is having several sequential passes over a block that is larger than the cache; but that's just a case where caches perform badly on principle, and cache designs that are usually considered better (higher associativity, LRU replacement) perform worse in this case.

OTOH, for cases where the block does barely fits in the cache, page colouring performs quite a bit better. This particular access pattern can be more frequent than one might expect from other statistics, due to software optimizations like cache blocking.

One additional mechanism in which page colouring can help performance is by providing a predictable and understandable performance model to programmers. Caches are bad enough to analyse, one need not complicate the issue with unpredictable effects of random virtual-to-physical translation.

- anton

Signature · 3 lines
M. Anton Ertl                    Some things have to be seen to be believed
[email protected] Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html
#2 lore raw
Quoted 7 lines · Anton Ertl
Quoted 3 lines · Linus Torvalds

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.

Quoted 3 lines

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.

Quoted 3 lines

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.

Quoted 3 lines

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