Least Recently Used (LRU) Cache

Question

I know that I can use various container classes in STL but it's an overkill and expensive for this purpose.

We have over 1M+ users online and per user we need to maintain 8 unrelated 32-bit data items. The goal is to

1. find if an item exists in the list,
2. if not, insert. Remove oldest entry if full.

Brute Force approach would be to maintain a last write pointer and iterate (since only 8 items) but I am looking for inputs to better analyze and implement.

Look forward to some interesting suggestions in terms of design pattern and algorithm.

Answer 1

Don Knuth gives several interesting and very efficient approximations in The Art of Computer Proramming.

1. Self-organizing list I: when you find an entry, move it to the head of the list; delete from the end.

2. Self-organizing list II: when you find an entry, move it up one spot; delete from the end.

   [Both the above in Vol. 3 §6.1(A).]

3. Another scheme involves maintaining the list circularly with 1 extra bit per entry, which is set when you find that entry, and cleared when you skip past it to find something else. You always start searching at the last place you stopped, and if you don't find the entry you replace the one with the next clear bit with it, i.e. it hasn't been used since one entire trip around the list.

   [Vol. 1 §2.5(G).]

Answer 2

You want to use here a combination of a Hash table and a doubly linked list.
Each item is accessible via the hash table that holds the key you need plus a pointer to the element in the list.

Algorithm:

Given new item x, do:
1. Add x to the head of the list, save pointer as ptr.
2. Add x to the hash table where the data is stored, and add ptr.
3. If the list is bigger than allowed, take the last element (from the tail of the list) and remove it. Use the key of this element to remove it from the Hash table as well.