[jdjlist] Re: LFUCache -- a slightly different implementation

[James Stauffer]

Title: RE: [jdjlist] Re: LFUCache problem

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 -----Original Message----- From: Greg Nudelman [mailto:[EMAIL PROTECTED] Sent: Tuesday, November 18, 2003 10:52 AM To: jdjlist Subject: [jdjlist] Re: LFUCache -- a slightly different implementation 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 -----Original Message----- From: James Stauffer [mailto:[EMAIL PROTECTED] Sent: Monday, November 17, 2003 5:55 AM To: jdjlist Subject: [jdjlist] Re: LFUCache problem 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]