Memoisation in JavaScript – Unbounded Cache Crashes

// A foundational memoisation utility using a Map for type-safe key storage.
// This version handles single-argument functions to keep the mechanics visible.

function memorise(expensiveFunction) {
  // The cache lives inside this closure — it persists across all future calls
  // to the returned memoisedFunction, but is invisible to the outside world.
  const resultCache = new Map();

  return function memoisedFunction(argument) {
    // Check whether we've already computed a result for this exact argument.
    if (resultCache.has(argument)) {
      console.log(`[CACHE HIT]  argument=${argument}`);
      return resultCache.get(argument); // Return the stored result immediately
    }

    console.log(`[CACHE MISS] argument=${argument} — computing now...`);

    // We haven't seen this argument before, so run the real function.
    const computedResult = expensiveFunction(argument);

    // Store the result so the next identical call skips this work entirely.
    resultCache.set(argument, computedResult);

    return computedResult;
  };
}

// Simulates an expensive calculation — in reality this could be a complex
// mathematical transform, a tree traversal, or a regex-heavy string parse.
function computeSquare(number) {
  return number * number;
}

const memoisedSquare = memorise(computeSquare);

console.log(memoisedSquare(6));  // First call — must compute
console.log(memoisedSquare(6));  // Second call — served from cache
console.log(memoisedSquare(9));  // New argument — must compute
console.log(memoisedSquare(6));  // Back to 6 — still in cache
console.log(memoisedSquare(9));  // 9 is now cached too

// Production-grade memoisation for functions with multiple arguments.
// Uses a null-byte separator for primitives and warns on object arguments.

function memorise(targetFunction) {
  const resultCache = new Map();

  return function memoisedFunction(...argumentList) {
    // Build a cache key from all arguments.
    // The null byte (\0) is used as a separator because it cannot appear
    // naturally in typical string arguments, minimising collision risk.
    const cacheKey = argumentList
      .map(arg => {
        if (arg !== null && typeof arg === 'object') {
          // Objects are serialised — note this won't handle circular refs.
          // For object-heavy use cases, prefer the trie approach instead.
          return JSON.stringify(arg);
        }
        return String(arg);
      })
      .join('\0');

    if (resultCache.has(cacheKey)) {
      return resultCache.get(cacheKey);
    }

    const result = targetFunction.apply(this, argumentList);
    resultCache.set(cacheKey, result);
    return result;
  };
}

// A function that blends two paint colours with a mixing ratio.
// Imagine this hits a real colour-science algorithm in production.
function blendColours(colourA, colourB, ratio) {
  // Simplified stand-in for a complex colour blend computation
  return `blend(${colourA}, ${colourB}, ratio=${ratio})`;
}

const memoisedBlend = memorise(blendColours);

// First calls — all cache misses, real work happens
console.log(memoisedBlend('red', 'blue', 0.5));
console.log(memoisedBlend('red', 'blue', 0.7));
console.log(memoisedBlend('red', 'blue', 0.5)); // Cache hit — same three args

// Demonstrates why argument ORDER matters for the key
console.log(memoisedBlend('blue', 'red', 0.5)); // Miss — different order

// Demonstrates the null-byte separator preventing collisions:
// Without it, ('a|b', 'c') and ('a', 'b|c') would collide.
const memoisedConcat = memorise((a, b) => `${a}+${b}`);
console.log(memoisedConcat('a|b', 'c'));  // key: 'a|b\0c'
console.log(memoisedConcat('a', 'b|c'));  // key: 'a\0b|c' — different, correct!

// Demonstrates the self-reference trap in recursive memoisation
// and shows both the broken and the correct pattern side by side.

// --- BROKEN PATTERN ---
// The recursive calls inside go to the original, un-memoised function.
function naiveFibonacci(n) {
  if (n <= 1) return n;
  return naiveFibonacci(n - 1) + naiveFibonacci(n - 2); // calls original!
}

function memorise(fn) {
  const cache = new Map();
  return function memoised(...args) {
    const key = args.join('\0');
    if (cache.has(key)) return cache.get(key);
    const result = fn.apply(this, args);
    cache.set(key, result);
    return result;
  };
}

// The outer call IS memoised, but sub-calls go to naiveFibonacci — no benefit.
const brokenMemoisedFib = memorise(naiveFibonacci);

// --- CORRECT PATTERN ---
// We declare the variable first, then assign it — so the function body
// can reference the memoised version of itself through the variable.
let fibonacci;
fibonacci = memorise(function(n) {
  if (n <= 1) return n;
  // 'fibonacci' here refers to the memoised wrapper, not the raw function.
  // This means every sub-problem call gets cached correctly.
  return fibonacci(n - 1) + fibonacci(n - 2);
});

