5 ms·

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 c

• thesz 3y ago
  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.