JavaScript: LRU replacement with a Map
Use Map's insertion order to evict the least recently used page and count page faults.
On this page
JavaScript classes and Map.
- Use Map's insertion order to evict the least recently used page and count page faults.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
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.
Code example
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(" "));faults: 12 resident, oldest first: 7 0 1
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
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(" "));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
| Step / line | 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 |
Behind the scenes
How JavaScript processes this code
A JavaScript engine parses and runs the source. A function body runs when the function is called. console.log writes to the console.
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.