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