Cached Results

This is an example of a caching mechanism that I introduced into a page I wrote for some project.

Problem

At a certain point, during the development of a visual calculator, I noticed that the computation of results corresponding to moving sliders on the page had become much slower than before.

Solution

To mitigate the problem I introduced a caching mechanism based on:

  1. selecting slow methods, whose results we’re going to cache;
  2. wrapping those methods into a check:
    • if there is a cached result, use it
    • otherwise, compute it now, save it, then use it;
  3. deleting cached results as soon as they become stale.

A nice thing about this cache mechanism is that it’s standard.

  • We don’t need to change the code of the app.
  • A new cached result is computed only when unavailable.
  • Cached results become unavailable after certain events.

A nice thing of my implementation is that it automatically computes which cached values to invalidate, based on their dependencies lists.

  • This means that we only have to define the dependencies lists, which is very easy. Just look at the method’s definition and list all of its inputs (params, function calls, and contextual values).
    monthlyLoanProfitMoney(): number {
        const result = (this.totalInstalmentMoney() - this.loanAmountMoney.value) / this.loanDurationMonths();
        return result;
    }
    

    Dependencies: totalInstalmentMoney, loanAmountMoney, loanDurationMonths.

Code

import * as _ from 'lodash';

export class CachedResults {

  private cache: any = {};

  // private definitions: any = {
  //   // computed: [input1, input2, ...],
  // };

  private invalidations: any;

  static getPathsOfTheTransitiveClosure(edges) {
    // TODO check for dependency loops and throw an error
    const result = [];
    _.forEach(edges, edge => {
      let [from,] = edge;
      let path = [from];
      let found = edge;
      while (found) {
        let [, to] = found;
        path.push(to);
        found = edges.find(([x,]) => x === to);
      }
      result.push(path);
    });
    return result;
  }

  constructor(
    private definitions: any,
  ) {
    this.invalidations = this.getInvalidations();
  }

  use(methodName, fn) {
    if (!this.cache[methodName]) {
      this.cache[methodName] = fn(...args);
    }
    return this.cache[methodName];
  }

  invalidate(changed) {
    const invalidCache = this.invalidations[changed];
    invalidCache.forEach(x => { delete this.cache[x] });
  }

  private getInvalidations() {
    const arcs = this.getArcsFromInputToComputed();
    const paths = CachedResults.getPathsOfTheTransitiveClosure(arcs);
    return this.getPathsFromRoots(paths);
  }

  private getComputedValues() {
    return Object.keys(this.definitions);
  }

  private getArcsFromInputToComputed() {
    const result = [];
    _.forEach(this.definitions, (inputs, computed) => {
      _.forEach(inputs, input => {
        result.push([input, computed]);
      });
    });
    return result;
  }

  private getRootValues() {
    const allInputs = [];
    _.forEach(this.definitions, inputs => {
      allInputs.push(...inputs);
    });
    const computed = this.getComputedValues();
    const origins = _.difference(allInputs, computed);
    return _.uniq(origins);
  }

  private getPathsFromRoots(paths) {
    const roots = this.getRootValues();
    const result = {};
    roots.forEach(origin => {
      const path = paths.find(([x,]) => x === origin);
      const [, ...rest] = path;
      result[origin] = rest;
    });
    return result;
  }

}

Usage

import { CachedResults } from '...';
//...
cache: CachedResults;
//...
constructor() {
    this.cache = new CachedResults({
        loanDurationMonths: 'loanDurationYears'.split(' '),
        totalInstalmentMoney: 'loanDurationMonths monthlyInstalmentMoney'.split(' '),
        monthlyInstalmentMoney: 'annualPercentageRate loanDurationYears loanAmountMoney'.split(' '),
    });
}
//...
monthlyLoanProfitMoney(): number {
    return this.cache.use('monthlyLoanProfitMoney', () => {
        const result = (this.totalInstalmentMoney() - this.loanAmountMoney.value) / this.loanDurationMonths();
        return result;
    });
}
//...
<input id="loanDurationYears" type="range" min="5" max="30" step="1" (change)="cache.invalidate('loanDurationYears')" />

How to ´Promise.all´ the values of a JS hash

For doing something like this:

var hash = { key1: value1, key2: promise2, ... };
Promise.all(hash).then(hash => ...);

I wrote this little function:

  function promiseAll(hash) {
    const keys = Object.keys(hash);
    const values = keys.map(key => hash[key]);
    return Promise.all(values).then(resolved_values => {
      const resolved_hash = {};
      keys.forEach((key, index) => {
        resolved_hash[key] = resolved_values[index];
      });
      return resolved_hash;
    });
  }

which allows you to do this:

var hash = { key1: value1, key2: promise2, ... };
promiseAll(hash).then(hash => ...);

How to promise in Chrome extensions

The following setup of Message Passing for communicating JSON data from a content script to a popup script is pretty usual:

  chrome.runtime.onMessage.addListener(function (request, sender, sendResponse) {
    if (sender.tab) {
      return;
    }
    switch (request) {
    case 'selected_count':
      const count = selected_count();
      console.log('selected_count:', count);
      sendResponse({
        data: count
      });
      break;
    case 'selected_items':
      const items = selected_items();
      console.log('selected_items:', items);
      sendResponse({
        data: items
      });
      break;
    case 'unselect_all':
      unselect_all();
      break;
    }
  });

However, if some ´items´ contain data that you get asynchronously (like an image), then the setup above will fail if those data are not loaded before the handler returns.

Unfortunately, ´Promise´s are the right tool for the job in this case, but you can’t use them right away, because you can’t send a promise back to the popup and let it handle that, because a message can’t contain a promise, because

A message can contain any valid JSON object (null, boolean, number, string, array, or [my annotation: POJO] object).

Fortunately, according to the documentation,

If you want to asynchronously use ´sendResponse´, add ´return true;´ to the ´onMessage´ event handler.

which you can do like I show in the rewrite below, where I use a ´Promise´ object to take care of the asynchronous bits:

  chrome.runtime.onMessage.addListener(function (request, sender, sendResponse) {
    const KEEP_CHANNEL_OPEN = true;
    const CLOSE_CHANNEL = false;
    var result = CLOSE_CHANNEL;
    if (sender.tab) {
      return result;
    }
    switch (request) {
    case 'selected_count':
      const count = selected_count();
      console.log('selected_count:', count);
      sendResponse({
        data: count
      });
      break;
    case 'selected_items':
      selected_items().then(items => {
        console.log('selected_items:', items);
        sendResponse({
          data: items
        });
      });
      result = KEEP_CHANNEL_OPEN;
      break;
    case 'unselect_all':
      unselect_all();
      break;
    }
    return result;
  });