Memoization in JavaScript, Angular and React

Posted by: V Keerti Kotaru , on 10/22/2020, in Category JavaScript
Views: 8016
Abstract: This tutorial demonstrates the Memoization technique via three implementations - JavaScript, Angular and React.js

Memoization (also spelled memoisation) is a caching technique for function calls.

Many of us have written code that caches expensive database calls, network calls, I/O etc. But how about caching the return value of a function that takes time to execute?

We can use the cached value as long as the arguments to the function calls do not change. This way we can execute the function only for new invocation with unique arguments.

Wikipedia defines memoization as following:

In computing, memoization or memoisation 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.

This article demonstrates Memoization in JavaScript. We begin with a barebone JavaScript implementation of Memoization. Next, we look at usage in Redux, an application state management framework. We will explore two implementations of Redux – in Angular and in React.

This article is an attempt to provide a holistic view of the Memoization concept across the JavaScript landscape.

Memoization in JavaScript

Memoization is a caching technique for functions. We can add behavior on top of a JavaScript function to cache results for every unique set of input parameters.

Let’s dive into the details with a very simple example: a multiplication function.

As you can guess, there is no performance incentive for caching the result of multiplication . However, we use this as a simplistic example in order to illustrate the concept of Memoization.

Consider the following code in Listing 1. We have a function that takes two arguments p1 and p2. It multiplies the two arguments and returns a value. To demonstrate memorization, we will write a wrapper that memoizes the function call. We can use this wrapper for a simple example ( as is the case here ), or for a more complex and expensive algorithm.

const multiply = memoizeAny((p1, p2) => {
    console.log("invoked original function", p1, p2);
    return p1 * p2;
});

Listing 1: Wrap multiply function for memoization

Notice the console log in Listing 2 that prints every time the multiplication function is invoked. The log doesn’t appear when the result is returned from the cache.

Save our JavaScript code in a file called memoize.js, and run it using node memoize.js (Refer to the Code Samples section at the end of the article for a link to the complete code sample).

Consider the following function calls and results.

console.log("multiply", multiply(10,30));// A new set of params. Performs multiplication and caches the result 
console.log("multiply", multiply(10,20));// A new set of params. Performs multiplication and caches the result
console.log("multiply", multiply(10,20));/* *** RETURNS CACHED VALUE *** */ 
console.log("multiply", multiply(10,10));// A new set of params. Performs multiplication and caches the result
console.log("multiply", multiply(10,30));/* *** RETURNS CACHED VALUE *** */
console.log("multiply", multiply(10,10));/* *** RETURNS CACHED VALUE *** */

Listing 2: Invoke memoized function

memoization-multiply-calls

Figure 1: Multiply() calls to demonstrate memoization

See Figure 1. For every unique set of arguments (say 10 and 20), the multiplication function is invoked. All repeated calls are returned from the cache.

Note: In the above sample, we are making an assumption that the function is a pure function. That is, the return value stays the same for a set of input arguments. If there are additional dependencies, other than the arguments, this technique does not work.

 

Memoization: the implementation

The following memoization wrapper is one simple way to implement memoization. However, as we will see, it is possible to optimize this implementation further.

const memoizeAny = (func) => {
    // Use this variable memoizedKeyValues to save results
    // Identify each result with it's input.
    // If the memoized function is called with the same input, use the existing value.  
    const memoizedKeyValues = [
        /* {
             args: stringified_input_parameters
             result: result
         }*/
    ];
    // Return a function. When we memoized multiply below, we called this function, for each invocation of multiplication
    return (...args) => {

        // for the given input (params), check if there is a cached result
        let result = memoizedKeyValues.find(x => x.args === JSON.stringify(args))

        // YES, there is a cached result
        if (result) {
            console.log("from cache", args);
            return result.result; // return cached result
        }

        // controls comes to this line only if there is no cached result.
        result = func.apply(this, args); // invoke the function

        // cache result
        memoizedKeyValues.push({
            args: JSON.stringify(args),
            result: result
        })

        // return the result
        return result;
    }
}

Listing 3: Memozation decorator



Notice, memoizeAny accepts a function as a parameter. In a way, it acts as a decorator, enhancing the behavior of the provided function (multiply() in the sample).

The variable memoizedKeyValues maintains:

  1. key, every unique invocation of a function
  2. value, result after the function is invoked.

The memoizeAny function returns another function. In Listing 1, the constant multiple is assigned to this function object. Notice that the arguments provided to multiply are passed to this function.

This function converts arguments to a string creating a unique key. For every repeated function call, this value stays the same. For the first invocation of the function, we run the actual multiplication function and store the result in cache (array variable memoizedKeyValues). For every new invocation, we can query if the cache has a value with the given key. If it’s a repeated invocation, there will be a match. The value is returned from cache.

Notice, the actual function is invoked by functionObject.apply(). The control reaches this statement only if the cache doesn’t have a key for the given arguments.

Notice the console.log when return value is returned from cache (to demonstrate memorization). It’s the key – stringified arguments. See Figure-1 for the result.

Pure function

A pure function consistently returns the same value for a given set of input arguments. Pure functions do not have side effects which modify the state outside it s scope. Imagine, the multiply function depending on a global variable. For the sake of an example, call it a multiplication factor. The memoization logic we saw earlier doesn’t work anymore. Consider the following code in Listing 4:

var globalFactor=10;
          const multiply = memoizeAny( (p1, p2) => p1 * p2 * globalFactor);

Listing 4: Need for pure functions

The value of globalFactor could be modified by a different function in the program. Let’s say we memoized a result 2000 for input arguments 10 and 20 (10 * 20 * 10). Say, a different function changes the value of global factor to 5. If the next invocation returns value from cache, it’s incorrect. Hence, it is important that the function is a pure function for memoization to work.

Note: As a work around, we may include globalFactor while generating the key. However, it will be cumbersome (but not impossible) to make such logic generic.

Scope of memoizeAny()

Every invocation of memoizeAny() (in Listing 4) creates a separate instance of the returned function. The array used for cache (variable memoizedKeyValues) is local to each instance of the function. Hence, we have separate function objects and cache objects for two different memoized functions. Consider add() and multiply() functions memoized. If the same set of arguments are passed to add and multiply, they do not interfere.

In Listing 5, multiply(10,20) is cached separate from add(10,20). The result 200 for the former does not interfere with result 30 for the latter.

    const multiply = memoizeAny(function(p1, p2) {
    console.log("invoked original function", p1, p2);
    return p1 * p2;
});

const sum = memoizeAny((p1, p2) => {
    console.log("invoked original function", p1, p2);
    return p1 + p2;
});

console.log("multiply", multiply(10, 30)); // A new set of params. Performs multiplication and caches the result 
console.log("multiply", multiply(10, 20)); // A new set of params. Performs multiplication and caches the result
console.log("sum", sum(10, 20)); // A new set of params (for sum). Performs multiplication and caches the result
console.log("sum", sum(10, 20)); /* *** RETURNS CACHED VALUE *** */
console.log("multiply", multiply(10, 20)); /* *** RETURNS CACHED VALUE *** */
console.log("multiply", multiply(10, 10)); // A new set of params. Performs multiplication and caches the result
console.log("sum", sum(10, 10)); /* *** RETURNS CACHED VALUE *** */
console.log("multiply", multiply(10, 30)); /* *** RETURNS CACHED VALUE *** */
console.log("multiply", multiply(10, 10)); /* *** RETURNS CACHED VALUE *** */
console.log("sum", sum(10, 10)); /* *** RETURNS CACHED VALUE *** */

Listing 5: Separate instance for each invocation of memoizeAny()

However, if we call memoizeAny() on multiply repeatedly, they create separate instances as well. It might result in unexpected behavior. One way to solve this problem would be to create a factory function which creates and returns a singleton instance of a memoized function. We may compare function object passed-in as an argument to determine if there is a singleton memoized function available, already. If not, wrap with memoizeAny().

