JavaScript: LRU replacement with a Map

Use Map's insertion order to evict the least recently used page and count page faults.

JavaScript

class LruMemory {
  constructor(frames) {
    this.frames = frames;
    this.pages = new Map();
    this.faults = 0;
  }

  access(page) {
    if (this.pages.has(page)) {
      this.pages.delete(page);
    } else {
      this.faults++;
      if (this.pages.size === this.frames) {
        const oldest = this.pages.keys().next().value;
        this.pages.delete(oldest);
      }
    }
    this.pages.set(page, true);
  }
}

const refs = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1];
const memory = new LruMemory(3);
for (const page of refs) {
  memory.access(page);
}
console.log("faults: " + memory.faults);
console.log("resident, oldest first: " + [...memory.pages.keys()].join(" "));

Output

faults: 12
resident, oldest first: 7 0 1

Explanation

When memory is full, a cache or an operating system must evict something. Least-recently-used (LRU) evicts the item that has gone unused the longest, on the assumption that recent use predicts future use. Each access either hits a resident page or causes a page fault.

A JavaScript Map iterates its keys in insertion order. On every access the page is deleted and inserted again, which moves it to the end, so the first key is always the least recently used. Evicting means deleting map.keys().next().value. With 3 frames, the classic reference string below causes 12 page faults.

Explore the dry run

Guided walkthroughReady

1class LruMemory {

2 constructor(frames) {

3 this.frames = frames;

4 this.pages = new Map();

5 this.faults = 0;

6 }

8 access(page) {

9 if (this.pages.has(page)) {

10 this.pages.delete(page);

11 } else {

12 this.faults++;

13 if (this.pages.size === this.frames) {

14 const oldest = this.pages.keys().next().value;

15 this.pages.delete(oldest);

16 }

17 }

18 this.pages.set(page, true);

19 }

20}

22const refs = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1];

23const memory = new LruMemory(3);

24for (const page of refs) {

25 memory.access(page);

26}

27console.log("faults: " + memory.faults);

28console.log("resident, oldest first: " + [...memory.pages.keys()].join(" "));

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
A hit: remove the page so it can be re-inserted as the most recent.	`—`	—
A fault with full memory: the first key is the least recently used page.	`—`	—
Insert at the end, marking the page as the most recently used.	`—`	—
This reference string causes 12 faults with 3 frames.	`faults = 12`	faults: 12
The last three distinct pages used were 7, 0, and 1.	`faults = 12`	faults: 12 resident, oldest first: 7 0 1

Cost and common mistakes

Each access is O(1) on average.

Real operating systems cannot afford to reorder a structure on every memory access. They approximate LRU with reference bits.
Sequential scans larger than memory defeat LRU, because every access is a fault. Some caches use other policies for scan-heavy workloads.

Try it yourself

How many faults would FIFO with 3 frames have on this string?

Reveal answer and reasoning

15 faults, so LRU is better here.

JavaScript: LRU replacement with a Map

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading