Bas Groothedde

JavaScript Memoization Timeout


Caching data every now and then!


This blog post will be a continuation on my previous post about function memoization, in which I demonstrated simple function memoization. In this post I will discuss an additional method which allows the programmer to specify a specific amount of time to cache the data before it expires and has to be generated again.

Remind me, what's memoization again?

Let's cite Wikipedia again, however reading the previous post might also be helpful.

In computing, memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

When would a timeout on the cache be helpful?

Let's say you have a function which retrieves a list of statistics from the server each time a user clicks a button. When you only want to display new information every ten seconds instead of reloading the information on each click, such a timed memoized function might be useful. This would prevent the high amount of requests to the server due to many clicks and thus decrease server load. There are many more implementations which would be useful.

What we ended up with last time

Here's the code we ended up in the example last time, we'll be expanding it with our implementation with timeout.

;(function(root) {
    'use strict';

    // A 32-bit checksum of a string.
    if(!String.prototype.checksum) {
        String.prototype.checksum = function() {
            var checksum = 0, i, chr, len;
            if (this.length == 0) {
                return checksum;
            }

            for (i = 0, len = this.length; i < len; i++) {
                checksum = ((((checksum << 5) - checksum) + this.charCodeAt(i)) | 0);
            }

            return checksum;
        };
    }

    var memoize = function memoize(f) {
        if(typeof(f) !== "function" || !(f instanceof Function)) {
            throw new TypeError("Provided argument is not a function.");
        }

        /*
            The cache object for the memoized function. Each function 
            will hold its own cache object. The object will be indexed
            by 32-bit checksums of argument-lists.
        */
        var cache = {}; 

        return function MemoizedFunction() {
            // Create a checksum of all the arguments, if any argument is available.
            var checksum = 0;
            if(arguments.length > 0) {
                // if you don't expect complex argument structure, this will suffice
                // checksum = Array.prototype.join.call(arguments, ",").checksum();

                // serialize the arguments object to a JSON string and create a 32-bits checksum.
                checksum = JSON.stringify(arguments).checksum();
            }

            // if the checksum is unknown in the cache, call the function and cache it.
            if(typeof(cache[checksum]) === 'undefined') {
                cache[checksum] = f.apply(f, arguments);
            }

            // return the cached value.
            return cache[checksum];
        };
    };

    /** 
        Once is a function which allows a function to be called only once, regardless
        of the input. 
    */
    var once = function once(f) {
        if(typeof(f) !== "function" || !(f instanceof Function)) {
            throw new TypeError("Provided argument is not a function.");
        }

        var cached;

        return function OnceFunction() {
            if(typeof(cached) === 'undefined') {
                cached = f.apply(f, arguments);
            }

            return cached;
        };
    };

    root.memoize = memoize;
    root.once    = once;
}('mem' in window ? window.mem : window.mem = {})); // export to mem, create mem if it doesn't exist.

Additional function

For our new function we'll be using the memoize function as a base, so the new timed function will not be a timed once. This can later be added with ease. The extended logic is quite simple, instead of just checking if the cache contains a value for the arguments checksum, it will also check if the elapsed time since the last check exceeds the timeout to see if it needs to call the original function again.

The time check also needs to take the arguments checksum into account. Here's the snippet that should be added to what we already had:

var timed = function timed(f, timeout) {
    if(typeof(f) !== "function" || !(f instanceof Function)) {
        throw new TypeError("Provided argument is not a function.");
    }

    if(typeof(timeout) !== "number") {
        throw new TypeError("Provided argument is not a number.");
    }

    /*
        The cache object for the memoized function. Each function 
        will hold its own cache object. The object will be indexed
        by 32-bit checksums of argument-lists.

        The times object maintains a list of 'last updated time'. 
        These times are used to determine the age of the cache
        item.
    */
    var cache = {}; 
    var times = {}; 

    return function TimedMemoizedFunction() {
        // What's the current time?
        var now = +new Date();

        // Create a checksum of all the arguments, if any argument is available.
        var checksum = 0;
        if(arguments.length > 0) {
            // if you don't expect complex argument structure, this will suffice
            // checksum = Array.prototype.join.call(arguments, ",").checksum();

            // serialize the arguments object to a JSON string and create a 32-bits checksum.
            checksum = JSON.stringify(arguments).checksum();
        }

        /*
            if the checksum is unknown in the cache, call the function and cache it.
            if the last update time is unknown in the times cache, call the function and cache it.
            if the current time minus the last update time is equal to or greater than the timeout, 
            call the function and cache it.
        */
        if(typeof(cache[checksum]) === 'undefined' || typeof(times[checksum]) === 'undefined' || (now - times[checksum]) >= timeout) {
            cache[checksum] = f.apply(f, arguments);
            times[checksum] = now;
        }

        // return the cached value.
        return cache[checksum];
    };
};

root.timed = timed;

Example

Here's an example with all features implemented and tested by creating a few interval timers. The timedOnce function is also added in this example. I suggest clicking rerun to see the results from the start.

Check out this pen.

Summary

  • memoize - cache results based on a checksum of the arguments provided to the function, and when the function is called again with the same arguments, return the cached result instead of recalling the original function.
  • once - cache result based on a checksum of the arguments provided to the function once, and always return the first result despite of the provided arguments in future calls.
  • timed - identical to memoize, however cached results expire after a specific amount of time. If the cached results have expired, the original function will be called again and the cached results will be overwritten.
  • timedOnce - identical to once, however the cached result expires after a specific amount of time. If the cached result has expired, the original function will be called again once until the next cache expiration.

I hope this blog was worth the read, thanks for sticking out until the end!


Related articles

Discussion