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

[Bill Davidsen <davidsen@tmr.com>]

Peter Zijlstra wrote:

>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.
>

Thanks, you have cleared up all of the issues which I felt were unclear.

-- 
bill davidsen <davidsen@tmr.com>
  CTO TMR Associates, Inc
  Doing interesting things with small computers since 1979