Introduction
A LRU Cache is a key-value based data container that is constrained by size and/or age, removing the least recently used objects first. This algorithm requires keeping track of the most recent time each object is accessed.
1:Most LRU Caching algorithms consist of two parts: a dictionary and a doubleLinkLlist.
1:The dictionary guarantees quick access to your data.
2:In double linked list the node can remove itself without other reference. it takes constant time to add and remove nodes from the head or tail.
Alogorith 1: adding new items to the head, removing items from the tail, and moving any existing items to the head when referenced (touched). This algorithm is good for single threaded applications but becomes very slow in a multi-threaded environment.
In a multi-threaded app, every time the linked list is modified, it must be locked. This requires thread locks on insert, read, and delete operations, causing the slowness.
Alogorith 2:Another algorithm is to mark each item’s age with a timestamp (DateTime or incremented Integer) value when touched. When the cache becomes full, the list of items must be sorted and truncated. This keeps insert and read operations very fast because no locks are required, but makes delete painfully slow (normally O(N * log N), for sorting).
Available Library :https://github.com/bitfaster/BitFaster.Caching
pseudo LRU designed for concurrent workloads – currently in use in a production system. Performance is very close to ConcurrentDictionary, ~10x faster than MemoryCache and hit rate is better than a conventional LRU. Full analysis provided in the github link below.
algorithm3:AgeBag’s
My implementation of LRUCache contains two distinct sections which are coded as subclasses. The LifespanMgr class tracks the item usage and determines which items to remove when the cache gets full/old. The Index class provides Dictionary key/value access to all objects stored in the cache. The Index has delegates to calculate the key of any item added to the cache, and to load an item by key/value from an external source.
Instead of storing item nodes in the Index, the Index holds WeakReference objects that point at the item nodes. By doing this, the Index does not prevent items from being garbage collected. This also allows old items to be removed from the AgeBag without having to remove the items from the index. Once a Node is removed from the LifespanMgr, it becomes eligible for garbage collection. The Node is not removed from the Indexes immediately. If an Index retrieves the node prior to garbage collection, it is reinserted into the current AgeBag’s node list. If it has already been garbage collected, a new object gets loaded. If the Index size exceeds twice the cache’s capacity, the Index is cleared and rebuilt.
ref :https://www.codeproject.com/Articles/23396/A-High-Performance-Multi-Threaded-LRU-Cache
Pseudo-LRU (PLRU)
For CPU caches with large associativity (generally >4 ways), the implementation cost of LRU becomes prohibitive. In many CPU caches, a scheme that almost always discards one of the least recently used items is sufficient, so many CPU designers choose a PLRU algorithm which only needs one bit per cache item to work. PLRU typically has a slightly worse miss ratio, has a slightly better latency, uses slightly less power than LRU and lower overheads compared to LRU.
Site Title 