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