[Adept Open Source Library] The LRU Cache
Paul Marrington
// Once 50 elements are cached the least recently accessed will be discarded. Cache cache = new Cache( 50);
Just think of a linked list. When you add an item it's added to the end of the list. When you access an item it's unlinked from its current location and linked again at the end. Therfore if you add an item to a list with the maximum number of entries, then the item at the start of the list is removed, close called if closeable, and discarded.
Note that because the Cache class is used for more than just simple LRU caches, the clean operation does not happen synchronously. An item is added on request then the method returns to the caller. This makes the cache very fast. A lower priority background thread will pick up oversized caches, closing and removing least-recently-used items that aren't currently locked.
The LRU cache is commonly used to cache objects in memory that would otherwise require a more expensive retrieval procedure. The Adept browser code, for example, uses a LRU cache to hold static elements such as HTML files and images. This way they are loaded from disk once and served from memory if they are popular enough to always be at the end of the list. Items that are used infrequently are more likely to be discarded and require a disk retrieval to get back. Note that the browser caches static content in a similar way. In addition, the Adept server cache will effect files requested from multiple browsers.
Using a LRU cache, rather than storing the item in a Map, allows the developer to control memory usage.
If there's any possibility that an item being cached may change at the original source, use a trigger or time sensitive cache as well as the LRU method.
Next time we'll talk about Time Sensitive Caches.
--
Posted by Paul Marrington to Adept Open Source Library at 8/31/2005 04:06:00 PM