Benchmarks to exploit LRU deficiencies

Benchmarks to exploit LRU deficiencies

[Marcelo Tosatti]

Hi,

There are a few experimental implementations of advanced replacement
algorithms being developed and discussed. Unfortunately, there is lack of
knowledge on how to properly test them.

I've set up a page on the Linux-MM wiki with the intent to describe
LRU's weaknesses and collect benchmarks which exhibit its problems.

Contributions are essential to get this moving, please help.

At the moment there is one test (miniDB) available.

http://www.linux-mm.org/PageReplacementTesting

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: Benchmarks to exploit LRU deficiencies

[Marcelo Tosatti]

On Tue, Oct 11, 2005 at 02:13:29AM +0200, Andi Kleen wrote:
> On Monday 10 October 2005 20:46, Marcelo Tosatti wrote:
> > Hi,
> >
> > There are a few experimental implementations of advanced replacement
> > algorithms being developed and discussed. Unfortunately, there is lack of
> > knowledge on how to properly test them.
> 
> I think if you want to really see advantages you should not implement
> the advanced algorithms for the page cache, but for the inode/dentry
> cache. 

The major problem I can see is that of page versus icache/dcache 
"unused" list ordering and fragmentation, which is why we're trying
to aim at entire pages.

But other than that it works fine AFAIK.

> We seem to have far more problems in this area than with the
> standard page cache.

How's that?

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: Benchmarks to exploit LRU deficiencies

[Marcelo Tosatti]

On Tue, Oct 11, 2005 at 02:41:41AM +0200, Andi Kleen wrote:
> On Monday 10 October 2005 22:26, Marcelo Tosatti wrote:
> 
> > But other than that it works fine AFAIK.
> 
> I don't think so.
> 
> >
> > > We seem to have far more problems in this area than with the
> > > standard page cache.
> >
> > How's that?
> 
> At least in many cases where i've seen machines becomming unusable
> the problem was dcache/inode pollution, not page cache getting
> unbalanced.
> 
> Good example is running rsync.

You mean rsync kicks out your pagecache working set?

How come the machine is unusable?

How can the problem be reproduced? Run rsync is too vague I guess.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: Benchmarks to exploit LRU deficiencies

[Andi Kleen]

On Monday 10 October 2005 20:46, Marcelo Tosatti wrote:
> Hi,
>
> There are a few experimental implementations of advanced replacement
> algorithms being developed and discussed. Unfortunately, there is lack of
> knowledge on how to properly test them.

I think if you want to really see advantages you should not implement
the advanced algorithms for the page cache, but for the inode/dentry
cache. We seem to have far more problems in this area than with the
standard page cache.

-Andi

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: Benchmarks to exploit LRU deficiencies

[Andi Kleen]

On Monday 10 October 2005 22:26, Marcelo Tosatti wrote:

> But other than that it works fine AFAIK.

I don't think so.

>
> > We seem to have far more problems in this area than with the
> > standard page cache.
>
> How's that?

At least in many cases where i've seen machines becomming unusable
the problem was dcache/inode pollution, not page cache getting
unbalanced.

Good example is running rsync.

-Andi

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: Benchmarks to exploit LRU deficiencies

[Rik van Riel]

On Tue, 11 Oct 2005, Andi Kleen wrote:

> I think if you want to really see advantages you should not implement
> the advanced algorithms for the page cache,

I suspect the page cache really wants it too, especially
for database workloads.

> but for the inode/dentry cache. We seem to have far more problems in 
> this area than with the standard page cache.

However, I agree with you that the inode/dentry cache
probably needs it more on file and web server workloads.

The page cache getting invalidated whole inodes at a
time, even when the inode is getting referenced frequently,
could be a performance problem on some systems.

-- 
All Rights Reversed

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: Benchmarks to exploit LRU deficiencies

[Andi Kleen]

On Tuesday 11 October 2005 01:21, Marcelo Tosatti wrote:

> You mean rsync kicks out your pagecache working set?

Yes.

> How come the machine is unusable?

Everything is very slow.

> How can the problem be reproduced? Run rsync is too vague I guess.

Is it? Just try it. 

-Andi

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: Benchmarks to exploit LRU deficiencies

[Christoph Lameter]

On Tue, 11 Oct 2005, Andi Kleen wrote:

> I think if you want to really see advantages you should not implement
> the advanced algorithms for the page cache, but for the inode/dentry
> cache. We seem to have far more problems in this area than with the
> standard page cache.

We have had significant problems with the page cache for a long time. 
Systems slow down because node memory is filled up with page cache 
pages that are not properly reclaimed and thus off node allocation 
occurs. The current method of freeing memory requires a scan which 
makes this whole thing painfully slow. There are special hacks in SLES9 to 
deal with these issues.

Moreover the LRU algorithm leads to the eviction of important pages if a 
program does a simple scan of a large file.

I hope that the advanced page replacement methods address some of these 
problems.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: Benchmarks to exploit LRU deficiencies

[Magnus Damm]

On 10/12/05, Christoph Lameter <clameter@engr.sgi.com> wrote:
> On Tue, 11 Oct 2005, Andi Kleen wrote:
>
> > I think if you want to really see advantages you should not implement
> > the advanced algorithms for the page cache, but for the inode/dentry
> > cache. We seem to have far more problems in this area than with the
> > standard page cache.
>
> We have had significant problems with the page cache for a long time.
> Systems slow down because node memory is filled up with page cache
> pages that are not properly reclaimed and thus off node allocation
> occurs. The current method of freeing memory requires a scan which
> makes this whole thing painfully slow. There are special hacks in SLES9 to
> deal with these issues.
>
> Moreover the LRU algorithm leads to the eviction of important pages if a
> program does a simple scan of a large file.
>
> I hope that the advanced page replacement methods address some of these
> problems.

I think it would be interesting to separate the handling of mapped
pages from unmapped ones. The reason for this separation is the
difference how the working set is estimated:

Mapped pages:  young-bits in pte:s + mark_page_accessed().
Unmapped pages: mark_page_accessed() only.

Mapped pages needs to be scanned through to determine the working set
(and young-bits needs to be cleared), but unmapped working set
estimation could be handled directly by mark_page_accessed(), removing
the need to scan unmapped pages.

Another advantage of this separation IMO would be that it is easier to
build fine-grained memory resource control on top of it, where a
per-CPUSET (or CKRM class) guarantee and limit could be implemented
both for unmapped pages and mapped pte:s.

Other interesting areas are better mapped working set estimation
through periodical pte scanning and pte ageing, but I'm sure these
topics have been rejected before...

/ magnus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>