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