Rich Object Models & Angular.js: Memoization

14 Mar 2014 Rich Object Models & Angular.js: Memoization

In my previous post on getter methods and Angular.js I showed how complex calculations can be hidden behind simple Javascript properties. One downside to this technique is that we can start to get a little blasé about when calculations are actually being executed. This can in-turn lead to performance issues.

In this post I’m going to talk about expensive calculations in rich object models – be they hidden behind getter methods or just regular methods – and how we can use memoization to reduce the impact that these calculations have on performance. Memoization isn’t something that you should use all the time, but for use-cases involving long chains of calculations it can be an effective optimization technique, especially within a framework like Angular.

If you don’t feel like reading, you can always jump to the part of my ng-conf presentation that covers memoization, or go straight to the Github project. Either way, I’m assuming that you’re familiar with the foundational concepts I introduced in the first post in this series.

An Example

Let’s continue with the example from my previous posts: calculating the cost, revenue and profit of a proposal to fit-out aircraft interiors:

angular.module('models').
  factory('Proposal', function(Base) {
    return Base.extend({
      get profit() {
        return this.revenue.minus(this.cost);
      },
      get revenue() {
        return this.price.
          convertTo(this.internalCurrency);
      },
      get cost() {
        this.recurringEngineering.cost.plus(
          this.nonRecurringEngineering.cost
        );
      },
      ...
    });
  });

Say that we want to display these values in a tabular format, as well as provide an input field that lets us change the number of aircraft that we are proposing to fit-out. Our template might look a bit like this:

...
<tr><td>Cost</td><td money="proposal.cost"></td></tr>
<tr><td>Revenue</td><td money="proposal.revenue"></td></tr>
<tr><td>Profit</td><td money="proposal.profit"></td></tr>
...
<tr>
  <td>Number of Aircraft</td>
  <td>
    <input type="number" 
      min="1" 
      ng-model="proposal.numberOfAircraft">
    </input>
  </td>
</tr>
...

Note that:

• We’re using a custom directive to display monetary values. This is really just to avoid code duplication – in each case we need to display both the currency and the amount.
• Although we’re using property notation to access the values, we could just as well be binding to method invocations. With getter methods it’s just a little easier to lose track of what’s actually being computed 🙂

By setting up two-way bindings, we can ensure that if the number of aircraft in the proposal is changed, then the cost, revenue and profit values will be updated automatically.

To guarantee that the correct updates happen, every time any sort of event is detected by Angular – be it from user input, an AJAX callback, or even a timer – it will execute a digest cycle.

Each digest cycle involves Angular repeatedly iterating over the watch list – which will include the proposal.cost, proposal.revenue and proposal.profit expressions – and re-evaluating these expressions until no changes are detected.

Furthermore, even during a single iteration over the watch list, evaluating some of these expressions will result in calculations being performed multiple times. For example, we display both the cost and the profit, but the cost is also used to calculate the profit. This effectively means that we’re calculating the cost twice.

Probably the most well-known rule of Angular performance optimisation is that your watch expressions should not take too long to evaluate. But in our case, as proposals grow larger – more parts, more cost items, etc – the calculation time will grow accordingly. We mightn’t be able to eliminate this time completely, but can we at least reduce the number of unnecessary calculations?

Introducing Memoization

Memoization is a well-known strategy for speeding up computation-expensive programs.

In the context of a language with functional roots like Javascript, memoization is when you wrap a function such that when it is invoked for the first time, the result of the invocation is stored. On subsequent calls, rather than re-invoking the original function, the stored value is returned immediately. Libraries like underscore.js and lodash provide memoization tools, or you can write your own.

Before memoizing methods on objects, there’s one key question we first have to ask: are the underlying calculations idempotent and will they have no side-effects during a digest cycle? In the case of our proposal calculations, this is indeed the case. For example, we’d expect the revenue to remain unchanged during multiple iterations over the watch-list during a single digest cycle.

So without any further ado I present the Base.memoize method – a declarative means to specify properties on an object whose values should be memoized. Here’s what it looks like in action:

angular.module('models').
  factory('Proposal', function(Base) {
    return Base.extend({
      memoize: ['revenue', 'cost', 'profit'],

      get profit() {
        return this.revenue.minus(this.cost);
      },
      get revenue() {
        return this.price.
          convertTo(this.internalCurrency);
      },
      get cost() {
        this.recurringEngineering.cost.plus(
          this.nonRecurringEngineering.cost
        );
      },
      ...
    });
  });

In this case, invocations of the profit, revenue and cost getter methods will be memoized. The implementation also handles calls to regular methods. However, if used on a regular method, it doesn’t pay any attention to method arguments – the same result will be returned on subsequent calls even if the arguments are different. Consequently, to avoid confusion it’s advisable to not memoize methods that take arguments.

Unmemoization

Memoization is great but you’re probably asking yourself at what point we actually clear any results that have been memoized. For example, if the user sets the number of aircraft once, then sets it again, we want the calculated values to be updated both times.

