Performance issues with a tree structure and shouldComponentUpdate in React / Redux

Question

I'm fairly new to React, Redux and ImmutableJS, and have run into some performance issues.

I have a large tree structure of data, which I'm currently storing as a flat list in this structure:

new Map({
  1: new Node({
    id: 1,
    text: 'Root',
    children: [2,3]
  }),
  2: new Node({
    id: 2,
    text: 'Child 1',
    children: [4]
  }),
  3: new Node({
    id: 3,
    text: 'Child 2',
    children: []
  }),
  4: new Node({
    id: 4,
    text: 'Child of child 1',
    children: []
  })
});

While structuring it as a flat list makes updating nodes easy, I'm finding that interaction gets sluggish as the tree grows. Interaction includes being able to select one or more nodes, toggle the visibility of their child nodes, update the text, and so on. It looks like a key reason for the the sluggish UI is that the entire tree is being redrawn for each interaction.

I want to use shouldComponentUpdate such that if I update node 3, nodes 2 and 4 do not update. This would be easy if the data was stored as a tree (I could simply check whether this.props !== nextProps), but as the data is stored in a flat list the check would be substantially more complex.

How should I being storing the data and using shouldComponentUpdate (or other methods) to support a smooth UI with hundreds or thousands of tree nodes?

Edit

I've been connecting the store at the top level, and then having to pass the entire store down to subcomponents.

My structure is:

<NodeTree> 
  <NodeBranch>
    <Node>{{text}}</Node>
    <NodeTree>...</NodeTree>
  </NodeBranch>
  <NodeBranch>
    <Node>{{text}}</Node>
    <NodeTree>...</NodeTree>
  </NodeBranch>
  ...
</NodeTree>

The <Node> can do a simple check with shouldComponentUpdate to see if the title has changed, but I have no similar solution to use on the <NodeTree> or <NodeBranch> given the recursive nature of the tree.

It looks like the best solution (thanks @Dan Abramov) would be to connect each <NodeBranch>, rather just connecting at the top level. I'll be testing this this evening.

Answer 1

I just added a new example showing just that.
You can run it like this:

git clone https://github.com/rackt/redux.git

cd redux/examples/tree-view
npm install
npm start

open http://localhost:3000/

Answer 2

Dan Abramov solution is fine in 99% of usual cases.

But the computation time required on each increment is proportional O(n) to the number of nodes in the tree , because each connected node HOC has to execute a little bit of code (like identity comparison...). This code is pretty fast to execute however.

If you test Dan Abramov solution, with 10k nodes on my laptop I start to see some latency when trying to increment the counter (like 100ms latency). It is probably much worse on cheap mobile devices.

One could argue that you should not try to render 10k items in the DOM at once, and I totally agree with that, but if you really want to display a lot of items and connect them it is not that simple.

If you want to turn this O(n) to O(1), then you can implement your own connect system where the HOC's (Higher Order Component) subscription is only triggered when the underlying counter is updated, instead of all HOC's subscriptions.

I've covered how to do so in this answer.

I created an issue on react-redux so that connect becomes more flexible and permit easily to customize the store's subscription through options. The idea is that you should be able to reuse connect code and subscribe efficiently to state slices changes instead of global state changes (ie store.subscribe()).

const mapStateToProps = (state,props) => {node: selectNodeById(state,props.nodeId)}

const connectOptions = {
   doSubscribe: (store,props) => store.subscribeNode(props.nodeId)
}

connect(mapStateToProps, undefined,connectOptions)(ComponentToConnect)

It is still your own responsability to create a store enhancer with a subscribeNode method.