JavaScript Memoization: Optimization Through Caching

Memoization is an optimization technique that speeds up function execution by caching the results of expensive function calls and returning the cached result when the same inputs occur again. It's particularly useful for functions with expensive computations or recursive algorithms.

What is Memoization?

Memoization is a specific form of caching that involves storing the results of function calls. When a memoized function is called with the same arguments, it returns the cached result instead of recalculating it.

// Without memoization
function expensiveOperation(n) {
  console.log(`Computing for ${n}`);
  // Simulate expensive computation
  let result = 0;
  for (let i = 0; i < n * 1000000; i++) {
    result += Math.random();
  }
  return result;
}

// Multiple calls recalculate each time
console.time('without memo');
expensiveOperation(50);
expensiveOperation(50); // Recalculates
expensiveOperation(50); // Recalculates again
console.timeEnd('without memo');

// With memoization
function memoize(fn) {
  const cache = new Map();

  return function (...args) {
    const key = JSON.stringify(args);

    if (cache.has(key)) {
      console.log(`Returning cached result for ${args}`);
      return cache.get(key);
    }

    console.log(`Computing for ${args}`);
    const result = fn.apply(this, args);
    cache.set(key, result);

    return result;
  };
}

const memoizedExpensive = memoize(expensiveOperation);

console.time('with memo');
memoizedExpensive(50);
memoizedExpensive(50); // Returns cached result
memoizedExpensive(50); // Returns cached result
console.timeEnd('with memo');

How Memoization Works

Basic Implementation

// Simple memoization for single argument functions
function simpleMemoize(fn) {
  const cache = {};

  return function (arg) {
    if (arg in cache) {
      return cache[arg];
    }

    const result = fn(arg);
    cache[arg] = result;
    return result;
  };
}

// Example: Factorial
const factorial = simpleMemoize(function (n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
});

console.log(factorial(5)); // Computes: 120
console.log(factorial(5)); // From cache: 120
console.log(factorial(6)); // Computes using cached factorial(5): 720

Multiple Arguments

// Memoization for multiple arguments
function memoizeMultipleArgs(fn) {
  const cache = new Map();

  return function (...args) {
    // Create a unique key for the arguments
    const key = args
      .map((arg) => {
        if (typeof arg === 'object') {
          return JSON.stringify(arg);
        }
        return String(arg);
      })
      .join('|');

    if (cache.has(key)) {
      return cache.get(key);
    }

    const result = fn.apply(this, args);
    cache.set(key, result);

    return result;
  };
}

// Example: Distance calculation
const distance = memoizeMultipleArgs((x1, y1, x2, y2) => {
  console.log(`Calculating distance between (${x1},${y1}) and (${x2},${y2})`);
  return Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
});

console.log(distance(0, 0, 3, 4)); // Calculates: 5
console.log(distance(0, 0, 3, 4)); // From cache: 5

Custom Key Generation

// Memoization with custom key generator
function memoizeWithKeyGen(fn, keyGenerator) {
  const cache = new Map();

  return function (...args) {
    const key = keyGenerator ? keyGenerator(...args) : JSON.stringify(args);

    if (cache.has(key)) {
      return cache.get(key);
    }

    const result = fn.apply(this, args);
    cache.set(key, result);

    return result;
  };
}

// Example: Memoizing with object arguments
const processUser = memoizeWithKeyGen(
  (user) => {
    console.log(`Processing user: ${user.name}`);
    // Expensive user processing
    return {
      ...user,
      processed: true,
      score: Math.random() * 100,
    };
  },
  // Custom key generator - only use id for caching
  (user) => user.id
);

const user1 = { id: 1, name: 'John', age: 30 };
const user2 = { id: 1, name: 'John', age: 31 }; // Same id, different age

console.log(processUser(user1)); // Processes
console.log(processUser(user2)); // Returns cached (same id)

Advanced Memoization Patterns

1. LRU (Least Recently Used) Cache

class LRUCache {
  constructor(maxSize = 10) {
    this.maxSize = maxSize;
    this.cache = new Map();
  }

  get(key) {
    if (!this.cache.has(key)) {
      return undefined;
    }

    // Move to end (most recently used)
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value);

    return value;
  }

  set(key, value) {
    // Remove if exists (to update position)
    if (this.cache.has(key)) {
      this.cache.delete(key);
    }

    // Add to end
    this.cache.set(key, value);

    // Remove oldest if over capacity
    if (this.cache.size > this.maxSize) {
      const firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey);
    }
  }

  has(key) {
    return this.cache.has(key);
  }
}

