Weapon of Choice

This is an example of a caching mechanism that I added to an Angular 2+ page.

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;

1. 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).

escalivada(): number {
  return (this.escabeche() - this.gazpacho.value) / this.paella();
}

Dependencies: escabeche, gazpacho, paella.

Code

import * as _ from 'lodash';

export class CachedResults {

    private cache: any = {};

    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({
        paella: 'arrozNegre'.split(' '),
        escabeche: 'paella arrozCubana'.split(' '),
        arrozCubana: 'gachas arrozNegre gazpacho'.split(' '),
    });
}
//...
escalivada(): number {
    return this.cache.use('escalivada', () => {
        return (this.escabeche() - this.gazpacho.value) / this.paella();
    });
}
//...

<input id="arrozNegre" max="30" min="5" step="1" type="range" />