Redux

Redux is an application state management framework. In this article, we will discuss the pattern and two popular implementations.

  1. NgRx for an Angular applications
  2. Redux and Reselect libraries for a React application

In the context of memoization, consider Selectors (reselect in React). It is one piece of Redux implementation. Let’s consider a sample Todo application for ease of understanding the use case.

Say, it provides three features.

  1. Create a todo
  2. Mark a todo complete
  3. Filter todos based on their completed status.

See Figure 2 for a redux implementation of the same.

redux-data-flow

Figure 2: Redux data flow in a Todo application

 

Notice a component CreateTodo for creating todos. Another component TodoList for listing, filtering and marking the todos as complete. The components dispatch actions, which invoke the pure functions called reducers, which return application level state.

Memoized selectors are used before returning the state to the component.

A typical redux store maintains a large centralized application state object. If busy components continuously select (retrieve) data from the redux store, it can quickly become a bottle-neck. Depending on the size of the application, retrieving data from the store could be a costly operation.

It is a good use case for memoization. For repeated retrieval of state, components use memoized selectors. As long as state is not modified, arguments (input) for the selectors stay the same (see Figure 2 for input/output to the selector).

Hence, the selector can return cached results to the components.

Memoization Angular Implementation

Let’s begin by visiting an Angular implementation of selectors and memoization with NgRx. If you are interested in React, jump to the next section.

This section describes memorization implementation with NgRx selectors.

Components make use of data returned by the NgRx selectors. They receive data from the NgRx store a few times, cached results are returned a couple of other times. This section aims to demonstrate the same and explain how optimization is achieved.

Selectors in NgRx are a use case for memoization. While the JavaScript section we saw earlier was theoretical with basic examples like multiplication and addition, the following code sample is realistic for caching results of a function in JavaScript.

Consider the following Angular folder structure. Refer to Code Samples section at the end of the article for links to the complete code sample.

src/app/ngrx/todo.reducer.ts – Todo feature specific reducer function. Returns todo state.

src/app/ngrx/todo.actions.ts – Todo actions to retrieve todo state, toggle a todo complete, create a new todo.

src/app/ngrx/todo.selector – Retrieve all todos or active/incomplete todos.

src/app/create-todo/ (folder) – Component to create a todo

src/app/todo-list/ (folder) – Component to list todos, filter and mark a todo complete.

In Figure 3, notice the CreateTodo component for creating todos. Alongside, notice a TodoList component for listing, filtering and marking todos complete.

angular-todo-sample-app

Figure 3: Angular Todo Sample Application

Now look at Listing 6 for memoized selectors. The createSelector API creates the two selectors getActiveTodos and getAllTodos. It’s imported from the module ‘@ngrx/store’.

export const getActiveTodos = createSelector(
    TODOS,
    state => {
        console.log("%cInvoked getActiveTodos()", "background: skyblue; color: purple; font-size: 14pt");
        return state.filter(item => item.isComplete === false)
    }
);

export const getAllTodos = createSelector(
    TODOS,
    state => {
        console.log("%cInvoked getAllTodos()", "background: lightgreen; color: purple; font-size: 14pt");
        return state;
    }
);

Listing 6: NgRx Selectors

These selectors are invoked from the todo list component. If you look at Listing 7, the function onShowAllClick() is invoked on toggling “Include completed tasks”. Depending on the toggle switch status, it either uses the getAllTodos() selector or the getActiveTodos() selector.