function memoizeWithLRU(fn, maxSize = 10) {
  const cache = new LRUCache(maxSize);

  return function (...args) {
    const key = JSON.stringify(args);

    if (cache.has(key)) {
      return cache.get(key);
    }

    const result = fn.apply(this, args);
    cache.set(key, result);

    return result;
  };
}

// Example usage
const fibonacci = memoizeWithLRU((n) => {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}, 100);

// Only keeps last 100 results in cache

2. Time-based Expiration

function memoizeWithTTL(fn, ttl = 60000) {
  // Default 1 minute
  const cache = new Map();

  return function (...args) {
    const key = JSON.stringify(args);
    const cached = cache.get(key);

    if (cached && Date.now() - cached.timestamp < ttl) {
      console.log(
        `Returning cached result (age: ${Date.now() - cached.timestamp}ms)`
      );
      return cached.value;
    }

    console.log('Computing fresh result');
    const result = fn.apply(this, args);

    cache.set(key, {
      value: result,
      timestamp: Date.now(),
    });

    return result;
  };
}

// Example: API call caching
const fetchUserData = memoizeWithTTL(async (userId) => {
  console.log(`Fetching data for user ${userId}`);
  const response = await fetch(`/api/users/${userId}`);
  return response.json();
}, 30000); // Cache for 30 seconds

// First call fetches from API
await fetchUserData(123);

// Within 30 seconds, returns cached data
await fetchUserData(123);

// After 30 seconds, fetches fresh data
setTimeout(async () => {
  await fetchUserData(123);
}, 31000);

3. Weak Memoization

// Using WeakMap for object arguments
function weakMemoize(fn) {
  const cache = new WeakMap();

  return function (obj) {
    if (cache.has(obj)) {
      return cache.get(obj);
    }

    const result = fn.call(this, obj);
    cache.set(obj, result);

    return result;
  };
}

// Example: DOM element processing
const getElementData = weakMemoize((element) => {
  console.log('Processing element:', element.tagName);

  return {
    tag: element.tagName,
    classes: Array.from(element.classList),
    bounds: element.getBoundingClientRect(),
    children: element.children.length,
  };
});

// Cache is automatically cleaned when elements are removed from DOM
const div = document.createElement('div');
console.log(getElementData(div)); // Processes
console.log(getElementData(div)); // From cache

// When div is garbage collected, cache entry is also removed

4. Async Memoization

function memoizeAsync(fn) {
  const cache = new Map();
  const pending = new Map();

  return async function (...args) {
    const key = JSON.stringify(args);

    // Return cached result if available
    if (cache.has(key)) {
      return cache.get(key);
    }

    // Return pending promise if already fetching
    if (pending.has(key)) {
      return pending.get(key);
    }

    // Create new promise
    const promise = fn
      .apply(this, args)
      .then((result) => {
        cache.set(key, result);
        pending.delete(key);
        return result;
      })
      .catch((error) => {
        pending.delete(key);
        throw error;
      });

    pending.set(key, promise);
    return promise;
  };
}

// Example: Preventing duplicate API calls
const fetchData = memoizeAsync(async (endpoint) => {
  console.log(`Fetching ${endpoint}`);
  const response = await fetch(endpoint);
  return response.json();
});

// Multiple simultaneous calls only result in one fetch
Promise.all([
  fetchData('/api/data'),
  fetchData('/api/data'),
  fetchData('/api/data'),
]).then((results) => {
  console.log('All results:', results);
});

Practical Examples

1. Fibonacci Sequence

// Without memoization - exponential time complexity
function fibonacciSlow(n) {
  if (n <= 1) return n;
  return fibonacciSlow(n - 1) + fibonacciSlow(n - 2);
}

// With memoization - linear time complexity
const fibonacciMemo = (function () {
  const cache = new Map();

  return function fib(n) {
    if (cache.has(n)) {
      return cache.get(n);
    }

    let result;
    if (n <= 1) {
      result = n;
    } else {
      result = fib(n - 1) + fib(n - 2);
    }

    cache.set(n, result);
    return result;
  };
})();

console.time('slow');
console.log(fibonacciSlow(40)); // Takes several seconds
console.timeEnd('slow');

console.time('memoized');
console.log(fibonacciMemo(40)); // Instant
console.timeEnd('memoized');

