Skip to main content

Best performing Least Used List

3 replies [Last post]
byhisdeeds
Offline
Joined: 2006-01-06

I have a java application that requires me to sample hundereds of image files. To speed things up, I coded a Least Used List of a fixed size, of BufferedImages, that removed the least used entry when it required space for a new entry. I did this by using a priority queue to order a list of usage, as well as a hashmap to access the entries quickly.

it works ok, but I'm looking to optimise it and was wondering if anybody could tell me whether a Least Recently Used alogoritim would serve my purpose just as well. This would probably be faster, as I just keep the most recently accessed entry at the head of the list, and remove the tail when I need space.

Reply viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
jkleemann
Offline
Joined: 2004-06-29

Use EHCache (BlockingCacheFactory) and then you will get the benefit of an image cache too. I did this with a specialised PDFViewer whereas i modified ehcache a bit to support nonmutable cache entries (normally ehcache writes entries it read from the cachefile back to disk again because it cannot decide if the entry was modified or not).

Of course you can omit serialising / diskcaching. That would make sense if you need something like thumbnails resp. creating your cached image is more expensive than some file-io which depends on the size of the images on disk, in your memory, .... you will know whats best.

The serialisation code for a buffered image is easy when you use a common internal format (its mostly RGB, 8bit comps.) - just get the databuffers and some metastuff... i can show you the code ... its simple. So i wrote what i called ImageWrapper and added some serialisation code to it.

the you do not need to worry anymore (except for creation of images) but if your hashtable key is sufficient to create the image/thumbnail (like a relative file reference to a basedir,etc) then this is what i would do.

Memory mgmt is something special, but with ehcache you will specify something like max-mem-elements=N

Implemented in a day and then you never have to worry again, cache eviction policies can be set to 2 modes (but i would guess you would never be able to tell a difference).

Message was edited by: jkleemann

bclapper
Offline
Joined: 2005-07-29

Another option is the Apache Commons Collection class LRUMap. See
http://commons.apache.org/collections/api-release/org/apache/commons/col...

byhisdeeds
Offline
Joined: 2006-01-06

OK. For my exisitng implementation I get 99.06% hit rate after 10 million requests. When I implement the LRU using the LinkedHashMap I get 100% for the same and more requests. As my access pattern is regular I guess that's to be expected. I'm gonna try the apache commons LRUMap next and see if that give similar performance.

I need a light weight solution so the EHCache seems a bit heavy, but I'll look into it.

Thanks everyone.