Self-caching functions in JavaScript and Python

Earlier I wrote some code which repeatedly calls a function which performs a database query – often the same query. This encouraged me to explore various ways to cache the results of function calls in both Python (to solve my immediate problem) and JavaScript (because I find that language endlessly fascinating).

I played around with Fibonacci, which is a well suited to the task: it can be described in just a couple of lines of code yet benefits enormously from caching due to its recursive nature.

JavaScript Fibonacci without caching

function fibonacci(n) {
    if (n <= 1) return n;
    return fibonacci(n - 2) + fibonacci(n - 1);
}

I created a simple timer:

function timer(func) {
    var i = 10, start;
    while (i--) {
        start = new Date;
        func.apply(this, [].slice.call(arguments, 1));
        console.log(func.name, 'executed in', new Date - start, 'ms');
    }
}

How does the vanilla function perform?

>>> timer(fibonacci, 35);
fibonacci executed in 559 ms
fibonacci executed in 559 ms
fibonacci executed in 559 ms
fibonacci executed in 557 ms
fibonacci executed in 557 ms
fibonacci executed in 559 ms
fibonacci executed in 558 ms
fibonacci executed in 558 ms
fibonacci executed in 559 ms
fibonacci executed in 559 ms

Values of n much larger than 35 locked up my browser. That's not good. Fortunately, it's easy to improve the performance significantly.

JavaScript Fibonacci with caching via closure

JavaScript has closure, which means that each function has access to the variables and parameters or its outer function (and the variables and parameters of its outer function's outer function, and so on).

This is incredibly powerful. It makes it possible to create a variable, cache, which can only be accessed by our fibonacci function. This ensures that our cache cannot be overwritten, accidentally or otherwise.

fibonacci = (function () {

    var cache = {};

    return function (n) {

        var cached = cache[n];
        if (cached) return cached;

        if (n <= 1) return n;

        return (cache[n] = fibonacci(n - 2) + fibonacci(n - 1));
    };
}());

Does caching make a difference?

>>> timer(fibonacci, 35);
 executed in 1 ms
 executed in 0 ms
 executed in 0 ms
 executed in 0 ms
 executed in 0 ms
 executed in 0 ms
 executed in 0 ms
 executed in 0 ms
 executed in 0 ms
 executed in 0 ms

Undeniably, yes. Not only is the new version of the function much faster, but its less recursive nature makes it possible to find Fibonacci numbers for much larger values of n.

A slightly different approach is to initialize the cache with values for 0 and 1, making the if (n <= 1) logic unnecessary. Since one of the cached values is now 0, however, the if (cached) statement is no longer appropriate.

fibonacci = (function () {

    var cache = { 0:0, 1:1 };

    return function (n) {

        var cached = cache[n];
        if (typeof cached !== 'undefined') return cached;

        return (cache[n] = fibonacci(n - 2) + fibonacci(n - 1));
    };
}());

JavaScript Fibonacci with caching via function property

It's also possible to cache results without using closure. This is important since Python (which I'll get to shortly) does not have this capability.

function fibonacci(n) {

    if (!fibonacci.cache) fibonacci.cache = {};

    var cached = fibonacci.cache[n];
    if (cached) return cached;

    if (n <= 1) return n;

    return (fibonacci.cache[n] = fibonacci(n - 2) + fibonacci(n - 1));
}

To avoid the overhead of checking for the existence of the cache on each invocation, the cache could be initialized outside of the function definition.

function fibonacci(n) {
    // function body
}
fibonacci.cache = {};

Caching via function property and caching via closure performed equally well for me in Safari on Mac OS X.

Python Fibonacci without caching

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n - 2) + fibonacci(n - 1)

Does the vanilla Python function outperform the vanilla JavaScript function?

>>> import time
>>> for i in range(10): t = time.time(); fibonacci(35); print time.time() - t;

Interestingly, Python was more than an order of magnitude slower than JavaScript in this worst-case scenario. The point of this exercise is not to compare apples to oranges, however, it's to see how much of a difference caching makes in each case.

Python Fibonacci with caching via function property

def fibonacci(n):
    if n in fibonacci.cache:
        return fibonacci.cache[n]
    elif n <= 1:
        return n
    else:
        f = fibonacci.cache[n] = fibonacci(n - 2) + fibonacci(n - 1)
        return f

fibonacci.cache = {}

This resulted in fibonacci(35) being executed roughly 75,000 times as fast on an empty cache as the vanilla function.

Python Fibonacci with caching via mutable default argument

For the sake of completion I'll include this unappealing approach.

def fibonacci(n, _cache={}):
    if n <= 1:
        return n
    elif n in _cache:
        return _cache[n]
    else:
        f = _cache[n] = fibonacci(n - 2) + fibonacci(n - 1)
        return f

How does this work? In Python, default arguments are brought to life upon a function's creation, not its execution. Thus when fibonacci is called with just one argument (n) the value of _cache is the dictionary that was created at the time that fibonacci was created. Python's dictionaries are mutable, meaning that they can be changed in place. Together, these two features make it possible to use a mutable default argument — in this case a dictionary — as a cache.

Final thoughts

I had fun experimenting with these various approaches, furthering my understanding of both JavaScript and Python in the process. I've been writing JavaScript casually for several years; now that I'm making an effort to actually learn the language I'm starting to appreciate its brilliance.

Possibly related posts

• Converting integers to ordinals
• Python loops can have else clause?!
• Filtering lists in Python, Ruby, and JavaScript
• Bitwise NOT operator proves useful in JavaScript
• Repeating strings in JavaScript

Comments

var fibonacci1 = (function () {
    var cache = [1, 1], r;
    return function (n) {
        return cache[n] ||
            (cache.push(r = fibonacci1(n - 2) + fibonacci1(n - 1)), r);
    };
}());

var fibonacci2 = function(n) {
    var cache = fibonacci2.cache || (console.log('cache created!'), fibonacci2.cache = [1, 1]), r;
    return cache[n] ||
        (cache.push(r = fibonacci2(n - 2) + fibonacci2(n - 1)), r);
}

Respond