WeakMap + Redux

weakmap_redux.md

Combining Weakmap + Redux for fun and profit.

Scenario

Lets say we have a large Redux State object which looks like this...

interface State {
  stockMarketData: {
    [stockTicker: string]: {
      name: string;
      // very long array of observations
      priceHistory: {
        value: number,
        date: Date
      }[]
    }
  },
  ...otherProps
}

And I want to find the maximum value across all stocks for some reason. Assuming I can't change my data structure (better choice), I come up with a function to compute the max.

function getMaxValue(stockMarketData: State['stockMarketData']) {
  let max = -Infinity;
  for (const ticker in stockMarketData) {
    const data = stockMarketData[ticker];
    for (const observation of data.priceHistory) {
      if (observation.value > max) {
        max = observation.value;
      }
    }
  }
  return max;
}

This is all fun and dandy until I realize that this function gets called in lots of components across the app, and since it needs to walk over thousands of data points, starts to cause performance issues.

Memory issues with Map for object-keyed caches.

Since, we know that objects in redux will only change when a new value is set, we can rely on object references themselves for caching. However, using a traditional memoizing strategy like storing results in a Map presents problems.

For example, if we tried to use Map to cache our results...

// wrap a function with caching logic
// BAD: this will cause a memory leak!
function memoize<K extends {}, V>(fn: (key: K) => V) {
  const cache = new Map<K, V>(); // this will grow monotonically
  
  return (key: K) => {
    const cached = cache.get(key);
    if (cached) return cached;
    
    const value = fn(key);
    cache.set(key, value);
    
    return value;
  };
}

// memoized max function
const memoizedMax = memoize(getMaxValue);

We will quickly run into memory leak problems. This is due to the fact by setting cache.set(key, value), we have created a reference which blocks the garbage collector from removing value from the heap. This means that the cache will monotonically grow in memory size as the app is used.

WeakMap as a solution.

Fortunately, ES2015 WeakMaps can solve all our problems here. Re-writing memoize above with WeakMap instead of Map, we will no longer see memory leaks...

// GOOD: no more memory leaks!
function memoize<K extends {}, V>(fn: (key: K) => V) {
  const cache = new WeakMap<K, V>(); // does not prevent garbage collection
  
  return (key: K) => {
    const cached = cache.get(key);
    if (cached) return cached;
    
    const value = fn(key);
    cache.set(key, value);
    
    return value;
  };
}

Why does this work? What is the difference between Maps + WeakMaps?

In simplified terms, we can think of WeakMaps as using the object keys themselves to hold the data. For example, a (hacky, super basic) version of weakmaps could be implemented as...

class WeakMap<V> {
  constructor() {
    // use a symbol so they are different between instances.
    this.key = new Symbol('WeakMapKey'); 
  }
  
  set(keyObject: Object, value: V) {
    keyObject[this.key] = value;
  }
  
  get(keyObject: Object) {
    return keyObject[this.key];
  }
}

Since the map association is stored on the keyObjects themselves (as opposed to on the Map), keyObjects are free to be garbage collected. Therefore, we won't cause the same type of memory leaks faced by Maps.