Memoization in JavaScript

JavaScript and functional programming go hand in hand. There are times when our functions will be expensive in terms of performance. Performing the same functions with the same input over and over again could degrade the experience of the application and it is unnecessary.

Memoization is an optimization technique in which we cache the function results. If we provide the same input again, we fetch the result from the cache instead of executing code that can cause a performance hit.

In case the result is not cached, we would execute the function and cache the result. Let's take an example of finding the square of a number.

const square = () => {
    let cache = {}; // set cache
    return (value) => {
        // if exists in cache return from cache
        if (value in cache) {
            console.log("Fetching from cache");
            return cache[value];
        } else {
            // If not in cache perform operation
            console.log("Performing expensive query");
            const result = value * value;
            cache[value] = result; // store the value in cache
            return result; // return result
        }
    }
}

const sq = square();
console.log(sq(21)); // Performing expensive query, 441
console.log(sq(21)); // Fetching from cache, 441

Why or when to use it?

• For expensive function calls, i.e. functions that do network calls where the output might not change or functions with large computations or disk I/O.
• For pure functions (where function output stays the same given the same input).
• For functions with a limited range of input but highly recurring.

Comments

[Amin]

Hi Parwinder and thanks for your article.

If you use a constant for your cache, you would still be able to add some keys to it. Plus, it makes reassignment by mistake throw an error which is an added security.

You can even use an immediately invoked function expression to handle to prevent having to call the function to get the closure first.

Plus, your else branch is not necessary since you are returning (and thus stopping the execution of the function) in your conditional statement.

In the end, this proposal could serve as an alternative for implementing the memoized square function.

const square = (() => {
    const cache = {};

    return value => {
        if (typeof cache[value] !== "undefined") {
            console.log("Fetching value from the cache.");
            return cache[value];
        }

        console.log("Computing and storing the result in the cache.");
        return cache[value] = value * value;
    };
})();

console.log(square(2));
console.log(square(4));
console.log(square(6));
console.log(square(6));

// Computing and storing the result in the cache.
// 4
// Computing and storing the result in the cache.
// 16
// Computing and storing the result in the cache.
// 36
// Fetching value from the cache.
// 36

And if you need to create multiple memoized functions, you can even extract the memoization in its own helper function.

const memoize = callback => {
    const cache = {};

    return (...parameters) => {
        const args = JSON.stringify(parameters);

        if (typeof cache[parameters] !== "undefined") {
            console.log("Fetching value from the cache.");
            return cache[parameters];
        }

        console.log("Computing and storing the result in the cache.");
        return cache[parameters] = callback(...parameters);
    };
};

const square = memoize(value => value * value);

console.log(square(2));
console.log(square(4));
console.log(square(6));
console.log(square(6));

// Computing and storing the result in the cache.
// 4
// Computing and storing the result in the cache.
// 16
// Computing and storing the result in the cache.
// 36
// Fetching value from the cache.
// 36

[shadowtime2000]

You could also use a Map for that.

const memoize = (callback) => {
    const cache = new Map();

    return (...parameters) => {
        if (typeof cache.get(parameters) !== "undefined") {
            return cache.get(parameters);
        }
        cache.set(parameters, callback(...parameters));
        return cache.get(parameters);
    }
}

[Parwinder 👨🏻‍💻]

👏🏼 I like this

[Nikola Radulaški]

Why not just cache.get(parameters) !== undefined?

[Parwinder 👨🏻‍💻]

Thanks for the feedback @aminnairi . Excellent writeup and valid points. Instead of updating my original post with your recommendation, I am going to add a note to it. Readers can see how I approached it and how you made it better (and the reasoning behind it)

In the case of multiple memorization functions I do however prefer @shadowtime2000 implementation (but that is just a preference based on readability)

[Clay Ferguson]

I recently had a need to cache the results of decryption of an encrypted string so that decryption only runs once, and ended up using a cache where the 'key' of the cache is the hash of the string. Here's the hashing functions I have:

    hashOfString = (s: string): string => {
        let hash = 0;
        let i = 0;
        let chr = 0;
        if (s.length === 0) return hash.toString();

        for (i = 0; i < s.length; i++) {
            chr = s.charCodeAt(i);
            hash = ((hash << 5) - hash) + chr;
            hash |= 0; // Convert to 32bit integer
        }
        return hash.toString();
    }

    hashOfObject = (obj: Object): string => {
        if (!obj) return "null";
        return this.hashOfString(JSON.stringify(obj));
    }

Although the above isn't perfectly good in terms of avoiding hash collisions. I guess I should boost it up to a SHA-256 to be more 'solid' code.