Prev: A new prime number pattern
Next: solutions to Sipser's Theory of Computation
From: Tim Little on 13 Jul 2010 05:58
On 2010-07-13, dhruvbird <dhruvbird(a)gmail.com> wrote:
> Exactly, which is why the count is approximated for only those
> objects in the cache.

It's not even an approximation. The counts you have are not
approximations of frequencies, they are not even related.


> I hope you see the practical value of evicting the least
> "frequently" used items from the cache (along with their counts).

I don't, as your algorithm yields a *terribly poor* eviction policy.
It can result in 100% cache miss rate with arbitrarily large cache
sizes for situations in which only 2 objects are accessed frequently.
In many cases of actual usage patterns it will be even worse than FIFO
or random eviction. For most practical access patterns it comes
pretty close to being LIFO, which is very much an opposite of
desirable cache behaviour.


However, I am convinced that you are happy with its performance, and
that you are also happy to call it LFU. So I think we're done.


- Tim
From: dhruvbird on 13 Jul 2010 13:52
On Jul 13, 2:54 pm, Dann Corbit <dcor...(a)connx.com> wrote:
> In article <da10bed9-6d80-4f30-a6b4-0fc8bb1fa3b7
> @x18g2000pro.googlegroups.com>, dhruvb...(a)gmail.com says...
>
>
>
>
>
>
>
> > On Jul 12, 4:04 pm, Tim Little <t...(a)little-possums.net> wrote:
> > > On 2010-07-12, dhruvbird <dhruvb...(a)gmail.com> wrote:
>
> > > > While I agree with the point you make about LFU working in a certain
> > > > way, this is exactly how all currently implemented LFU algorithms
> > > > work.
>
> > > No, LFU caches periodically age entries so that the frequencies
> > > are updated.
>
> > On the contrary, pure LFU is based on access count only and the
> > algorithm you mention is actually a variation which involves ageing.
> >http://en.wikipedia.org/wiki/Least_Frequently_Used
> >http://en.wikipedia.org/wiki/Cache_algorithms#Least-Frequently_Used
>
> Did you bother to read those entries?
>
> "Least frequently used
> In computer science, the term "Least Frequently Used" (LFU) refers to a
> cache algorithm for memory management. The expiration policy removes
> entities from the cache that are used the least. If the use frequency of
> each entity is the same, then they are expired by the Least Recently
> Used (LRU) algorithm."
>
> Here is the entry for the LRU algorithm:
>
> "Least Recently Used (LRU): discards the least recently used items
> first. This algorithm requires keeping track of what was used when,
> which is expensive if one wants to make sure the algorithm always
> discards the least recently used item. General implementations of this
> technique require to keep "age bits" for cache-lines and track the
> "Least Recently Used" cache-line based on age-bits. In such
> implementation, every time a cache-line is used, the age of all other
> cache-lines changes. LRU is actually a family of caching algorithms with
> members including: 2Q by Theodore Johnson and Dennis Shasha and LRU/K by
> Pat O'Neil, Betty O'Neil and Gerhard Weikum."
>
> It is clear that time is involved.

1. It is not necessary that items with the same frequency get evicted
by the LRU algorithm. It is just *one* of the ways to go about the
task. There could be a different way wherein any random entry is
evicted if there are many frequently used entries (having the same
access count/frequency).

2. LRU is an orthogonal discussion.

3. LRU doesn't require you to keep track of time. It can be (and
usually) is very easily implemented by using a combination of a linked
list and a hash map.

Regards,
-Dhruv.
From: dhruvbird on 13 Jul 2010 13:57
On Jul 13, 2:58 pm, Tim Little <t...(a)little-possums.net> wrote:
> On 2010-07-13, dhruvbird <dhruvb...(a)gmail.com> wrote:
>
> > Exactly, which is why the count is approximated for only those
> > objects in the cache.
>
> It's not even an approximation.  The counts you have are not
> approximations of frequencies, they are not even related.

You have obviously missed the interpretation of "frequently" in LFU.

>
> > I hope you see the practical value of evicting the least
> > "frequently" used items from the cache (along with their counts).
>
> I don't, as your algorithm yields a *terribly poor* eviction policy.
> It can result in 100% cache miss rate with arbitrarily large cache
> sizes for situations in which only 2 objects are accessed frequently.
> In many cases of actual usage patterns it will be even worse than FIFO
> or random eviction.  For most practical access patterns it comes
> pretty close to being LIFO, which is very much an opposite of
> desirable cache behaviour.

From what I see, you aren't giving any solid evidence or even quoting
any publications to base your claims on.
I have quoted numerous resources which clearly contradict the views
you held.

Regards,
-Dhruv.
From: dhruvbird on 13 Jul 2010 13:59
On Jul 13, 2:37 pm, Tim Little <t...(a)little-possums.net> wrote:
> On 2010-07-13, dhruvbird <dhruvb...(a)gmail.com> wrote:
>
> > From:http://docs.jboss.org/jbosscache/1.4.0/TreeCache/en/html/eviction_pol...
> > "Node usage starts at 1 when a node is first added. Each time it is
> > visted, the node usage counter increments by 1. This number is used to
> > determine which nodes are least frequently used."
>
> Also from that page: "wakeUpIntervalSeconds. This is the interval (in
> seconds) to process the node events and also to perform sweeping for
> the size limit and age-out nodes."  So it does ageing, which allows
> counts to estimate frequency of use.  Yours does not estimate
> frequency of use, and old but infrequently used nodes may never be
> evicted.

As I had earlier mentioned, this is one variation of LFU which is
called "ageing LFU".

Regards,
-Dhruv.
From: Dann Corbit on 13 Jul 2010 14:33
In article <5b3865ae-24ad-43dd-9416-495d8f3fad58
@x1g2000prc.googlegroups.com>, dhruvbird(a)gmail.com says...
> 1. It is not necessary that items with the same frequency get evicted
> by the LRU algorithm. It is just *one* of the ways to go about the
> task. There could be a different way wherein any random entry is
> evicted if there are many frequently used entries (having the same
> access count/frequency).

What do you think the "Recently" means in Least Recently Used?
If we do not consider time, then it is not an LRU algorithm.

> 2. LRU is an orthogonal discussion.
>
> 3. LRU doesn't require you to keep track of time. It can be (and
> usually) is very easily implemented by using a combination of a linked
> list and a hash map.

If it does not consider time, then it is not an LRU algorithm. It is
something else.

First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4
Prev: A new prime number pattern
Next: solutions to Sipser's Theory of Computation