Information


Blog Posts


Collections



Contact


Things Ian Says

Memoization

Some of my recent blog entries have dealt with using functional practices in Javascript. There are obviously downsides to functional programming as well, and one commonly stated one is around performance.

One area this applies to is in the large number of function calls resulting from this approach — particularly when we are writing recursive code.

We will give an example of this problem — calculating Fibonacci numbers — and then look at a technique known as memoization as a way of improving performance.

Fibonacci Numbers

Fibonacci Numbers (or the Fibonacci Sequence) is a mathematical sequence where each number in the sequence is made by adding together the two previous numbers.

We start off with 1 as both the first and second numbers. We then calculate the third as 1 + 1 = 2, the fourth is 1 + 2 = 3, the fifth is 2 + 3 = 5, the sixth is 3 + 5 = 8 and so on.

The Fibonacci sequence is named after its inventor (a 12th century Italian mathematician) and has remained of interest because it occurs commonly in nature.

Let’s talk about honeybees …

Female honeybees can reproduce with or without males. An unfertilised honeybee will give birth to a male, whereas a fertilised honeybee will give birth to a female.

So, a male honeybee (1 honeybee) will have a single female honeybee as his parent (1 honeybee). Going back a generation, his mother will have both a male and a female as her parents (2 honeybees). Going further back, that male will have one female parent and the female will have two (3 honeybees). Another generation gives us 5 honeybees (two for each of the females and one for the male).

As you can see, this is the Fibonacci sequence (and keeps going however many generations we go back).

Calculating Fibonacci Numbers

Suppose I want to write a Javascript function to calculate Fibonacci numbers (for some honeybee-related game I am writing). How would I go about this?

As I said in my blog entry on functional programming, what I want to do is describe the answer declaratively rather than procedurally. I’ve already stated how we calculate a Fibonacci number earlier — by adding together the two previous numbers. So we can easily implement that:

function fib (n) {
    return fib(n - 1) + fib(n - 2);
};

This function will obviously give us infinite recursion, so we also need another element from my description — start off with 1 as both the first and second numbers:

function fib (n) {

    if (n <= 2) {
        return 1;
    }

    return fib(n - 1) + fib(n - 2);
};

That was simple, so let’s see what happens when we run it:

     +-------------+-------------+-----------+
     | Result      | Func calls  | Time (ms) |
+----+-------------+-------------+-----------+
| 10 |          55 |          54 |     0.072 |
| 15 |         610 |         609 |     0.115 |
| 20 |       6,765 |       6,764 |     0.167 |
| 25 |      75,025 |      75,024 |     1.350 |
| 30 |     832,040 |     832,039 |    10.267 |
| 35 |   9,227,465 |   9,227,464 |   117.123 |
| 40 | 102,334,155 | 102,334,154 |  1267.468 |
+----+-------------+-------------+-----------+

Here you can see the value of n, the number in the nth position in the Fibonacci series, the number of function calls which have been made in calculating the result, and the elapsed time (in milliseconds) to perform that calculation. As you can see, all the numbers shoot up very quickly.

Think for a minute about how our function calculates the 20th number. It does this by adding together the 18th and 19th numbers. Now think about how the 19th number is calculated by adding together the 17th and 18th numbers. So, we end up calculating the 18th number twice (once directly and once as a consequence of calculating the 19th number). If you think about it, this becomes a combinatorial issue, with each smaller number being calculated more and more times.

Before we can look at how this can be optimised, we need to understand what is meant by a pure function.

Pure Functions

A pure function is one where the result of the function is only dependent on the inputs, where the same input always gives the same result, and where there are no side effects to the function.

Our fib function is an example of a pure function. The result of the function does depend on the input; every time we pass in the number 10 we would expect the answer 55; and the function doesn’t do anything else apart from calculate the result.

An example of a function which is not pure would be getTime(). This returns the number of milliseconds since the unix epoch. So each time we call it, we get a different result.

A getter function would not be pure — the answer depends on the value of the thing it is getting.

A setter function would not be pure — it has a side effect of changing the value it is setting.

Pure functions are important in functional programming, since they give flexibility around how they are calculated.

Suppose we had a function call like:

var result = add(getFirstValue(), getSecondValue());

As a trivial example of pure functions, we could have the following:

function getFirstValue () {
    return 2;
}

function getSecondValue () {
    return 3;
}

In this case, our result from add will always be 5, whether getFirstValue or getSecondValue is evaluated first.

If, however, we had the following definitions:

var x = 2;

function getFirstValue () {
    x = x + 1;
    return 2;
}

function getSecondValue () {
    return x;
}

With this example, if getFirstValue is evaluated before getSecondValue the answer is 5, but if getSecondValue is evaluated before getFirstValue then the answer is 4.

The above example is contrived and, in actual fact, Javascript defines the evaluation order as left to right. However, once we start using promises, things become less predictable. Consider the following code:

