Benchmarks to exploit LRU deficiencies
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 [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 5 lines · 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 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 [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 10 lines · Andi Kleen
Quoted 5 lines · 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 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.
Quoted 2 lines
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 [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 1 line · Marcelo Tosatti
But other than that it works fine AFAIK.
I don't think so.
Quoted 5 lines
Quoted 3 lines
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 [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 10 lines · Andi Kleen
Quoted 1 line · Marcelo Tosatti
But other than that it works fine AFAIK.
I don't think so.
Quoted 4 lines
Quoted 3 lines
We seem to have far more problems in this area than with the standard page cache.
Quoted 7 lines
Quoted 1 line
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 [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 1 line · Marcelo Tosatti
You mean rsync kicks out your pagecache working set?
Yes.
Quoted 1 line
How come the machine is unusable?
Everything is very slow.
Quoted 1 line
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 [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 2 lines · Andi Kleen
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.
Quoted 2 lines
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.
Signature · 7 lines
All Rights Reversed -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 4 lines · Andi Kleen
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 [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 14 lines · Christoph Lameter
Quoted 4 lines · Andi Kleen
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.
Quoted 5 lines
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 [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>