LFU is a much trickier concept than LRU for
caching. Of course, any LFU implementation must really be a hybrid LRU/LFU
algorithm. Otherwise once the cache fills up, nothing else can ever get
inserted!
It seems what is really needed here is an algorithm
that utilizes two metrics, last access, and total accesses,
in determining when to invalidate (remove) an element.
I have a few of recommendations:
- maintain two usage counts, one for the previous
period (hour, day, whatever) and one for the current period. Use the
sum of these to give you a moving hit count
that won't overflow an int.
- maintain a Map on top of your linked list to
provide quick access to cache elements: O(logN) vs O(N) if I remember my
Analysis of Algorithms class correctly.
- maintain your linked list in LRU order, but apply
an additional criteria when invalidating elements. E.g., whenever the
cache fills up remove the 1st 10% of elements whose usage count is below a
threshold. If you don't find enough, raise the threshold and try
again.
- use Doug Lea's data structures to reduce the
locking and lock-contention penalties.
- for testing use a non-uniform random number
generator (like java.util.Random.nextGaussian()) to generate your
keys. This will better similate a typical cache situation where certain
elements are much more likely to get requested.
I may take a crack at this ... it's been a while
since my last attempt at a cache utility.
Keats
----- Original Message -----
Sent: Tuesday, November 18, 2003 1:36
PM
Subject: [jdjlist] Re: LFUCache -- LRU vs
LFU implementation
If the cache is sized well is there much difference between LRU and
LFU?
I know that our cache implementation needs a redesign but it seems
those things are never very high on the company's priority list.
:-)
James Stauffer
Dear
James,
What you're describing is a good implementation of the
LRU (Least-Recently-Used) cache. Mine is a LFU (Least-Frequently-Used)
cache.
Also, I should mention that the performance of removing
from a Vector by item value (not item index in the List) is O(n) as well, so
your implementation probably suffers from the same problem as mine, i.e. the
speed of cache operations depends linearly on the cache size. I expect
that due to using a Vector to maintain the order you'll get an O(n)
performance for both for get() and add().
Nonetheless, thanks for letting me know
that this works well under "normal circumstances". That
is very encouraging!
BTW, a slightly better implementation of the
LRUCache is to use a hand-made linked list instead of a Vector. That way
you get constant-time performance for get() and add() since you maintain the
pointers to the head and tail of the list, as well as pointers to every
individual element (through the hash) so you don't need to re-shuffle your
List every time you remove something, you just point the (now orphan) child
back to the grand-parent and you're done. By using a linked list to
maintain the order, you get O(alpha) (i.e. constant-time) for the remove() and
add() operations (no search time and no reshuffling) that results in O(alpha)
for both get() and add() operations in the cache. I can send you that
implementation if you like.
If only I could get that kind of
O(alpha) performance for the LFUCache add()...
Darn!! :-)
Greg
Could
both adds and gets change the order?
For our cache we have a Hashtable
(old code so old classes) and a Queue (Implemented as a Vector -- again old
code). get:
1. Use the Hashtable to get the
object. 2. Remove the key from the Queue and
add it in again (basically resetting its
age) add: 1. If full first remove the head item from the Queue and
also remove it from the Hashtable 2. Add the object to the Hashtable and the
key to the Queue.
With a good better implementation of
the Queue I think it would give very good
performance.
James Stauffer
Dear James
and All,
In other words, what happens more, get() or
add()? I would think for well-sized cache, you should get a "quite a
few more" :-) get() then add()... I guess that's what I'm expecting.
You may get significant churning if it's badly sized. But for our
system, 80% of requests use 20% of our objects. And since every missed
get() is also an add(), for us it makes a lot of sense to have LFUCache
instead of LRUCache. Unfortunately, after my testing, I determined that, as
expected, the performance of the add() operation is not that great. In fact
it is O(n), while the get() is constant -time with this configuration.
It is almost as though it would be nice to have a List set up in parallel
that is sorted periodically by a background thread that depends on
use. Then the add() is also basically constant-time, but that
kind of class is not easy to test reliably, since depending on when the
sorter thread wakes up, you'll get different cache
contents...
Maybe the thing to do is to set up frequency buckets
rather then a full sort. But then you have to adjust the bucket
boundaries as the max frequency increases (what a mess, hehehehe).
Anyway, here
is the solution for now (it was developed on my own time and equipment, and
is in no shape or form affiliated with IMX or it's subsidiaries, though it
may, at some point, be used by IMX). Feel free to use it if you
like, but as I mentioned above, the add() performance is not that
great:
http://www.hotscifi.com/archive/LFUCache.java
Thanks again Everyone for all your help. Feel free to
give me a piece of your mind, if you feel like doing a quick review of this
code. I'll try to continue posting updates to this, if I
can.
Greg
Since the order that you want things sorted in can change based on
usage then it could never keep it sorted with a standard collection.
Correct?
What happens more? The action that
changes the order (accessing the items) or getting the items in the sorted
order?
James Stauffer
---
You are currently subscribed to jdjlist as:
[EMAIL PROTECTED]
To unsubscribe send a blank email to
[EMAIL PROTECTED]
http://www.sys-con.com/fusetalk
To unsubscribe from all mailing lists, click:
http://sys-con.com/[EMAIL PROTECTED]
---
You are currently subscribed to jdjlist as: [EMAIL PROTECTED]
To unsubscribe send a blank email to
[EMAIL PROTECTED]
http://www.sys-con.com/fusetalk
To unsubscribe from all mailing lists, click:
http://sys-con.com/[EMAIL PROTECTED]
---
You are currently subscribed to jdjlist as:
[EMAIL PROTECTED]
To unsubscribe send a blank email to
[EMAIL PROTECTED]
http://www.sys-con.com/fusetalk
To unsubscribe from all mailing lists, click:
http://sys-con.com/[EMAIL PROTECTED]
---
You are currently subscribed to jdjlist as: [EMAIL PROTECTED]
To unsubscribe send a blank email to
[EMAIL PROTECTED]
http://www.sys-con.com/fusetalk
To unsubscribe from all mailing lists, click:
http://sys-con.com/[EMAIL PROTECTED]
---
You are currently subscribed to jdjlist as: [EMAIL PROTECTED]
To unsubscribe send a blank email to [EMAIL PROTECTED]
http://www.sys-con.com/fusetalk
To unsubscribe from all mailing lists, click:
http://sys-con.com/[EMAIL PROTECTED]
****************************************************************************
This e-mail, and any attachment, is intended only for the person or entity to which it is addressed and may contain confidential and/or privileged material. Any review, re-transmission, copying, dissemination or other use of this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from any computer. The contents of this message may contain personal views which are not the views of Discovery Communications, Inc. (DCI).
****************************************************************************
|
