[1a1a11a]

Sorry, I may miss something. How would "random two choices" differ from LRU?

[thesz]

I provided a link, you can read more about differences there.

LRU suffers from linear access pattern, where it cannot degrade gracefully. Try to cache N+1 items in N-item LRU when items are accessed linearly or at random with removal.

The "random two choices" algorithm will replace an entry that is less recently accessed from two randomly selected. There is a chance that some of N+1 linealy accessed items will be in cache after a full scan.

[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...

[thesz]

This is the implementation of hashtable_rand_obj:

  cache_obj_t *chained_hashtable_rand_obj_v2(const hashtable_t *hashtable) {
    uint64_t pos = next_rand() & hashmask(hashtable->hashpower);
    while (hashtable->ptr_table[pos] == NULL)
      pos = next_rand() & hashmask(hashtable->hashpower);
    return hashtable->ptr_table[pos];
  }

It returns first object in random chain, not the random object. This introduces a bias into selection of random objects. I have not had time to review your other code, but I strongly suspect return values of hashtable_rand_obj are skewed into preferring more recently inserted objects.

As the code of RandomTwo depends on the hashtable_rand_obj, it also biased.

The same is for Random cache policy.