2. Dynamic Programming

// Longest common subsequence with memoization
function longestCommonSubsequence(str1, str2) {
  const memo = new Map();

  function lcs(i, j) {
    // Base case
    if (i === str1.length || j === str2.length) {
      return 0;
    }

    // Check memo
    const key = `${i},${j}`;
    if (memo.has(key)) {
      return memo.get(key);
    }

    let result;
    if (str1[i] === str2[j]) {
      result = 1 + lcs(i + 1, j + 1);
    } else {
      result = Math.max(lcs(i + 1, j), lcs(i, j + 1));
    }

    memo.set(key, result);
    return result;
  }

  return lcs(0, 0);
}

console.log(longestCommonSubsequence('ABCDGH', 'AEDFHR')); // 3 (ADH)

// Knapsack problem with memoization
function knapsack(items, capacity) {
  const memo = new Map();

  function solve(i, remainingCapacity) {
    // Base case
    if (i >= items.length || remainingCapacity <= 0) {
      return 0;
    }

    // Check memo
    const key = `${i},${remainingCapacity}`;
    if (memo.has(key)) {
      return memo.get(key);
    }

    // Skip current item
    let result = solve(i + 1, remainingCapacity);

    // Include current item if it fits
    if (items[i].weight <= remainingCapacity) {
      result = Math.max(
        result,
        items[i].value + solve(i + 1, remainingCapacity - items[i].weight)
      );
    }

    memo.set(key, result);
    return result;
  }

  return solve(0, capacity);
}

const items = [
  { weight: 10, value: 60 },
  { weight: 20, value: 100 },
  { weight: 30, value: 120 },
];

console.log(knapsack(items, 50)); // 220

3. React Component Memoization

// Memoizing expensive computations in React
import React, { useMemo, useCallback } from 'react';

// Custom hook for memoization
function useMemoizedValue(computeFn, deps) {
  const cache = React.useRef(new Map());

  return useMemo(() => {
    const key = JSON.stringify(deps);

    if (cache.current.has(key)) {
      return cache.current.get(key);
    }

    const result = computeFn();
    cache.current.set(key, result);

    return result;
  }, deps);
}

// Component example
function ExpensiveComponent({ data, filter }) {
  // Memoize filtered results
  const filteredData = useMemo(() => {
    console.log('Filtering data...');
    return data.filter((item) => item.includes(filter));
  }, [data, filter]);

  // Memoize callback
  const handleClick = useCallback((item) => {
    console.log('Clicked:', item);
  }, []);

  // Custom memoization for complex computation
  const analysis = useMemoizedValue(() => {
    console.log('Analyzing data...');
    return {
      total: filteredData.length,
      average:
        filteredData.reduce((a, b) => a + b.length, 0) / filteredData.length,
    };
  }, [filteredData]);

  return (
    <div>
      <h3>
        Analysis: {analysis.total} items, avg length: {analysis.average}
      </h3>
      {filteredData.map((item) => (
        <div key={item} onClick={() => handleClick(item)}>
          {item}
        </div>
      ))}
    </div>
  );
}

// React.memo for component memoization
const MemoizedComponent = React.memo(
  ExpensiveComponent,
  (prevProps, nextProps) => {
    // Custom comparison function
    return (
      prevProps.data === nextProps.data && prevProps.filter === nextProps.filter
    );
  }
);

4. API Response Caching

class APICache {
  constructor(defaultTTL = 300000) {
    // 5 minutes default
    this.cache = new Map();
    this.defaultTTL = defaultTTL;
  }

  async fetch(url, options = {}, ttl = this.defaultTTL) {
    const key = this.generateKey(url, options);
    const cached = this.cache.get(key);

    // Check if cached and not expired
    if (cached && Date.now() - cached.timestamp < ttl) {
      console.log(`Cache hit for ${url}`);
      return cached.data;
    }

    console.log(`Cache miss for ${url}`);

    try {
      const response = await fetch(url, options);
      const data = await response.json();

      // Cache the successful response
      this.cache.set(key, {
        data,
        timestamp: Date.now(),
      });

      // Clean old entries periodically
      this.cleanOldEntries();

      return data;
    } catch (error) {
      // Return cached data even if expired on error
      if (cached) {
        console.log('Returning stale cache due to error');
        return cached.data;
      }
      throw error;
    }
  }

