LRU Cache Perf Test

Benchmark created on October 31, 2024

Setup

class LRUNode {
	constructor(
		key,
		value,
		next,
		prev,
	) {
		this.key = key;
		this.value = value;
		this.next = next;
		this.prev = prev;
	}
}

class LRUCacheOld {
	//set default limit of 10 if limit is not passed.
	constructor(limit = 10) {
		this.size = 0;
		this.limit = limit;
		this.head = null;
		this.tail = null;
		this.cache = {};
	}

	// Write Node to head of LinkedList (i.e. this.head)
	// update cache with Node key and Node reference
	write(key, value) {
		this.ensureLimit();

		// If key already exists, remove it first so each key is
		// represented uniquely within the linked list
		if (this.cache[key]) {
			this.remove(key);
		}

		if (!this.head) {
			this.head = new LRUNode(key, value);
			this.tail = this.head;
		} else {
			const node = new LRUNode(key, value, this.head);
			this.head.prev = node;
			this.head = node;
		}

		// Update the cache map
		this.cache[key] = this.head;
		this.size += 1;
	}

	// Read from cache map and make that node as new Head of LinkedList
	read(key) {
		if (this.cache[key]) {
			const value = this.cache[key]?.value;

			// node removed from it's position and cache
			this.remove(key);
			// write node again to the head of LinkedList to make it most recently used
			this.write(key, value);

			return value;
		}
		return null;
	}

	// Convenience helper to read from cache map and retun a default if null
	readWithDefault(key, defaultCb) {
		const current = this.read(key);
		if (current !== null) return current;

		this.write(key, defaultCb(key));
		return this.read(key);
	}

	ensureLimit() {
		if (this.size === this.limit) {
			this.remove(this.tail?.key);
		}
	}

	remove(key) {
		const node = this.cache[key];
		if (!node) return;

		if (node.prev) {
			node.prev.next = node.next;
		} else {
			this.head = node.next;
		}

		if (node.next) {
			node.next.prev = node.prev;
		} else {
			this.tail = node.prev;
		}

		delete this.cache[key];
		this.size -= 1;
	}
}

class LRUCacheNew {
	constructor(limit = 10) {
		this.limit = limit;
		this.cache = new Map();
	}

	write(key, value) {
		if (this.cache.has(key)) {
			this.cache.delete(key);
		} else if (this.cache.size === this.limit) {
			// always delete entry from head (least recently used)
			const first = this.cache.keys().next().value;
			this.cache.delete(first);
		}

		this.cache.set(key, value);
	}

	read(key) {
		if (this.cache.has(key)) {
			const item = this.cache.get(key);
			// on successful read, re-insert entry at tail of map
			this.cache.delete(key);
			this.cache.set(key, item);
			return item;
		}
		return null;
	}

	// Convenience helper to read from cache map and return a default if null
	readWithDefault(key, defaultCb) {
		const current = this.read(key);
		if (current !== null) return current;

		this.write(key, defaultCb(key));
		return this.read(key);
	}

	remove(key) {
		this.cache.delete(key);
	}
}

var oldCache = new LRUCacheOld();
var newCache = new LRUCacheNew();

Test runner

for (let i = 0; i < 1000; i++) {
	oldCache.write(Math.round(Math.random() * 24), Math.random());
	oldCache.read(Math.round(Math.random()));
}

for (let i = 0; i < 1000; i++) {
	newCache.write(Math.round(Math.random() * 24), Math.random());
	newCache.read(Math.round(Math.random() * 24));
}

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 1: published on October 31, 2024