Highly Optimized in memory Cache with Data-Oriented Design

lruCache.js

export class LRUCache<K, V> {
  private readonly keys: K[];
  private readonly values: V[];
  private readonly accessOrder: number[]; // Index-based linked list
  private readonly keyToIndex = new Map<K, number>();
  private readonly maxSize: number;
  private head = 0;
  private tail = 0;
  private size = 0;
  private nextFreeIndex = 0;

  constructor(maxSize: number) {
    this.maxSize = Math.max(32, maxSize);

    // Pre-allocate arrays for better V8 optimization
    this.keys = new Array<K>(this.maxSize);
    this.values = new Array<V>(this.maxSize);
    this.accessOrder = new Array<number>(this.maxSize);

    // Initialize circular linked list indices
    for (let i = 0; i < this.maxSize; i++) {
      this.accessOrder[i] = (i + 1) % this.maxSize;
    }
  }

  get(key: K): V | undefined {
    const index = this.keyToIndex.get(key);
    if (index === undefined) return undefined;

    // Move to front (mark as most recently used)
    this.moveToFront(index);
    return this.values[index];
  }

  set(key: K, value: V): void {
    const existingIndex = this.keyToIndex.get(key);

    if (existingIndex !== undefined) {
      // Update existing entry
      this.values[existingIndex] = value;
      this.moveToFront(existingIndex);
      return;
    }

    let index: number;

    if (this.size < this.maxSize) {
      // Use next available slot
      index = this.nextFreeIndex++;
      this.size++;
    } else {
      // Evict least recently used
      index = this.tail;
      const oldKey = this.keys[index];
      this.keyToIndex.delete(oldKey);
      this.tail = this.accessOrder[this.tail];
    }

    this.keys[index] = key;
    this.values[index] = value;
    this.keyToIndex.set(key, index);
    this.moveToFront(index);
  }

  private moveToFront(index: number): void {
    if (index === this.head) return;

    // Remove from current position
    const prev = this.findPrevious(index);
    if (prev !== -1) {
      this.accessOrder[prev] = this.accessOrder[index];
    }
    if (index === this.tail) {
      this.tail = prev;
    }

    // Add to front
    this.accessOrder[index] = this.head;
    this.head = index;
  }

  private findPrevious(targetIndex: number): number {
    if (this.size <= 1) return -1;

    let current = this.head;
    while (current !== this.tail && this.accessOrder[current] !== targetIndex) {
      current = this.accessOrder[current];
    }

    return this.accessOrder[current] === targetIndex ? current : -1;
  }

  has(key: K): boolean {
    return this.keyToIndex.has(key);
  }

  delete(key: K): boolean {
    const index = this.keyToIndex.get(key);
    if (index === undefined) return false;

    this.keyToIndex.delete(key);

    // Remove from linked list
    const prev = this.findPrevious(index);
    if (prev !== -1) {
      this.accessOrder[prev] = this.accessOrder[index];
    }
    if (index === this.head) {
      this.head = this.accessOrder[index];
    }
    if (index === this.tail) {
      this.tail = prev;
    }

    this.size--;
    return true;
  }

  clear(): void {
    this.keyToIndex.clear();
    this.size = 0;
    this.nextFreeIndex = 0;
    this.head = 0;
    this.tail = 0;

    // Reset circular linked list
    for (let i = 0; i < this.maxSize; i++) {
      this.accessOrder[i] = (i + 1) % this.maxSize;
    }
  }

  // Fast iteration without allocating arrays
  forEach(callback: (value: V, key: K) => void): void {
    let current = this.head;
    let visited = 0;

    while (visited < this.size) {
      callback(this.values[current], this.keys[current]);
      current = this.accessOrder[current];
      visited++;
    }
  }

  get length(): number {
    return this.size;
  }
}