LouisJenkinsCS
commented
4 years ago Idea: Use a Splay Tree...
This doubles as an LRU Cache as the most-recently used nodes reach the root of the tree, and the random-eviction algorithm will only sample from the leaf nodes, meaning you have a gigantic stochastic LRU cache. Performance is going to be excellent when cache-lines are accessed more often than others as well, thanks to the properties of the splay tree.
The SPC needs a more specialized and specific data structure than what is currently available. Right now it uses Valgrind's
OSet, which is an ordered-set, implemented as an AVL Tree. As Michael has pointed out, it is easily possible to trim each store to a cache-line and then check in O(log(N)) (or even O(1)) time to check if it exists in the set. I am of the mindset that a Tree-based data structure which maintains the number of children it has, would be a much better choice. It has the following properties...1) All access is O(log(N)) which is O(1) given that the size of the cache is bounded. 2) Randomly sampling can be performed by weighting the left and right children and performing randomized/stochastic traversal to find a child to evict. 3) Optimizations that are specific to the SPC can be leveraged to speedup performance, which could be essential, especially for large-scale applications.