onShowAllClick(){
    // Toggle show all switch
    this.isAllSelected = !this.isAllSelected;

    if(this.isAllSelected){
      this.todos$ = this.store
        .pipe(
          select(selectors.getAllTodos)
        );
    } else {
      this.todos$ = this.store
        .pipe(
          select(selectors.getActiveTodos),
        );
    }

Listing 7: Component making use of the selectors

 

Notice the console.log statements in Listing 6. They print a log every time the selector is invoked, which retrieves state from the application store. In case of the state, the input argument for selector doesn’t change, the memoized result is returned.

Say, the user creates a new todo, the state is updated and the selector function is invoked till the state/argument changes again.

As we can see in Figure 4, toggling “include complete tasks” repeatedly uses cached results. It doesn’t retrieve state from the NgRx store (Redux store). Using the memoized results avoids querying a large NgRx store every time components request data.

And hence, using cached results is effective. The performance gains could vary based on application size, NgRx store size and even the efficiency of browser and the client machine.

console-log-selector-invoke

Figure 4: Console log on invoking the selector.

Follow the link for a complete Angular – NgRx code sample, https://github.com/kvkirthy/todo-samples/tree/master/memoization-demo

Memoization React Implementation

In this section, we cover another example of a Redux implementation – specifically, the React implementation. It describes how memoization works with Reselect.

It is a selector library, primarily for Redux. The library and the pattern aim to simplify Redux store.

Components consume application state. The state (or data) is created by components; for example, forms in components. It is also displayed and used in presentation logic etc. The selector functions calculate state as needed by the components. In addition to memoization, selectors can be composed. A selector can be used as an input to another selector.

This section aims to demonstrate memoization with reselect.

Redux accesses a large application store more often. Without memoization, any change to the state tree, be it in the area relevant to the component or not, leads to the Redux store being accessed. Expensive filtering and state calculations can occur.

Reselect’s memoization optimizes the same by accessing the store only when state being requested is updated. Otherwise, cached results are returned.

Consider the following structure for a React project with Redux and Reselect. The sample demonstrates memoization.

App.js – root component of the application

store.js – combines all reducers in the application to create a store

Consider the todo application in the React project:

CreateTodo.js – a component that allows the user to type-in a todo text and click create.

Todo.js – It lists all todos, allowing filtering in/out completed todos. In the code sample, CreateTodo is a child component of the Todo component.

todoSlice.js – It creates a slice that encapsulates initial state of the todos, reducers and actions. In the sample application, this file includes selectors as well.

We focus on memoization with reselect. To demonstrate the feature, consider the following Todo sample. The application provides three functionalities:

  1. Create a todo
  2. Mark a todo complete
  3. Filter todos based on their completed status.

reactjs-todo-sample

Figure 5: React Todo Sample Application

Notice the buttons (on top of the screen) – Include completed todos and Exclude completed todos. Clicking on the former shows all todos, even the completed items; and the latter excludes the completed items.

To create a memoized selector, use the createSelector API in the reselect module as shown in Listing 8.

// a selector function returns todos in the application state.
export const getAllTodos = state => state.todo.todos;

/* a selector function returns state indicating if completed todos to be included or excluded from the result */
export const showActiveTodos = state => state.todo.shouldIncludeComplete;

// The memoized selector
export const getTodos = createSelector([getAllTodos, showActiveTodos], (todos, showCompletedTodos) => {
    return showCompletedTodos ? todos : todos.filter(item => !item.isComplete);

Listing 8: Selectors

 

The selector getTodos is memoized and composed using two other selector functions getAllTodos and showActiveTodos. The selector function getAllTodos returns todos, which is only a part of the state tree. Typically, each feature is represented by a separate object in the Redux store. The application may have many other features and the application state is expected to include additional objects. The getTodos selector focuses only on todos.

The getTodos selector has a condition to return all todos including completed items or just the active items. When the selector is invoked the first time, it accesses the state tree and returns the data from the store. As application state is expected to be a large object, it could be a costly operation to repeatedly access the redux store.

When memomized, for repeated calls, the store is not accessed till the arguments change. Look at Figure 5. If the user clicks either of the filter buttons (“Include completed todos” or “Exclude completed todos”), the cached (or memoized) result is returned. Let’s add a console log to demonstrate invocation of the selector function in Listing 9.

export const getTodos = createSelector([getAllTodos, showActiveTodos], (todos, showCompletedTodos) => {
    console.log(`%cInvoked selector. Show Completed Todos: ${showCompletedTodos?'YES':'NO'} `, "background: skyblue; color: purple; font-size: 14pt", );
    return showCompletedTodos ? todos : todos.filter(item => !item.isComplete);

Listing 9: Selector with a console log statement

Notice Figure 6. During the initial page load, the selector function is invoked. The argument, showActiveTodos is defaulted to false. I clicked on “Include completed todos”. It invokes an action that sets state showActiveTodos to true. Notice, this state value is one of the arguments to the selector, getTodos().

As there is a change in argument value, the selector is invoked the next time. To demonstrate that the value is returned from cache when arguments don’t change, I continuously clicked the button “include complete todos” many times. The console log does not print anymore. It does not access the state tree, till the selector function arguments change.

As described in the section earlier, memorized selector avoids calculating state every time a change occurs in an unrelated section of a large Redux store. It optimizes React-Redux application by invoking the selector, only relevant state tree (accessed by the selector) is updated. Other times, cached results are used.

reactjs-app-console-log

Figure-6: Console log on the React application

Consider the following code snippet for Todo list component. Follow this link for a complete React, Redux and Reselect sample – https://github.com/kvkirthy/todo-samples/tree/master/react-demo

// Removed code for brevity

export function Todo() {    

    // useSelector() hook for using the Redux-reselect selector.
    let todos = useSelector(getTodos);
    
    return (<div className={styles.padded}> 
        /* Removed code for brevity */
        {todos.map(element => renderTodo(element))} 
    </div>);
}

Code Samples

● Memoization JavaScript code sample- https://github.com/kvkirthy/todo-samples/blob/master/memoization-demo/memoize.js

● Angular NgRx code sample- https://github.com/kvkirthy/todo-samples/tree/master/memoization-demo

● React- Redux and Reselect sample- https://github.com/kvkirthy/todo-samples/tree/master/react-demo

Resources

Wikepedia article on Memoization, https://en.wikipedia.org/wiki/Memoization

Angular NgRx documentation, https://ngrx.io/docs

Getting Started with Redux, https://redux.js.org/introduction/getting-started

Reselect (React) GitHub page, https://github.com/reduxjs/reselect

My past articles on memoization,

Part-1: Memoization

Part-2: Memoization with Selectors in NgRx .

This article has been technically reviewed by Benjamin Jakobus.

This article has been editorially reviewed by Suprotim Agarwal.

Absolutely Awesome Book on C# and .NET

C# and .NET have been around for a very long time, but their constant growth means there’s always more to learn.

We at DotNetCurry are very excited to announce The Absolutely Awesome Book on C# and .NET. This is a 500 pages concise technical eBook available in PDF, ePub (iPad), and Mobi (Kindle).

Organized around concepts, this Book aims to provide a concise, yet solid foundation in C# and .NET, covering C# 6.0, C# 7.0 and .NET Core, with chapters on the latest .NET Core 3.0, .NET Standard and C# 8.0 (final release) too. Use these concepts to deepen your existing knowledge of C# and .NET, to have a solid grasp of the latest in C# and .NET OR to crack your next .NET Interview.

Click here to Explore the Table of Contents or Download Sample Chapters!

What Others Are Reading!
Was this article worth reading? Share it with fellow developers too. Thanks!
Share on LinkedIn
Share on Google+

Author
V Keerti Kotaru is an author and a blogger. He has authored two books on Angular and Material Design. He was a Microsoft MVP (2016-2019) and a frequent contributor to the developer community. Subscribe to V Keerti Kotaru's thoughts at his Twitter account. Checkout his past blogs, books and contributions at kvkirthy.github.io/showcase.


Page copy protected against web site content infringement 	by Copyscape




Feedback - Leave us some adulation, criticism and everything in between!

Categories

JOIN OUR COMMUNITY

POPULAR ARTICLES

Tags

JQUERY COOKBOOK

jQuery CookBook