  generateKey(url, options) {
    return `${options.method || 'GET'}:${url}:${JSON.stringify(options.body || {})}`;
  }

  cleanOldEntries() {
    const now = Date.now();
    for (const [key, value] of this.cache.entries()) {
      if (now - value.timestamp > this.defaultTTL * 2) {
        this.cache.delete(key);
      }
    }
  }

  invalidate(pattern) {
    for (const key of this.cache.keys()) {
      if (key.includes(pattern)) {
        this.cache.delete(key);
      }
    }
  }
}

// Usage
const apiCache = new APICache();

// First call fetches from network
await apiCache.fetch('/api/users');

// Subsequent calls within 5 minutes return cached data
await apiCache.fetch('/api/users');

// Invalidate specific cache entries
apiCache.invalidate('/api/users');

Performance Considerations

1. Memory Usage

// Monitor cache size
function memoizeWithSizeLimit(fn, maxSize = 1000) {
  let cache = new Map();
  let accessCount = new Map();

  return function (...args) {
    const key = JSON.stringify(args);

    if (cache.has(key)) {
      // Track access frequency
      accessCount.set(key, (accessCount.get(key) || 0) + 1);
      return cache.get(key);
    }

    const result = fn.apply(this, args);

    // Add to cache
    cache.set(key, result);
    accessCount.set(key, 1);

    // Evict least frequently used if over limit
    if (cache.size > maxSize) {
      let minAccess = Infinity;
      let evictKey = null;

      for (const [k, count] of accessCount.entries()) {
        if (count < minAccess) {
          minAccess = count;
          evictKey = k;
        }
      }

      if (evictKey) {
        cache.delete(evictKey);
        accessCount.delete(evictKey);
      }
    }

    return result;
  };
}

// Memory-efficient memoization for large datasets
function memoizeSelective(fn, shouldCache) {
  const cache = new Map();

  return function (...args) {
    const key = JSON.stringify(args);

    if (cache.has(key)) {
      return cache.get(key);
    }

    const result = fn.apply(this, args);

    // Only cache if it meets criteria
    if (shouldCache(args, result)) {
      cache.set(key, result);
    }

    return result;
  };
}

// Example: Only cache expensive computations
const compute = memoizeSelective(
  (n) => {
    const start = performance.now();
    let result = 0;
    for (let i = 0; i < n * 1000000; i++) {
      result += Math.random();
    }
    const duration = performance.now() - start;
    return { result, duration };
  },
  (args, result) => result.duration > 100 // Only cache if took > 100ms
);

2. Cache Invalidation

class MemoizedFunction {
  constructor(fn) {
    this.fn = fn;
    this.cache = new Map();
  }

  call(...args) {
    const key = JSON.stringify(args);

    if (this.cache.has(key)) {
      return this.cache.get(key);
    }

    const result = this.fn(...args);
    this.cache.set(key, result);

    return result;
  }

  invalidate(...args) {
    if (args.length === 0) {
      // Clear entire cache
      this.cache.clear();
    } else {
      // Clear specific entry
      const key = JSON.stringify(args);
      this.cache.delete(key);
    }
  }

  invalidateMatching(predicate) {
    for (const [key, value] of this.cache.entries()) {
      const args = JSON.parse(key);
      if (predicate(args, value)) {
        this.cache.delete(key);
      }
    }
  }
}

// Usage
const memoizedCalc = new MemoizedFunction((x, y) => {
  console.log(`Computing ${x} + ${y}`);
  return x + y;
});

console.log(memoizedCalc.call(1, 2)); // Computes
console.log(memoizedCalc.call(1, 2)); // From cache

memoizedCalc.invalidate(1, 2); // Clear specific
console.log(memoizedCalc.call(1, 2)); // Recomputes

memoizedCalc.invalidateMatching((args) => args[0] === 1); // Clear all with x=1

When to Use Memoization

Good Use Cases

// 1. Pure functions with expensive computations
const isPrime = memoize((n) => {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 === 0 || n % 3 === 0) return false;

  for (let i = 5; i * i <= n; i += 6) {
    if (n % i === 0 || n % (i + 2) === 0) return false;
  }

  return true;
});

