Hello everyone! Memoization is an optimization technique that can significantly speed up function execution by caching their results. In this article, we’ll explore what memoization is, how it works in JavaScript, when and why to use it, and we’ll look at implementation examples.

What is Memoization?

Memoization is the process of storing the results of function execution so that the next time the function is called with the same arguments, the stored result can be returned immediately. Memoization prevents redundant calculations and improves performance, especially in cases where a function is called repeatedly with the same arguments.

When dealing with functions that involve complex and resource-intensive calculations (e.g., recursive functions for calculating Fibonacci numbers or factorials), optimization can be essential. Memoization allows you to avoid repeated calculations, improving performance, particularly for functions that are frequently called with identical arguments.

A Basic Example of Memoization

Let’s look at a simple example of a function that returns the square of a number:

function square(num) {
    console.log('Calculating square of', num);
    return num * num;
}

console.log(square(4)); // Calculating square of 4 -> 16
console.log(square(4)); // Calculating square of 4 -> 16 (calculation repeated)

Here, the square function performs the same calculation each time it’s called, even if we already know the result for the number 4. This is inefficient. Let’s add memoization to improve it.

Implementing a Memoized Function

To implement memoization, we’ll create a memoize function wrapper that caches the results of a target function:

function memoize(fn) {
    const cache = {}; // Object to store cached results

    return function(...args) {
        const key = JSON.stringify(args); // Create a key based on arguments

        if (cache[key]) {
            return cache[key]; // Return the cached result if available
        }

        const result = fn(...args); // Call the original function
        cache[key] = result; // Store the result in cache
        return result;
    };
}

const memoizedSquare = memoize(square);

console.log(memoizedSquare(4)); // Calculating square of 4 -> 16
console.log(memoizedSquare(4)); // 16 (no recalculation)

Now, the memoizedSquare function caches results for each unique set of arguments and retrieves them from the cache on subsequent calls.

How the memoize Function Works

1. Cache Creation: Inside memoize, a cache object is created to store results of the target function.
2. Key Generation: For each function call, a unique key is generated based on the arguments. In our example, we use JSON.stringify(args) to turn the argument array into a string.
3. Checking Cache: If the result for this key exists in the cache, it is returned immediately without re-running the function.
4. Storing New Result: If the result is not in the cache, the function is executed, and the result is stored for future calls.

Memoization and Recursive Functions

Memoization is especially useful for recursive functions, such as calculating Fibonacci numbers. Without memoization, such functions can be very slow due to repeated calculations.

Consider this Fibonacci function example:

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

console.log(fibonacci(40)); // Very slow

In this fibonacci example, calculating fibonacci(40) will take a long time, as many values are recalculated multiple times. Let’s add memoization to improve performance:

const memoizedFibonacci = memoize(fibonacci);
console.log(memoizedFibonacci(40)); // Much faster

Using memoization allows us to speed up the function execution significantly since the function will store intermediate values and reuse them as needed, avoiding redundant calculations.

Using Map for Memoization

In previous examples, we used an object to store the cache, but JavaScript's Map may be more convenient, as it allows storing any type of data as keys. For example:

function memoize(fn) {
    const cache = new Map();

    return function(...args) {
        const key = JSON.stringify(args);
        if (cache.has(key)) {
            return cache.get(key);
        }
        const result = fn(...args);
        cache.set(key, result);
        return result;
    };
}

Using Map can improve readability and performance in some cases.

Cache Size Limits and Cleanup

Memoization can lead to excessive memory usage since the cache can take up a lot of space if there are many unique function calls. To prevent memory overflow, you can implement a cache size limit. For example:

function memoizeWithLimit(fn, limit = 10) {
    const cache = new Map();

    return function(...args) {
        const key = JSON.stringify(args);
        if (cache.has(key)) {
            return cache.get(key);
        }

        const result = fn(...args);
        cache.set(key, result);

        if (cache.size > limit) {
            const firstKey = cache.keys().next().value;
            cache.delete(firstKey); // Remove the oldest element
        }

        return result;
    };
}

Here, if the cache size exceeds the defined limit, we delete the first added element. This allows the application to be more efficient because then we control the memory.

Memoization in real projects

In real projects, memoization is used not only to store some numbers, strings for calculations, but also components that, if they have not changed, can be rendered without re-rendering. For example, in the HMPL project, by enabling memoization, you can take an already rendered component from the cache if the response data from the server is the same:

const newDiv = compile(
  `<div>
      <button>Get the square root of 256</button>
      <div>{{ src: "/api/getTheSquareRootOf256", after: "click:button" }}</div>
  </div>`
)().response;

In this example, since the server will receive response 16, the component will not be re-rendered.

When to Use Memoization

Memoization is useful in the following cases:

1. Long Computations: If a function performs lengthy calculations, memoization can help avoid repeating them.
2. Frequent Reuse of Same Data: If a function is often called with the same arguments, memoization helps store and reuse results.
3. Recursive Functions: Memoization speeds up recursive functions by avoiding repeated calculations for the same arguments.

When Not to Use Memoization

Memoization may be inefficient if:

1. The function is rarely called with the same arguments — the cache will not be utilized frequently.
2. The data is highly dynamic, and the result depends on its current state.
3. The cache size is large, and there is no mechanism for cache cleanup.

Conclusion

Memoization is a powerful and useful optimization technique that can improve the performance of functions in JavaScript by avoiding redundant computations and reducing system load. However, it’s important to use memoization only when necessary, taking memory limitations into account.

In practice, memoization can be beneficial when developing complex applications involving heavy calculations, such as in data analysis, machine learning, etc.

Thank you all very much for reading the article!

If you liked this article, it would be great if you rated HMPL on GitHub with a star.

Star HMPL