Re: [PATCH] Rmap speedup

[Daniel Phillips <phillips@arcor.de>]

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?

-- 
Daniel