[1a1a11a]

Thank you! Yes, this addresses the scan-resistant issue, but I am not sure how different it would be on workloads without scan. But the workloads we used in evaluations have very few scans, and the power of SIEVE comes from quickly evicting newer objects so I guess "random two" would not improve. But I do not have a number right now, I am happy to add this to the comparison list.

[thesz]

Please, do add the "two random choices" to the list. It is a noticeable omission, let me explain why.

Here are some comparisons of 2-random-choices with LRU in context of CPU caches: https://danluu.com/2choices-eviction/

Relevant quote: "LRU does worse than 2-random when the miss rates are high, and better when the miss rates are low."

"The miss rates are high" is the case when evicting newer but unused in nea future objects is preferable, in my opinion. Thus, "two random choices" algorithm is a direct competitor to SIEVE, they work better than LRU in about same conditions.

[1a1a11a]

I had a try on a few traces; the random two-choice algorithm is only better when there is a big scan, and the LRU miss ratio curve shows a cliff. In all other cases, it is worse than LRU eviction.

Implementation can be found https://github.com/1a1a11a/libCacheSim/blob/develop/libCache...