Re: [PATCH 0/7] CART - an advanced page replacement policy

[Peter Zijlstra <a.p.zijlstra@chello.nl>]

On Thu, 2005-09-29 at 15:40 -0400, Bill Davidsen wrote:
> Peter Zijlstra wrote:
> > Multiple memory zone CART implementation for Linux.
> > An advanced page replacement policy.
> > 
> > http://www.almaden.ibm.com/cs/people/dmodha/clockfast.pdf
> > (IBM does hold patent rights to the base algorithm ARC)
> 
> Peter, this is a large patch, perhaps you could describe what configs 
> benefit, 

All those that use swap. Those that exploit the weak side of LRU more
than others.

CART is an adaptive algorithm that will act like LFU on one side and LRU
on the other, capturing both behaviours. Therefore it is also scan
proof, eg. 'use once' scans should not flush the full cache.

Hence people with LFU friendly applications will see an improvement
while those who have an LRU friendly application should see no decrease
in swap performance.

Non of the algorithms handle cyclic access very well, that is what patch
5 tries to tackle.

> how much, 

In the cyclic case (n+a: a << n) I've seen speedups of over 300%. Other
cases much less. However I've yet to encounter a case where it gives
worse performance.

I'm still constructing some corner case tests to give more hard numbers.

> and what the right to use status of the patent might 
> be. 

AFAIK IBM allows Linux implementation of their patents.
See: http://news.com.com/IBM+pledges+no+patent+attacks+against+Linux/2100-7344_3-5296787.html

> In other words, why would a reader of LKML put in this patch and try it?
> The description of how it works is clear, but the problem solved isn't.

I hope to have answered these questions. If any questions still remain,
please let me know.

Kind regards,

Peter Zijlstra


-- 
Peter Zijlstra <a.p.zijlstra@chello.nl>

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/