News for hackers. Stuff that matters.
Re:Cache Eviction: When Are Randomized Algorithms Better Tha... by carlmr on Monday February 18, 2019 @03:37AM (#19189340)
>>When Are Randomized Algorithms Better Than LRU?

>When the access pattern is random: recently used items are not more likely to be accessed than other items.

Wouldn't they perform equally well in this case? There's no advantage in LRU, but also no disadvantage if they're really unpredictably random.

Re:Cache Eviction: When Are Randomized Algorithms Better Tha... by adrianN on Monday February 18, 2019 @03:42AM (#19189363)
A random strategy has less overhead than LRU because there is no bookkeeping.
Re:Cache Eviction: When Are Randomized Algorithms Better Tha... by dan-robertson on Monday February 18, 2019 @10:12AM (#19191169)
This argument does not apply to the OP as it does not account for any bookkeeping. I think an actual answer is more complicated and will entirely depend on the definition of “random access pattern.”
Re:Cache Eviction: When Are Randomized Algorithms Better Tha... by carlmr on Tuesday February 19, 2019 @01:32PM (#19201460)
Yes, and bookkeeping and randomness both cost something.