Optimizing Redux Store

Mar 15, 2019 • 15 Minute Read

Introduction

Redux offers a pattern that generalizes well. This pattern, sometimes, causes complex scenarios to be treated as simple cases.

The good news is that optimizing your redux store isn't that different from optimizing any other piece of software - it always falls back to Data Structures and Algorithms. Always.

Don't worry; there's nothing scary there. We'll use two techniques in this guide:

Data normalization (we'll use a hash table to optimize lookups)
Memoization (avoiding unnecessary recomputation)

Example Application

We'll use an application here that isn't much different from what you're probably using already. We'll maintain a list of values and display their details.

The application will:

Keep a list of objects (format { id, number }) and display them as an unordered list (<ul>).
Display each object in the format fib(n) = nth Fibonacci number (i.e. the n-th element in the Fibonacci sequence).

Just recapitulating, here's what the Fibonacci sequence looks like:

Each number is equal to the sum of the previous two numbers - except for 0 and 1, which are equal to themselves.

The algorithm we will use for this example is the following:

          const fibonacci = (n) => {
    if (n <= 1) return n;

    return fibonacci(n - 1) + fibonacci(n - 2);
  };
    

This algorithm is terribly inefficient and will cause a stack overflow even with small numbers. That's why it's perfect for this example - we want to force a horrible performance here and showcase how to improve it.

In case you're curious, the recursive algorithm has a time complexity of O(2^n). You can very easily implement a bottom-up algorithm that avoids recursion and brings this complexity down to O(n), but that's not the focus for this guide - let's worry about Redux instead!

The Code

Here's the code for this application:

index.js

          import React from 'react';
  import ReactDOM from 'react-dom';
  import { Provider } from 'react-redux';
  import { createStore } from 'redux';
  import rootReducer from './reducers';
  import './index.css';
  import App from './App';

  const store = createStore(rootReducer);

  ReactDOM.render(
    <Provider store={store}>
      <App />
    </Provider>,
    document.getElementById('root'),
  );
    

reducers.js

          import { combineReducers } from 'redux';
  import fibonacciReducer from './FibonacciList/ducks';

  const rootReducer = combineReducers({
    fibonacci: fibonacciReducer,
  });

  export default rootReducer;
    

App.js

          import React, { Component } from 'react';
  import FibonacciList from './FibonacciList';
  import './App.css';

  class App extends Component {
    render() {
      return (
        <div className="App">
          <header className="App-header">
            <FibonacciList />
          </header>
        </div>
      );
    }
  }

  export default App;
    

FibonacciList/index.js

          import React from 'react';
  import AddNumber from './addNumber';
  import List from './list';

  const FibonacciList = () => (
    <>
      <AddNumber />
      <List />
    </>
  );

  export default FibonacciList;
    

FibonacciList/addNumber.js

          import React, { useState } from 'react';
  import { connect } from 'react-redux';
  import { bindActionCreators } from 'redux';
  import { addNumber } from './ducks';

  const AddNumber = React.memo(({ addNumber }) => {
    const [newNumber, setNewNumber] = useState('');

    const handleSubmit = (e) => {
      e.preventDefault();
      if (!newNumber) return;

      addNumber(newNumber);
      setNewNumber('');
    };

    const handleChange = (e) => setNewNumber(Number(e.target.value) || '');

    return (
      <form onSubmit={handleSubmit}>
        <input type="number" onChange={handleChange} value={newNumber} />
        <input type="submit" value="Create" />
      </form>
    );
  });

  const mapDispatchToProps = dispatch => bindActionCreators({ addNumber }, dispatch);

  export default connect(null, mapDispatchToProps)(AddNumber);
    

FibonacciList/list.js

          import React from 'react';
  import { connect } from 'react-redux';
  import Details from './details';
  import { selectNumbers } from './ducks';

  const List = React.memo(({ numbers }) => (
    <ul>
      {numbers.map(number => <Details key={number.id} numberId={number.id} />)}
    </ul>
  ));

  const mapStateToProps = (state) => ({
    numbers: selectNumbers(state),
  });

  export default connect(mapStateToProps)(List);
    

FibonacciList/details.js

          import React from 'react';
  import { connect } from 'react-redux';
  import { selectNumberDetails } from './ducks';

  const Details = ({ details }) => (
    <li>{`fib(${details.number}) = ${details.fibonacci}`}</li>
  );

  const mapStateToProps = (state, ownProps) => ({
    details: selectNumberDetails(state, { id: ownProps.numberId }),
  });

  export default connect(mapStateToProps)(Details);
    

FibonacciList/ducks.js

          // Actions
  const ADD_NUMBER = 'ADD_NUMBER';

  // Action Creators
  export const addNumber = number => ({
    type: ADD_NUMBER,
    number,
  });

  // Reducer
  const initialState = {
    values: [...new Array(30)].map((_, i) => ({ id: String(i), number: i + 1 })),
  };

  export default function fibonacciListReducer(state = initialState, action) {
    switch (action.type) {
      case ADD_NUMBER:
        return {
          ...state,
          values: [
            { id: String(state.values.length), number: action.number },
            ...state.values,
          ],
        };
      default:
        return state;
    }
  };

  // Selectors
  const fibonacci = (n) => {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
  };

  export const selectNumbers = state => state.fibonacci.values;
  export const selectNumberDetails = (state, { id }) => {
    const number = state.fibonacci.values.find(n => n.id === id);
    return { ...number, fibonacci: fibonacci(number.number) };
  }
    

There are many problems with this application and multiple ways of improving it, but let's focus on enhancing the redux store itself and its selectors.

Improving Lookups (For the values Array)

The time spent in filtering is not the main problem in this particular application (the Fibonacci calculation is), but, in my experience, this is one of the first issues to show up in the real world.

Whenever you select an item, your app will loop through each element in the array sequentially, until it finds the object. If this procedure is repeated over and over, or if you're dealing with humongous collections, this time quickly adds up and becomes a headache.

The best way to deal with this is to convert the structure you're using into a hash map. Luckily, JavaScript makes things ultra easy for us here - objects in JS are already hash maps!

Example:

          const notNormalized = [{
    id: '1',
    number: 3,
  }, {
    id: '2',
    number: 5,
  }];

  // selecting from this array:
  const item = notNormalized.find(item => item.id === '2'); // will run for all elements until reaching the element with id '2'

  const normalized = {
    '1': {
      id: '1',
      number: 3,
    },
    '2': {
      id: '2',
      number: 5,
    },
  };

  // selecting from this hash map
  const item2 = normalized['2']; // doesn't get worse as the array grows - time complexity of O(1)
    

To convert arrays into hash maps - and assuming each element in the array contains an id - let's use the following function:

          const normalize = arr => arr.reduce(
    (acc, curr) => ({
      values: { ...acc.values, [curr.id]: curr },
      ids: [...acc.ids, curr.id], 
    }),
    { values: {}, ids: [] },
  );
    

We're keeping the IDs in their original order here, so we can rehydrate the hash map and create an array that looks exactly like the original.

The new reducer and selectors now look like this:

          // Reducer
  const normalize = arr => arr.reduce(
    (acc, curr) => ({
      values: { ...acc.values, [curr.id]: curr },
      ids: [...acc.ids, curr.id], 
    }),
    { values: {}, ids: [] },
  );

  const originalValues = [...(new Array(30))].map((_, i) => ({ id: String(i), number: i + 1 }));

  export const initialState = normalize(originalValues); // convert array into hash map and array of ordered ids

  export default function fibonacciListReducer(state = initialState, action) {
    switch (action.type) {
      case ADD_NUMBER:
        const id = String(state.ids.length);
        return {
          ...state,
          values: {
            ...state.values,
            [id]: { id, number: action.number },
          },
          ids: [id, ...state.ids],
        };
      default:
        return state;
    }
  };

  // Selectors
  const fibonacci = (n) => {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
  };

  export const selectNumbers = state => state.fibonacci.ids.map(id => state.fibonacci.values[id]);
  export const selectNumberDetails = (state, { id }) => {
    const number = state.fibonacci.values[id] || {};
    return { ...number, fibonacci: fibonacci(number.number) };
  };
    

Improving Selectors (Memoization)

Memoization is a fancy name for caching. One (very) simple example of memoization would be the following:

          const memo = {};
  const sum = (a, b) => a + b;
  const sumMemoized = (a, b) => {
    const key = `${a}${b}`;
    if (memo[key]) return memo[key];

    memo[key] = sum(a, b);
    return memo[key];
  };
    

This technique avoids the recalculation of values by storing values in memory - in other words, you're trading space (memory) for time (computation).

Of course, you can implement memoization from scratch, but a much simpler approach is to use a library. The most popular library for memoizing selectors is called reselect.

In our application, this is how we can use reselect to memoize selectNumbers:

          import { createSelector } from 'reselect';

  // .... actions, reducers, etc

  const selectBaseState = state => state.fibonacci;
  const selectBaseIds = state => selectBaseState(state).ids;
  const selectBaseValues = state => selectBaseState(state).values;

  export const selectNumbers = createSelector(
    selectBaseIds,
    selectBaseValues,
    (ids, values) => ids.map(id => values[id]) || [],
  );
    

This new selector prevents running that map function over and over, giving you a speed boost.

Now, selectNumerDetails is a bit more complex. reselect, by default, doesn't work properly across component instances (i.e. the selector itself is memoized). Since each time we instantiate the Details component we provide it with a different id prop, our selector is called each time with different arguments - which will trigger reselect to believe things just changed.

To make reselect work in this scenario, we need to change a couple of things:

Turn our selectNumberDetails selector into a factory (let's call it makeSelectNumberDetails):

          export const makeSelectNumberDetails = () => createSelector(
    selectItem,
    (item) => ({
      ...item,
      fibonacci: fibonacci(item.number),
    }),
  );
    

Do the same thing for our mapStateToProps - let's turn it into makeMapStateToProps:

          const makeMapStateToProps = () => {
    const selectNumberDetails = makeSelectNumberDetails();
    return (state, ownProps) => ({
      details: selectNumberDetails(state, ownProps),
    });
  };

  export default connect(makeMapStateToProps)(Details);
    

These selectors will already give you massively superior performance. Just for the final extra boost, let's memoize the fibonacci function, too - this time from scratch! Hooray!

          const makeFibonacci = () => {
  const memo = { 0: 0, 1: 1 };
  return (n) => {
    if (memo[n]) return memo[n];

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

const fibonacci = makeFibonacci();
    

Good, but what are the numbers?

I'm glad you asked!

Let's run a test where we:

Reload the page
Type 45 into the input field
Start recording performance (on Chrome)
PressEnter
Wait until the new item is displayed and stop recording.

Results:

Optimized: 0.1s
Non-optimized: 29s

No, seriously. The optimized code runs 290 times better, and that's with a value of 45. Given how horrible the performance of that Fibonacci algorithm is, if you enter 500 into that form, a typical computer is likely not to complete the computation in your lifetime. Our optimized application will continue clocking sub-second updates in the same scenario.

Conclusion

A good rule of thumb when designing your Redux store (and everything else) is to avoid premature optimization. I had situations where I made performance worse by trying to apply optimization techniques where they weren't required at all - so, unless you already have an issue, it's good to strive for simplicity. A simple, easily understandable piece of code is the best thing you can hope to achieve. Building on top of it (and optimizing it!) will be much easier if the code is already straightforward from the beginning.

For all other situations, things always boil down to Data Structures and Algorithms (I'm sure I sound like your CS 101 teacher now). The techniques used in this guide were:

Optimizing lookup by changing the data structure used in the store - using a hash map (JS Object) instead of an array.
Avoiding unnecessary calls to our selectors by using memoization (with reselect).
Finally, improving the performance of our expensive algorithm by manually memoizing it.

Hash maps and memoization weren't selected by chance here - in my experience, and without a proper study to collect data on the subject, these two things are the number one approach most commercial applications can benefit from. There are, obviously, some other things you can do - a hash map might not be the best structure for your use case, and merely memoizing a poorly designed algorithm might not be the perfect solution (even though it will probably improve things).

That said, the core of the question is always the same. When looking into a performance issue, your first question should be Am I using the appropriate data structure for this problem? followed closely by Is my algorithm properly designed? Are there major performance issues that can be solved here?. We can then finalize with Are there wasted update cycles? Is my code executed multiple times unnecessarily?.

I sincerely hope this helps you with that weird component that's getting stuck in mapStateToProps for half a minute during each update!