// 2. Recursive algorithms
const editDistance = memoize((str1, str2, i = 0, j = 0) => {
  if (i === str1.length) return str2.length - j;
  if (j === str2.length) return str1.length - i;

  if (str1[i] === str2[j]) {
    return editDistance(str1, str2, i + 1, j + 1);
  }

  return (
    1 +
    Math.min(
      editDistance(str1, str2, i + 1, j), // Delete
      editDistance(str1, str2, i, j + 1), // Insert
      editDistance(str1, str2, i + 1, j + 1) // Replace
    )
  );
});

// 3. API calls with stable responses
const getUserProfile = memoizeWithTTL(async (userId) => {
  const response = await fetch(`/api/users/${userId}`);
  return response.json();
}, 300000); // 5 minute cache

When to Avoid

// 1. Functions with side effects
// DON'T memoize this
function updateDatabase(data) {
  database.save(data);
  return { success: true };
}

// 2. Functions that depend on external state
// DON'T memoize this
function getCurrentTime() {
  return new Date();
}

// 3. Functions with large inputs/outputs
// Be careful with memory usage
function processLargeDataset(data) {
  // If data is very large, caching might use too much memory
  return data.map(complexTransformation);
}

// 4. Frequently changing data
// Consider TTL or don't memoize
function getStockPrice(symbol) {
  // Changes every second - memoization not helpful
  return fetchRealtimePrice(symbol);
}

Best Practices

1. Choose the Right Cache Key

// Bad: Inefficient key for objects
const badMemoize = memoize((obj) => {
  return obj.value * 2;
});

// Good: Extract relevant properties
const goodMemoize = memoize(
  (obj) => {
    return obj.value * 2;
  },
  (obj) => obj.value
); // Custom key extractor

// Better: Design functions to accept primitives
const betterFunction = memoize((value) => {
  return value * 2;
});

2. Monitor Cache Performance

function memoizeWithStats(fn) {
  const cache = new Map();
  let hits = 0;
  let misses = 0;

  const memoized = function (...args) {
    const key = JSON.stringify(args);

    if (cache.has(key)) {
      hits++;
      return cache.get(key);
    }

    misses++;
    const result = fn.apply(this, args);
    cache.set(key, result);

    return result;
  };

  memoized.stats = () => ({
    hits,
    misses,
    hitRate: hits / (hits + misses),
    cacheSize: cache.size,
  });

  memoized.clearCache = () => {
    cache.clear();
    hits = 0;
    misses = 0;
  };

  return memoized;
}

// Usage
const memoizedFn = memoizeWithStats(expensiveOperation);

// Use the function
memoizedFn(1);
memoizedFn(1);
memoizedFn(2);

console.log(memoizedFn.stats());
// { hits: 1, misses: 2, hitRate: 0.33, cacheSize: 2 }

3. Test Memoized Functions

// Test that memoization doesn't change behavior
function testMemoization(fn, memoizedFn, testCases) {
  for (const args of testCases) {
    const expected = fn(...args);
    const actual = memoizedFn(...args);

    console.assert(
      JSON.stringify(expected) === JSON.stringify(actual),
      `Mismatch for args ${args}: expected ${expected}, got ${actual}`
    );

    // Test that second call returns same result
    const cached = memoizedFn(...args);
    console.assert(
      JSON.stringify(actual) === JSON.stringify(cached),
      `Cache inconsistency for args ${args}`
    );
  }
}

// Test cache behavior
function testCacheInvalidation(memoizedFn) {
  const result1 = memoizedFn(1);
  const result2 = memoizedFn(1);

  console.assert(result1 === result2, 'Should return cached result');

  if (memoizedFn.clearCache) {
    memoizedFn.clearCache();
    const result3 = memoizedFn(1);
    console.assert(
      result1 === result3,
      'Should return same value after cache clear'
    );
  }
}

Conclusion

Memoization is a powerful optimization technique that can significantly improve performance by caching function results. Key benefits include:

• Performance improvement for expensive computations
• Reduced API calls and network requests
• Optimization of recursive algorithms
• Better user experience through faster responses

Important considerations:

• Only memoize pure functions without side effects
• Be mindful of memory usage and implement eviction strategies
• Consider cache invalidation requirements
• Use appropriate cache key generation strategies
• Monitor cache hit rates and effectiveness

Best practices:

• Start with simple memoization and add complexity as needed
• Use WeakMap for object arguments when appropriate
• Implement TTL for time-sensitive data
• Consider LRU or other eviction strategies for bounded caches
• Test both correctness and performance improvements

Memoization is an essential tool in the performance optimization toolkit. Use it wisely to create faster, more efficient JavaScript applications!