Caches: LRU vs. Random
10 months ago
- #performance optimization
- #computer architecture
- #cache eviction policies
- 缓存随机淘汰策略并不像普遍认为的那么糟糕，尤其是与LRU（最近最少使用）算法相比时。
- 当紧密循环完全命中缓存时LRU表现优异，但若循环超出缓存容量就会引发缺失，而随机淘汰的性能下降更为平缓。
- 2-随机淘汰策略（通过LRU在两个随机选项中抉择）展现出强劲竞争力，尤其在大型缓存中表现突出。
- 在SPEC CPU基准测试中，2-随机与LRU性能接近：LRU在小型缓存中略优，而2-随机在大型缓存中更胜一筹。
- 层级化缓存结构使淘汰策略效果复杂化，因为LRU对L3等高层级缓存可能并非最优选择。
- 伪LRU和伪2-随机策略提供了接近真实算法的实用方案，前者逼近LRU性能，后者近似2-随机效果。
- 提高缓存关联度会扩大LRU与2-随机之间的性能差距，其中LRU在小型缓存中更受青睐。
- 2-随机策略的数学原理基于『双随机选择的威力』理论，该理论证明了负载均衡中对数级的改进效果。
- 未来研究方向可包括：为不同缓存层级定制淘汰策略，或将2-随机策略拓展至CPU缓存之外的其他缓存类型。