Implementing LRU with timestamp: How expensive is memory store and load?

Question

I'm talking about LRU memory page replacement algorithm implement in C, NOT in Java or C++.

According to the OS course 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

Memory load and store operation should be very fast. Is it really necessary to get rid of these little tiny operations?

In the case of memory replacement, the overhead of loading page from disk should be a lot more significant than memory operations. Why would actually care about memory store and load?

If what the notes said isn't correct, then what is the real problem with implementing LRU with timestamp?

EDIT:

As I dig deeper, the reason I can think of is like the following. These memory store and load operations happen when there is a page hit. In this case, we are not loading page from disks, so the comparison is not valid.

Since the hit rate is expected to be very high, so updating the data structure associated with LRU should be very frequent. That's why we care about the operations repeated in the udpate process, e.g., memory load and store.

But still, I'm not convincing how significant the overhead is to do memory load and store. There should be some measurements around. Can someone point me to them? Thanks!

Answer 1

Memory load and store operations can be quite fast, but in most real life cases the memory subsystem is slower - sometimes much slower - than the CPU's execution engine.

Rough numbers for memory access times:

• L1 cache hit: 2-4 CPU cycles
• L2 cache hit: 10-20 CPU cycles
• L3 cache hit: 50 CPU cycles
• Main memory access: 100-200 CPU cycles

So it costs real time to do loads and stores. With LRU, every regular memory access will also incur the cost of a memory store operation. This alone doubles the number of memory accesses the CPU does. In most situations this will slow the program execution. In addition, on a page eviction all the timestamps will need to be read. This will be quite slow.

In addition, reading and storing the timestamps constantly means they will be taking up space in the L1 or L2 caches. Space in these caches is limited, so your cache miss rate for other accesses will probably be higher, which will cost more time.

In short - LRU is quite expensive.