memoize-the-practical-method-decorator.md

Memoized, the practical method decorator

In computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs.

In other words, if you calculate something, save the result. The next time you need to perform the same calculation, you just look it up. This applies to any algorithm, and many time we can use it with methods on an object.

Let's start with a naive fibonacci algorithm in CoffeeScript:

fibonacci = (n) ->
  if n < 2
    n
  else
    fibonacci(n-2) + fibonacci(n-1)

Since this is a post about method decorators, we'll gratuitously rewrite this function into an object with a helper method:

class Fibonacci

  constructor: (@n) ->
  
  toInt: ->
    @fibonacci(@n)
  
  fibonacci:
    (n) ->
      if n < 2
        n
      else
        @fibonacci(n-2) + @fibonacci(n-1)

And we'll time it:

coffee> s = (new Date()).getTime(); new Fibonacci(45).toInt(); ( (new Date()).getTime() - s ) / 1000
28.565

Yecch! There are other, faster and more interesting algorithms, of course. But this one is good precisely because it is almost maximally pessimum: Computing fibonacci(n - 2) is going to require computing fibonacci(n - 3). Having done this, it computes fibonacci(n - 1). But of course, computing fibonacci(n - 1) is going to require computing fibonacci(n - 2) and fibonacci(n - 3), ignoring the work it has already done!

We can easily rewrite the algorithm in another form that doesn't do the same work twice, but let's stick with it and see what we get from memoization.

Introducing memoized, our method decorator

Time to write a memoization decorator! If you aren't familiar with method decorators, Method Combinators in CoffeeScript explains that a method decorator is a function that adds functionality to a method. We're going to write one that memoizes the result of our fibonacci helper, this time in JavaScript:

memoized = function(methodBody) {
  var memos;
  memos = {};
  return function() {
    var key;
    key = JSON.stringify(arguments);
    if (memos.hasOwnProperty(key)) { 
      return memos[key];
    } else {
      return memos[key] = methodBody.apply(this, arguments);
    }
  };
};

Our decorator is a little limited: It can only handle methods that take zero or more arguments, each of which must be amenable to JSON.stringify. It works perfectly for our example, but you can build something more robust if you need more flexibility.

Let's redo our class to use it:

FastFibonacci = (function() {

  function FastFibonacci(n) {
    this.n = n;
  }

  FastFibonacci.prototype.toInt = function() {
    return this.fibonacci(this.n);
  };

  FastFibonacci.prototype.fibonacci = memoized(
    function(n) {
      if (n < 2) {
        return n;
      } else {
        return this.fibonacci(n - 2) + this.fibonacci(n - 1);
      }
    }
  );

  return FastFibonacci;

})();

And we'll time it again:

js> s = (new Date()).getTime(); new FastFibonacci(45).toInt(); ( (new Date()).getTime() - s ) / 1000
0.001

That makes quite the difference! Memoization isn't limited to mathematical computations or recursive algorithms. If you are careful about preserving idempotence, memoization can be used to save superfluous database lookups, AJAX calls and almost anything else that takes time to resolve.

What does a decorator get us?

The memoized decorator is quite handy. We can memoize any method we like with a single label. We don't have to write something like this CoffeeScript snippet:

  fibonacci:
    do ->
      memos = {}
      (n) ->
        memos[n] ?= if n < 2
                      n
                    else
                      @fibonacci(n-2) + @fibonacci(n-1)

This tangles the memoize implementation with the base logic of the fibonacci function, and it isn't reusable. And of course, it composes with other decorators we might use without tangling even more concerns and responsibilities in our code.

Sounds good, but memoized seems familiar...

Indeed it does. Jeremy Ashkenas' Underscore.js library has a memoize function that does this exact thing for any arbitrary function. It can also be used for methods.

What's that? Methods are functions, so anything that works with a function must necessarily work with a method? Not exactly. Anything that works with a function also works with a method that never refers to JavaScript's this pseudo-variable. And that's the case with our fibonacci helper method above. But once you start referring to this, method decorators will break your methods unless they preserve the correct receiver object. That's why our memoized decorator invokes .apply(this, arguments), to preserve the correct receiver. Perusing the source code for Underscore 1.3.1, we see that memoize preserves this and can be used as a method decorator:

_.memoize = function(func, hasher) {
    var memo = {};
    hasher || (hasher = _.identity);
    return function() {
      var key = hasher.apply(this, arguments);
      return _.has(memo, key) ? memo[key] : (memo[key] = func.apply(this, arguments));
    };
  };

Underscore provides other useful functions that act as method decorators. Both memoize and once can be used directly as decorators:

UnderscoreEg = (function() {

  function UnderscoreEg() {}

  UnderscoreEg.prototype.initialize = _.once(
    function() {
      // Initialization that must not be performed
      // more than once
    }
  );

  return UnderscoreEg;

})();

throttle and debounce have additional parameters you can handle with a little partial evaluation. Here's throttled in CoffeeScript:

throttled = 
  (milliseconds) ->
    (methodBody) ->
      _.throttle(methodBody, milliseconds)
    
class AnotherUnderscoreEg

  sayWhat:
    throttled(10000) \
    ->
      alert('What!?')

Summary

memoized is a practical method decorator you can use right away. If you use Underscore.js in your projects, you can use its _.memoize and _.once directly as decorators. You can also make method decorators out of _.throttle and _.debounce with partial evaluation.

More Reading

• npm install method-combinators
• Using Method Decorators to Decouple Code
• Understanding Python Decorators on StackOverflow
• Introduction to Python Decorators by Bruce Eckel
• Aspect-Oriented programming using Combinator Birds

---

My recent work:

• JavaScript Allongé, CoffeeScript Ristretto, and my other books.
• allong.es, practical function combinators and decorators for JavaScript.
• Method Combinators, a CoffeeScript/JavaScript library for writing method decorators, simply and easily.
• jQuery Combinators, what else? A jQuery plugin for writing your own fluent, jQuery-like code.

---

(Spot a bug or a spelling mistake? This is a Github repo, fork it and send me a pull request!)

Reg Braithwaite | @raganwald