$q.all([
    getFirstValue(),
    getSecondValue()
]).then(function (data) {
    return data[0] + data [1];
});

In this situation, it is no longer defined whether getFirstValue or getSecondValue will be evaluated first. If our functions are not pure, then we risk different answers randomly being produced by our code.

Pure functions are also a pre-requisite for being able to memoize a function (which is why I am discussing them).

Memoization

Memoization is actually a simple technique, which stores the results of computationally intensive pure functions the first time they are calculated, then returns this stored value on future calls. So, we get rid of time-consuming calculations, but use up more space doing so.

If we do not use pure functions, then we will end up getting incorrect results. For example, if we try to memoize getTime() we will always get back the time of the first call whenever we called it.

You can see that this should be an advantage for us in our Fibonnaci calculation, since we have already identified that we are doing the same calculation repeatedly.

var memo = [];

function fib (n) {

    if (n <= 2) {
        return 1;
    }

    if (!memo[n]) {
        memo[n] = fib(n - 1) + fib(n - 2);
    }

    return memo[n];
};

This is based on our previous version, except we now use a variable called memo to store the results of calculations. If we don’t already have a result stored in memo we calculate it otherwise we just return the previously calculated result.

We can simplify it further, by noting that we can pre-populate our memo array with the first two values which allows us to remove our check for those calculations:

var memo = [0, 1, 1];

function fib (n) {

    if (!memo[n]) {
        memo[n] = fib(n - 1) + fib(n - 2);
    }

    return memo[n];
};

Finally, because we don’t want this to depend on an external variable, we can use the module pattern to make it available through a closure:

var fib = (function () {

    var memo = [0, 1, 1];

    return function (n) {

        if (!memo[n]) {
            memo[n] = fib(n - 1) + fib(n - 2);
        }

        return memo[n];
    };
})();

So, let’s fire it up and see how it performs now:

     +-------------+-------------+-----------+
     | Result      | Func calls  | Time (ms) |
+----+-------------+-------------+-----------+
| 10 |          55 |           8 |     0.500 |
| 15 |         610 |          13 |     0.012 |
| 20 |       6,765 |          18 |     0.006 |
| 25 |      75,025 |          23 |     0.007 |
| 30 |     832,040 |          28 |     0.014 |
| 35 |   9,227,465 |          33 |     0.008 |
| 40 | 102,334,155 |          38 |     0.011 |
+----+-------------+-------------+-----------+

By comparing back to our earlier table, you can see that it is still returning the correct result, but now the number of function calls (i.e. where a calculation needs to be made) is significantly reduced and consequently so is the execution time.

Previously we talked about the combinatorial increase in function calls without memoization. Here, we can see that the increase is now linear. In fact, we can see that the number of calls matches the value we are trying to calculate minus the two predetermined values.

We can see that the time has correspondingly reduced. Note that I am running this in a vagrant box, which is probably why there is some fluctuation in the timing results.

The above, however, clearly shows the time efficiency that memoization has brought - and also that the computational complexity is now linear.

Remember, however, that this reduction in time complexity comes at the cost of an increase in space complexity. At some point, the additional storage needed will start to give us problems. So it’s important to understand your problem parameters before deciding whether memoization is a useful technique.

As with currying, writing the memoization by hand is a useful way of understanding what is going on, but for real projects you should use a memoization module. This will let you write a standard (pure) function and then transform it to a memoized version.

Comparison with Procedural Approach

It’s just worth finishing by comparing this with a procedural approach. For a procedural approach, we will write a single function which goes from 1 up to the desired number in the sequence, adding up the numbers as we go. To achieve this, we will need some variables for the last and last but one numbers and will need to keep shuffling values into them. Here’s what I came up with:

function fib (n) {

    var result = 0;
    var last = 1;
    var beforeLast = 0;

    for (var i = 1; i < n; i++) {
        result = last + beforeLast;
        beforeLast = last;
        last = result;
    }

    return result;
};

Now let’s see how it runs:

     +-------------+-------------+-----------+
     | Result      | Func calls  | Time (ms) |
+----+-------------+-------------+-----------+
| 10 |          55 |           1 |     0.085 |
| 15 |         610 |           1 |     0.002 |
| 20 |       6,765 |           1 |     0.002 |
| 25 |      75,025 |           1 |     0.001 |
| 30 |     832,040 |           1 |     0.002 |
| 35 |   9,227,465 |           1 |     0.002 |
| 40 | 102,334,155 |           1 |     0.002 |
+----+-------------+-------------+-----------+

It produces the correct answer and obviously only makes one function call per result. Importantly, the performance is very good — better than our memoized version. However, we are talking about improvements of fractions of a millisecond, which may not be significant to you unless you are trying to squeeze out the absolute best performance.

And I feel the functional version has more readability (and is closer to the problem statement), which brings its own benefits.