Re: [PATCH] Rmap speedup

From: Daniel Phillips (
Date: Mon Aug 05 2002 - 08:48:26 EST

On Monday 05 August 2002 09:05, Andrew Morton wrote:
> Andrew Morton wrote:
> It makes basically no difference at all. Maybe pulled back 10 of the lost
> 50%. The kernel is still spending much time in the pte_chain walk in
> page_remove_rmap().

I wouldn't call that 'no difference', just not as much as hoped for.

Well, I'm not quite out of tricks yet. There's one more to go, and it just
might be worth more than all the others. It's a little subtle though, and
I'm still working out some wrinkles, so I'll write it up in detail tomorrow.

For now, consider that our rmaps tend to form a lot of parallel chains. That
is, if you look at the chains for two pages whose index differs by one, the
pte fields of each of the pte_chain nodes differs by 4. This relationship
tends to hold quite consistently over rather large groups of pages, a fact
that I took advantage of in the lock batching. Now, if we put a relative
number in the pte field instead of an absolute pointer, the corresponding
pte_chain nodes for all those parallel chains become identical. How nice it
would be if we could share those pte chain nodes between pages.

I've convinced myself that this is possible. It's a little tricky though: we
have to handle CoW unsharing, and the possibility of the index changing (as
with the lock batching, but in this case there's a little more work to do).
My feeling is that the implementation will not be particularly messy, even
though it sounds scary on first blush.

> Despite the fact that the number of pte_chain references in
> page_add/remove_rmap now just averages two in that test.

It's weird that it only averages two. It's a four way and your running 10 in
parallel, plus a process to watch for completion, right?

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 : Wed Aug 07 2002 - 22:00:27 EST