// Track how many real computations happen to prove memoisation is working
let computationCount = 0;
fibonacci = memorise(function(n) {
  computationCount++;
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
});

const result = fibonacci(10);
console.log(`fibonacci(10) = ${result}`);
console.log(`Total computations performed: ${computationCount}`);
// Without memoisation this would compute 177 times for n=10.
// With correct recursive memoisation it computes exactly 11 times (0 through 10).

// Second call — should need ZERO new computations
computationCount = 0;
console.log(`fibonacci(10) again = ${fibonacci(10)}`);
console.log(`Computations on second call: ${computationCount}`);

// A memoisation utility with LRU eviction — safe for production use
// where the input space is large or unbounded.

function memoiseLRU(targetFunction, maxCacheSize = 100) {
  // We use a Map for the cache because Map preserves insertion order,
  // which makes implementing LRU eviction straightforward.
  const lruCache = new Map();

  return function memoisedWithLRU(...argumentList) {
    const cacheKey = argumentList.map(String).join('\0');

    if (lruCache.has(cacheKey)) {
      // LRU trick: delete and re-insert to move this entry to the end
      // (most recently used position) of the Map's iteration order.
      const cachedValue = lruCache.get(cacheKey);
      lruCache.delete(cacheKey);
      lruCache.set(cacheKey, cachedValue);
      return cachedValue;
    }

    const freshResult = targetFunction.apply(this, argumentList);

    // If we're at capacity, evict the least recently used entry.
    // Map.keys().next().value gives us the first (oldest) key in iteration order.
    if (lruCache.size >= maxCacheSize) {
      const oldestKey = lruCache.keys().next().value;
      lruCache.delete(oldestKey);
      console.log(`[LRU EVICT] Removed entry for key: "${oldestKey}"`);
    }

    lruCache.set(cacheKey, freshResult);
    return freshResult;
  };
}

// Simulate an expensive prime-check — in reality this could be a
// complex data transformation or a third-party library call.
function isPrime(num) {
  if (num < 2) return false;
  for (let divisor = 2; divisor <= Math.sqrt(num); divisor++) {
    if (num % divisor === 0) return false;
  }
  return true;
}

// Tiny cache of 3 to demonstrate eviction clearly
const memoisedIsPrime = memoiseLRU(isPrime, 3);

console.log(memoisedIsPrime(7));    // Miss — cache: [7]
console.log(memoisedIsPrime(11));   // Miss — cache: [7, 11]
console.log(memoisedIsPrime(13));   // Miss — cache: [7, 11, 13]
console.log(memoisedIsPrime(7));    // Hit — moves 7 to end: [11, 13, 7]
console.log(memoisedIsPrime(17));   // Miss, cache full — evicts 11: [13, 7, 17]
console.log(memoisedIsPrime(13));   // Hit — still in cache

// Quick benchmark to decide if memoisation is worth it for your function.

function memoise(fn) {
  const cache = new Map();
  return function(...args) {
    const key = args.join('\0');
    if (cache.has(key)) return cache.get(key);
    const result = fn.apply(this, args);
    cache.set(key, result);
    return result;
  };
}

// Example: an expensive regex validation (simulated)
function validateEmail(email) {
  // In reality this could be a complex regex or API call
  let result = 0;
  for (let i = 0; i < email.length; i++) {
    result += email.charCodeAt(i);
  }
  return result;
}

const memoisedValidate = memoise(validateEmail);

function benchmark(label, fn, argsList) {
  const start = performance.now();
  for (const args of argsList) {
    fn(...args);
  }
  const end = performance.now();
  console.log(`${label}: ${(end - start).toFixed(2)}ms for ${argsList.length} calls`);
}

// Generate 100 unique emails
const uniqueEmails = Array.from({ length: 100 }, (_, i) => `user${i}@example.com`);
const singleEmail = ['test@example.com'];

// Benchmark unique calls (all misses)
benchmark('Un-memoised (unique)', validateEmail, uniqueEmails.map(e => [e]));
benchmark('Memoised (unique)', memoisedValidate, uniqueEmails.map(e => [e]));

// Benchmark repeated calls (all hits after first)
benchmark('Un-memoised (repeated)', validateEmail, Array(100).fill(singleEmail));
benchmark('Memoised (repeated)', memoisedValidate, Array(100).fill(singleEmail));

// Sample output may vary by engine:
// Un-memoised (unique): 0.15ms for 100 calls
// Memoised (unique): 0.25ms for 100 calls (overhead)
// Un-memoised (repeated): 0.12ms for 100 calls
// Memoised (repeated): 0.02ms for 100 calls (6x faster)