Implement pseudo-LRU for several cache options

[pavelkryukov]

Currently we can model only True LRU in our caches. However, in real life caches implement PseudoLRU using binary trees. It has 90% precision in comparison to True LRU.

The change should go with new infrastructure which would allow to select LRU mode with string similarly to BPU mode selection.

[agrachiv]

Should I use my own simple binary tree realization, or it is better to use some well-protected structures with canaries and other stuff? This also might be a general question not only related to this issue.

[pavelkryukov]

Yes, you may use something from STL or Boost if there are any, or copy it from other sources. Please mind the license — we're using MIT, so we cannot use GPL code, for instance.

[pavelkryukov]

Now you have the unit tests for true LRU, and you have LRU deployable separately, so it becomes simpler to implement pseudo LRU or any other scheme.

[agrachiv]

I faced the problem. The methods I've added to the tru-LRU implementation in order to use it in functional simulator are not required in the performance one. But abstract class CacheReplacementInterface contains pure virtual methods that must be overridden (for example allocate). So I might need to separate back functional and performance implementation, or even desist from using abstract classes syntax, but all this solutions seems stupid. So could you suggest me something?

P.s: Also could you please remind me, what is the laboratory work deadline?

[pavelkryukov]

Just throw an exception in implementation of the derived class method.