|
The formatting on that is bad. Why does it remove my returns? I made a
few changes below to make it easier to read.
James Stauffer
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]
|
