Re: [PATCH] rmap 14

From: Daniel Phillips (
Date: Mon Aug 19 2002 - 13:04:29 EST

On Friday 16 August 2002 23:29, Scott Kaplan wrote:
> > Now... where this is going. I plan to write a module that will generate
> > page references to a given pattern. Possible pattern references are
> >
> > o Linear
> > o Pure random
> > o Random with gaussian distribution
> > o Smooth so the references look like a curve
> > o Trace data taken from a "real" application or database
> Noooooooooo!
> I can't think of a reason to test the VM under any one of the first three
> distributions. I've never, *ever* seen or heard of a linear or gaussian
> distribution of page references. As for uniform random (which is what I
> assume you mean by ``pure random''), that's not worth testing. If a
> workload presents a pure random reference pattern, any on-line policy is
> screwed. No process can do this on a data set that doesn't fit in memory,
> and if it does, there's no hope.

I disagree that the linear (which I assume means walk linearly through
process memory) and random patterns aren't worth testing. The former should
produce very understandable behaviour and that's always a good thing. It's
an idiot check. Specifically, with the algorithms we're using, we expect the
first-touched pages to be chosen for eviction. It's worth verifying that
this works as expected.

Random gives us a nice baseline against which to evaluate our performance on
more typical, localized loads. That is, we need to know we're doing better
than random, and it's very nice to know by how much.

The gaussian distribution is also interesting because it gives a simplistic
notion of virtual address locality. We are supposed to be able to predict
likelihood of future uses based on historical access patterns, the question
is: do we? Comparing the random distribution to gaussian, we ought to see
somewhat fewer evictions on the gaussian distribution. (I'll bet right now
that we completely fail that test, because we just do not examine the
referenced bits frequently enough to recover any signal from the noise.)

I'll leave the more complex patterns to you and Mel, but these simple
patterns are particularly interesting to me. Not as a target for
optimization, but more to verify that basic mechanisms are working as

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

This archive was generated by hypermail 2b29 : Fri Aug 23 2002 - 22:00:17 EST