Bench Memoization

README.md

Memo-what?

Memoization is a technique for storing computed values in-memory. Essentially, it's a fancy name for in-memory cache.

Why Memoize?

Memoization is useful when you have potentially expensive or highly repetitive computations that need to be executed. Rather than re-running the computation on each iteration, your routine computes once and fetches already computed values from memory.

The example I've used in this benchmark is testing ISO date interval strings. Valid strings would have more variance than my test set, but you can see how memoization would be useful in cases like this where the result set is relatively fixed. In this case, a simple memoized match function is nearly six times as fast as JavaScript's built-in regular expression match, and three times faster than lodash's implementation.

> [email protected] bench /private/tmp/bench
> node ./index.js

SimpleMemoize#test x 6,102,561 ops/sec ±1.21% (92 runs sampled)
LodashMemoize#test x 1,810,809 ops/sec ±0.47% (96 runs sampled)
RegExp#test x 1,328,119 ops/sec ±0.42% (95 runs sampled)
Fastest is SimpleMemoize#test

Why Not Memoize?

The rules for when to and when not to memoize are the same as when and when not to cache, that is, a bit tricky. If the input to your memoized function is going to vary a lot, the chances of a "hit" are much lower. Therefore, the extra work to look up and store results may actually end up being slower than a non-memoized implementation. Speaking of storage, memoization is definitely not free! If the computed results are very large or highly variant, and your memoized function will reside in memory for the lifetime of your process you can run into resource exhaustion issues.

Additionally, memoization works best when the results of your operation do not need to be invalidated. That is, given an input, the output will always be the same. There are techniques for invalidation (lodash's implementation even has built-in support for this), but it does increase the complexity of what your application needs to manage.

Basic Implementation

As stated above, a memoized function works best when a given input always results in the same output. A simple implementation then follows these steps:

1. Does the store already have a value for this input? If yes, return value, else, continue.
2. Compute the value
3. Store the value
4. Return the value

In JavaScript, this could look like this:

const memoize = worker => {
  const memoMap = new Map();
  return i => {
    if (memoMap.has(i)) {
      return memoMap.get(i);
    }
    const res = worker(i);
    memoMap.set(i, res);
    return res;
  }
}

const double = memoize(i => i * 2);
double(1); // 2, computed
double(1); // 2, not computed

Try it out!

This gist can be used to demonstrate the benefits of memoization. Make sure you have node.js v12+ on your machine, then download the gist, run npm i then npm run bench.

index.js

const _ = require('lodash');
const Benchmark = require('benchmark');

const FISCAL_YEAR_RE = /^\d{4}-[01]\d-[0-3]\d\/\d{4}-[01]\d-[0-3]\d$/;
const intervals = ['01', '02', '03', '04', '05', '06', '07', '08', '09', '10', '11', '12'].map(m => `2020-${m}-01/2021-${m}-28`);
const matchFiscalYear = i => i.match(FISCAL_YEAR_RE);
const matchFiscalYearMemo = _.memoize(matchFiscalYear);

const memoize = worker => {
  const memoMap = new Map();
  return i => {
    if (memoMap.has(i)) {
      return memoMap.get(i);
    }
    const res = worker(i);
    memoMap.set(i, res);
    return res;
  }
}
const simpleMemo = memoize(matchFiscalYear);

const loop = test => intervals.forEach(int => test(int));

const suite = new Benchmark.Suite;
suite
  .add('SimpleMemoize#test', () => {
    loop(simpleMemo)
  })
  .add('LodashMemoize#test', () => {
    loop(matchFiscalYearMemo)
  })
  .add('RegExp#test', () => {
    loop(matchFiscalYear)
  })
  .on('cycle', e => console.log(String(e.target)))
  .on('complete', function () {
    console.log('Fastest is ' + this.filter('fastest').map('name'));
  })
  .run();

package.json

{
  "name": "bench-memoize",
  "version": "1.2.1",
  "description": "Example of effects of memoization",
  "main": "index.js",
  "dependencies": {
    "benchmark": "^2.1.4",
    "lodash": "^4.17.21"
  },
  "devDependencies": {},
  "scripts": {
    "bench": "node ./index.js",
    "test": "exit 0"
  },
  "author": "Elliott Foster <[email protected]>",
  "license": "MIT"
}