Re: Comments conflicts with codes in HeapKeyGen_StoreEntry_LFUDA

--- maer727@sohu.com wrote:
> Here are the comments taken from the above of the
> function,
> HeapKeyGen_StoreEntry_LFUDA.
> ///////////////////////////////////////////////////
> but with aging to handle turnover of the popular
> document set
> ///////////////////////////////////////////////////
>
> Here are the codes taken from the same function,
> ///////////////////////////////////////////////////
> key = age + (double) e->refcount - tie;
> ///////////////////////////////////////////////////
>
> I think age means how long the object has been in
> cache.
> And if an object has a minimal key value then the
> object will be purged out from cache. Am I correct?
>

Wrong. age is the age of the heap. *Not* the age of an
object.

> The comment says that the purpose of LFUDA algorithm
> is to
> let the hot objects has less ability to stay in
> cache. Am
> I correct?
>

What is "ability"?

I asked a similar question to John Dilley (the guy who
wrote this part of code) and here is his reply.
---------------------------------------------------
The heap age is a technique to prevent frequency- or
refcount-based
policies
from perferring formerly popular objects over newer
objects. Imagine an
object that got a thousand hits a week ago and a
policy that computes
heap
key using refcount/size. The thousand hitter will
never be evicted.

However if you "age" all of the objects in the cache
by, say, dividing
their
key by some constant (say 2) or subtracting some
constant value from
their
key periodically then formerly-popular objects can be
evicted. A naiive
approach would walk the cache and touch each object
but this is very
expensive when there are millions of objects in the
cache.

Instead, the subtraction can be accomplished by adding
a "heap age" to
each
key when the key is computed (an object added or
updated). So if the
key
calculation is performed thus:
key = refs/size + age
you can easily see that incrementing the age by X
before adding a new
object
to cache has the same effect as decrementing all
previous keys by X.

There is a choice of how to compute age. The algorithm
I used is to set
the
age to the heap key of the most recently evicted
object. The key will
grow
over time, so it was made a float.
------------------------------------------------

Cheers,
Yee Man

__________________________________________________
Do You Yahoo!?
Yahoo! - Official partner of 2002 FIFA World Cup
http://fifaworldcup.yahoo.com
Received on Tue May 28 2002 - 12:15:31 MDT