Re: ARC patent

On Mon, 2005-01-17 at 15:11 -0500, Andrew Dunstan wrote:
> There's a very recent paper at
> http://carmen.cs.uiuc.edu/~zchen9/paper/TPDS-final.ps on an alternative
> to ARC which claims superior performance ...

>From a quick glance, this doesn't look applicable. The authors are
discussing buffer replacement strategies for a multi-level cache
hierarchy (e.g. they would call the DBMS buffer cache "L1", and the
kernel I/O cache "L2" -- note that despite the terminology, this has
little in common with L1/L2 caches in processors). They don't really
address caching for the L1-only case -- they're concerned with proposing
algorithms to manage the L2 cache (with or without explicit knowledge
about the content of the L1 cache).

A few years ago Tom implemented the LRU-K replacement policy[1], but
AFAIK the performance results from that weren't very positive (since the
implementation of LRU-K requires a heap and is therefore logarithmic
rather than constant time, that makes sense). The 2Q algorithm looks
like it might be worth investigating[2].

-Neil

[1] http://citeseer.ist.psu.edu/16869.html
[2] http://citeseer.ist.psu.edu/63909.html