|
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]
|
