Hello all,
  I have searched a lot and found the current best lower bound for LFU
page replacement to be O(lg(n)). However, there is an O(1) method to
implement all the operations, namely (insert, delete and access), so
was wondering if anyone has some across something like this.
http://dhruvbird.blogspot.com/2009/11/o1-approach-to-lfu-page-replacement.html

-Dhruv.

On Nov 25, 11:25=A0am, dhruvbird <dhruvb...@gmail.com> wrote:
> Hello all,
> =A0 I have searched a lot and found the current best lower bound for LFU
> page replacement to be O(lg(n)). However, there is an O(1) method to
> implement all the operations, namely (insert, delete and access), so
> was wondering if anyone has some across something like this.http://dhruvb=
ird.blogspot.com/2009/11/o1-approach-to-lfu-page-replace...
>
> -Dhruv.

This is very nice.  Your method works fine.  The only problem in a
virtual memory system is that the access operation needs to be
implemented in hardware and run as fast as the memory access itself.
The linked list operations are probably not practical in this
setting.  I think most real systems still use the clock algorithm for
this reason.  If you are implementing a cache for a software system
like a database, this ought to work great as long as the RAM
requirement for the lists can be managed.  In a 64-bit system with
small pages, the list nodes could take up a significant fraction of
cache size.  You'd might look at doing the lists with Knuth's XOR
trick to halve the number of pointers.

On Nov 26, 8:04=A0am, Gene <gene.ress...@gmail.com> wrote:
> On Nov 25, 11:25=A0am, dhruvbird <dhruvb...@gmail.com> wrote:
>
> > Hello all,
> > =A0 I have searched a lot and found the current best lower bound for LF=
U
> > page replacement to be O(lg(n)). However, there is an O(1) method to
> > implement all the operations, namely (insert, delete and access), so
> > was wondering if anyone has some across something like this.http://dhru=
vbird.blogspot.com/2009/11/o1-approach-to-lfu-page-replace...
>
> > -Dhruv.
>
> This is very nice. =A0Your method works fine. =A0The only problem in a
> virtual memory system is that the access operation needs to be
> implemented in hardware and run as fast as the memory access itself.
> The linked list operations are probably not practical in this
> setting.

Yes, you are right. However, it can be used in applications like web-
server caches. They refused to use LFU because of the high cost(log n)
per operation, but now that it can be done in O(1), this should open
the way for implement the LFU algorithm in places that want an LFU
type of behaviour.

>=A0I think most real systems still use the clock algorithm for
> this reason. =A0If you are implementing a cache for a software system
> like a database, this ought to work great as long as the RAM
> requirement for the lists can be managed. =A0In a 64-bit system with
> small pages, the list nodes could take up a significant fraction of
> cache size. =A0You'd might look at doing the lists with Knuth's XOR
> trick to halve the number of pointers.

Even LRU as implemented currently uses linked lists, but I agree that
the constant space overhead would be lesser because it requires just
one linked list whereas I suggest using 2 for LFU.

Regards,
-Dhruv.