To support this, I’ve also introduced an unmemoize method to the Base mixin that will clear the cached values for any memoized methods, meaning that they will get recomputed the next time they are invoked.

How do we use it? Well the simplest way is to call it whenever the user triggers some action. For example, when they set the number of aircraft in the proposal:

...
<tr><td>Cost</td><td money="proposal.cost"</td></tr>
<tr><td>Revenue</td><td money="proposal.revenue"></td></tr>
<tr><td>Profit</td><td money="proposal.profit"></td></tr>
...
<tr>
  <td>Number of Aircraft</td>
  <td>
    <input type="number" 
      min="1" 
      ng-model="proposal.numberOfAircraft"
      ng-change="proposal.unmemoize()">
    </input>
  </td>
</tr>
...

This will clear any memoizations that we have in place on the proposal, meaning that the correct cost, revenue and profit will get displayed each time the user does something. However, within each digest cycle, the cost, revenue and profit will still be memoized.

Nested Unmemoization

The memoize declaration can be applied to any business object, not just proposals. For example, we could avoid expensive calculations on a NonRecurringEngineering object by memoizing the material and internal costs:

angular.module('models').
  factory('NonRecurringEngineering', function(Base, Money) {
    ... 
    return Base.extend({
      memoize: ['materialCost', 'internalCost'],
      ..
      materialCost: function() {
        return total(this.materialCostItems);
      },
      internalCost: function() {
        return total(this.internalCostItems);
      },
      ...
    });
  });

These calculations also need to be unmemoized, but having to explicitly do that to every memoized object in the tree of calculations wouldn’t be practical. Instead I’ve made it that, in addition to specifying method names in the memoize declaration, you can also specify the names of child objects that should be unmemoized along with the parent. For example:

angular.module('models').
  factory('Proposal', function(Base) {
    return Base.extend({
      memoize: ['revenue', 'cost', 'profit', 
        'recurringEngineering', 'nonRecurringEngineering'],

      get profit() {
        return this.revenue.minus(this.cost);
      },
      ...
    });
  });

This means that when you call unmemoize on a proposal, the recurringEngineering and nonRecurringEngineering properties will also be unmemoized. They in-turn will then clear any memoized children that they have.

It’s expected that any child object specified in memoize will have Base mixed into it and will thus also have a corresponding unmemoize method. An exception will be thrown at mixin time if this is not the case.

Automatic Unmemoization

If we had several points in our template where proposal.unmemoize() needed to be called, the code will get quite repetitive. Even worse, if we forgot to clear memoizations at a particular interaction point, it’s likely that we’d get unexpected and incorrect results being displayed.

Consequently, it’d be awesome if our controller could instead arrange for proposal memoizations to get cleared whenever a digest cycle is either starting or finishing.

Whilst it’s possible to get a notification for each iteration over the watch list simply by creating a watch listener without an expression, to achieve the benefits of memoization, we only want a single notification per digest cycle, irrespective of how many times that cycle iterates over the watch list.

I’ve created an afterEveryDigest service that allows a controller to register a function to be executed after every digest cycle. Here’s an example of it in action:

angular.module('controllers', ['services']).
  controller('ProposalCtrl', 
    function($scope, $routeParams, ProposalSvc, afterEachDigest) {
      ProposalSvc.get($routeParams.proposalId).then(
        function(proposal) {
          $scope.proposal = proposal;

          afterEachDigest($scope, function() {
            $scope.proposal.unmemoize();
          });
        }
      );
    });

Now we no longer have to invoke proposal.unmemoize() at every place in the code where the user changes a proposal.

Note that the implementation of this service currently has to use a private Angular function called $$postDigest. It’s important to note that $$postDigest only gets executed after the next digest cycle, not after every cycle. To get it to run after every cycle, I initially tried to pass it a function that recursively scheduled itself, but $$postDigest will put that function on the queue of tasks for the current digest cycle, meaning that it will immediately execute the function again within the cycle, going into an infinite loop.

Fortunately I found a code snippet by Karl Seamon that provides an alternate approach by combining $$postDigest with a $watch. However, the fact remains that $$postDigest is still a private function. In the longer term I’m hoping for something like the $postDigestWatch call that Karl briefly mentioned might make it into Angular 1.3 in his ‘Angular Performance’ talk at ng-conf. However, there’s no sign of it yet, so things aren’t looking good.

Wrapping Up

You’ll find the Base.memoize, Base.unmemoize and afterEveryDigest code in the Github project. You may notice in the code that the memoize service being used under the hood has its own memoization implementation rather than delegating to underscore or lodash. This was because underscore’s implementation didn’t provide any way to unmemoize a method, and I didn’t want to introduce lodash as a dependency.

Memoization should not be used indiscriminately because the more you do it, the more you expose yourself to potential problems if you accidentally memoize a method that isn’t idempotent and/or has side-effects. Memoization can also make debugging more difficult as you’re introducing an additional level of indirection. That said, a few well-placed memoizations can dramatically increase the performance of your code. Just remember that, as always, it’s better to profile and optimise your specific problem scenario than to use a shotgun approach.