#5 LRUNode Does not Reset timeout on use

[Anonymous]

The LRUNode class does not reset its timeout value when
someone calls its getValue() method. This results in
items being removed regardless of their use.

This violates the concept of an LRU cache (at least
according to definition).

The fix is to reset the timeout value for the node when
the object's value is retrieved.

I have add this to the lru cache code and included the
file.

Might I also suggest refactoring the LRUNode to expose
its variables through methods rather than friendly
variable visibility? This would greatly decrease
confusion into who sets these variable's values.

Cheers.

[Nobody/Anonymous]

Modified source file for the LRU Cache.

[Jeff Drost]

Logged In: YES
user_id=348597

No.. actually this is intentional. The fact that the node
was used doens't change the time it was put into the cache.
The key here is the freshness of the data, which is what
the timeout does. The timeout may remove elements from the
cache, event if the max capacity is not meet. Only when the
max capacity is reached are non-expired nodes removed, and
they are removed reguardless of their timeout.

In my oppinion, the timeout is needed to keep the freshness
of the objects predictable, while the policy is used to
prevent the cache from consuming too much memory.

[Paul Cooley]

Logged In: YES
user_id=1001040

The contract of the LRU cache not stipulates the maxSize is
not to be violated, but that Least Recently Used items will
be dumped. I take this to mean, by definition, that items
that have not been accessed within the timeout will be
dropped.

But if an item is used, its timeout should be reset and
considered "fresh" again, since it has been recently used.
The item is then allowed to expire again as if it was a new
item, unless, of course, it is used once again.

The code in the LRU cache DOES move the item to the head of
the linked list, but since it does not reset the timeout,
the item expires even though it has been used.

Perhaps we are disagreeing on the definition of LRU:
http://en.wikipedia.org/wiki/Cache_algorithms

Thanks for the response. Cheers.

[Jeff Drost]

Logged In: YES
user_id=348597

Read your WIKI page again.

"Cache size is usually limited, and if the cache is full,
the computer (that is, the programmer) must decide which
items to keep and which to discard to make room for new items."

There are two major problems with a cache that is impemented
as your suggest.
(1) the timeout is ignored as long as nodes are used
frequently - this means very stale data can get stuck in the
cache as long as it is used frequently. I see the timeout as
a threshold for how old you are willing to let you data
get. That time starts when the data is obtained and stored
in the cache - not when it is used.
(2) if the cache's size is not bounded - if more nodes are
added to the cache faster than they expire, you will run
into a resource (memory) problem.

If you don't want nodes to expire due to a timeout, and only
want nodes to be evicted when the max capacity is reached,
then set your timeout to a really big number.