使用时间戳实现 LRU：内存存储和加载有多昂贵？
Implementing LRU with timestamp: How expensive is memory store and load?
我说的是用 C 而不是 Java 或 C++ 实现的 LRU 内存页面替换算法。
根据OS课程notes：
OK, so how do we actually implement a LRU? Idea 1): mark everything we touch with a timestamp.
Whenever we need to evict a page, we select the oldest page (=least-recently used). It turns out that this
simple idea is not so good. Why? Because for every memory load, we would have to read contents of the
clock and perform a memory store! So it is clear that keeping timestamps would make the computer at
least twice as slow. I
内存加载和存储操作应该非常快。 真的有必要去掉这些小操作吗？
在内存替换的情况下，从磁盘加载页面的开销应该比内存操作大很多。为什么实际上会关心内存存储和加载？
如果注释说的不对，那么用时间戳实现LRU的真正问题是什么？
编辑：
随着我深入挖掘，我能想到的原因如下。这些 内存存储和加载 操作在页面点击时发生。在这种情况下，我们没有从磁盘加载页面，因此比较无效。
由于预计命中率会很高，所以更新LRU相关的数据结构应该会很频繁。这就是为什么我们关心更新过程中重复的操作，例如内存加载和存储。
但是，我仍然不能说服进行内存加载和存储的开销有多大。周围应该有一些测量。有人可以指点我吗？谢谢！
内存加载和存储操作可能非常快，但在大多数现实生活中，内存子系统比 CPU 的执行引擎慢 - 有时慢得多。
内存访问时间的粗略数字：
- L1 缓存命中：2-4 CPU 周期
- L2 缓存命中：10-20 CPU 个周期
- L3 缓存命中：50 CPU 周期
- 主内存访问：100-200 CPU 周期
因此加载和存储需要实时时间。使用 LRU，每次常规内存访问也会产生内存存储操作的成本。仅此一项就使 CPU 的内存访问次数增加了一倍。在大多数情况下，这会减慢程序的执行速度。此外，在页面逐出时，需要读取所有时间戳。这会很慢。
此外，不断读取和存储时间戳意味着它们将在 L1 或 L2 缓存中占用 space。 Space在这些缓存中是有限的，因此您的其他访问的缓存未命中率可能会更高，这将花费更多时间。
简而言之 - LRU 相当昂贵。
我说的是用 C 而不是 Java 或 C++ 实现的 LRU 内存页面替换算法。
根据OS课程notes：
OK, so how do we actually implement a LRU? Idea 1): mark everything we touch with a timestamp. Whenever we need to evict a page, we select the oldest page (=least-recently used). It turns out that this simple idea is not so good. Why? Because for every memory load, we would have to read contents of the clock and perform a memory store! So it is clear that keeping timestamps would make the computer at least twice as slow. I
内存加载和存储操作应该非常快。 真的有必要去掉这些小操作吗？
在内存替换的情况下，从磁盘加载页面的开销应该比内存操作大很多。为什么实际上会关心内存存储和加载？
如果注释说的不对，那么用时间戳实现LRU的真正问题是什么？
编辑：
随着我深入挖掘，我能想到的原因如下。这些 内存存储和加载 操作在页面点击时发生。在这种情况下，我们没有从磁盘加载页面，因此比较无效。
由于预计命中率会很高，所以更新LRU相关的数据结构应该会很频繁。这就是为什么我们关心更新过程中重复的操作，例如内存加载和存储。
但是，我仍然不能说服进行内存加载和存储的开销有多大。周围应该有一些测量。有人可以指点我吗？谢谢！
内存加载和存储操作可能非常快，但在大多数现实生活中，内存子系统比 CPU 的执行引擎慢 - 有时慢得多。
内存访问时间的粗略数字：
- L1 缓存命中：2-4 CPU 周期
- L2 缓存命中：10-20 CPU 个周期
- L3 缓存命中：50 CPU 周期
- 主内存访问：100-200 CPU 周期
因此加载和存储需要实时时间。使用 LRU，每次常规内存访问也会产生内存存储操作的成本。仅此一项就使 CPU 的内存访问次数增加了一倍。在大多数情况下，这会减慢程序的执行速度。此外，在页面逐出时，需要读取所有时间戳。这会很慢。
此外，不断读取和存储时间戳意味着它们将在 L1 或 L2 缓存中占用 space。 Space在这些缓存中是有限的，因此您的其他访问的缓存未命中率可能会更高，这将花费更多时间。
简而言之 - LRU 相当昂贵。