New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Memoizing Hierarchial Selectors #47

Closed
ronag opened this Issue Sep 20, 2015 · 25 comments

Comments

Projects
None yet
6 participants
@ronag

ronag commented Sep 20, 2015

I'm a bit stuck on how one would go about memorising the following selector using this library:

export function selectItem(items, id) {
  const item = items[id]
  return {
    id,
    ...item && {
      children: item.children.map((id) => selectItem(items, id))
    }
  }
}

Currently if any item in the items state is modified all of the selections need to be rebuilt.

Any suggestions on how to go about with these kind of scenarios?

A more complete example: https://gist.github.com/ronag/bc8b9a33da172520e123

@ellbee

This comment has been minimized.

Show comment
Hide comment
@ellbee

ellbee Sep 21, 2015

Member

Hey @ronag, I don't fully understand the example.

Currently if any item in the items state is modified all of the selections need to be rebuilt.

What does a 'selection' refer to here?

Member

ellbee commented Sep 21, 2015

Hey @ronag, I don't fully understand the example.

Currently if any item in the items state is modified all of the selections need to be rebuilt.

What does a 'selection' refer to here?

@ronag

This comment has been minimized.

Show comment
Hide comment
@ronag

ronag Sep 24, 2015

@ellbee: If I use that in redux for mapStateToProps it will create a new object for every item every time a single item is updated and also cause a react re-render... which is not very optimal. It would be nice to somehow memoize it. But I don't think it is possible with reselect as is... correct me if I'm wrong,

ronag commented Sep 24, 2015

@ellbee: If I use that in redux for mapStateToProps it will create a new object for every item every time a single item is updated and also cause a react re-render... which is not very optimal. It would be nice to somehow memoize it. But I don't think it is possible with reselect as is... correct me if I'm wrong,

@ellbee

This comment has been minimized.

Show comment
Hide comment
@ellbee

ellbee Sep 24, 2015

Member

I'm sure there will be a way to get this to work without re-rendering everything. Other than the fact that it is a nested tree, I'm still a bit fuzzy on what exactly this example is doing. Can you add an example of what the state object looks like? I don't get the difference between state.nodes and state.tree. Also, what is the purpose of selectEvent?

Member

ellbee commented Sep 24, 2015

I'm sure there will be a way to get this to work without re-rendering everything. Other than the fact that it is a nested tree, I'm still a bit fuzzy on what exactly this example is doing. Can you add an example of what the state object looks like? I don't get the difference between state.nodes and state.tree. Also, what is the purpose of selectEvent?

@ronag

This comment has been minimized.

Show comment
Hide comment
@ronag

ronag Sep 24, 2015

selectEvent should be selectItem and state.tree is not relevant, not sure why I added it. I've fixed the sample.

ronag commented Sep 24, 2015

selectEvent should be selectItem and state.tree is not relevant, not sure why I added it. I've fixed the sample.

@ellbee

This comment has been minimized.

Show comment
Hide comment
@ellbee

ellbee Sep 25, 2015

Member
function selectNode(nodes, id) {
  const node = nodes[id]
  return {
    id,
    title: 'Loading...',
    ...node && {
      title: node.title,
      children: node.children.map((id) => selectNode(nodes, id))
    }
  }
}

Oh, you are recursively building the tree in the selector. Would it be easier to keep the tree in the store state and use shouldComponentUpdate in TreeViewNode to only re-render the parts of the tree that have actually changed?

Member

ellbee commented Sep 25, 2015

function selectNode(nodes, id) {
  const node = nodes[id]
  return {
    id,
    title: 'Loading...',
    ...node && {
      title: node.title,
      children: node.children.map((id) => selectNode(nodes, id))
    }
  }
}

Oh, you are recursively building the tree in the selector. Would it be easier to keep the tree in the store state and use shouldComponentUpdate in TreeViewNode to only re-render the parts of the tree that have actually changed?

@ronag

This comment has been minimized.

Show comment
Hide comment
@ronag

ronag Sep 25, 2015

Sure I could build a second structure in the reducer which I need to keep in sync. But that kind of negates the purpose and nice functional aspect of selectors... in this specific scenario.

ronag commented Sep 25, 2015

Sure I could build a second structure in the reducer which I need to keep in sync. But that kind of negates the purpose and nice functional aspect of selectors... in this specific scenario.

@ellbee

This comment has been minimized.

Show comment
Hide comment
@ellbee

ellbee Sep 25, 2015

Member

I was suggesting that it might be an easier solution than Reselect style selectors in this scenario. Keeping the structures in sync shouldn't be a problem if they are both updated by the same action.

Having realised selectNode is recursive, I can't see a nice way to memoize it in the way that you want. You can't memoize on nodes because of the recursive calls. Every single one is going recompute as nodes + id is going to be unique for any change to nodes. And you can't memoize on an individual node, because although a nodes data might not have changed the data of one of its children might have. This will lead to subtrees not getting recomputed.

@speedskater Do you have any wisdom for us here?

Member

ellbee commented Sep 25, 2015

I was suggesting that it might be an easier solution than Reselect style selectors in this scenario. Keeping the structures in sync shouldn't be a problem if they are both updated by the same action.

Having realised selectNode is recursive, I can't see a nice way to memoize it in the way that you want. You can't memoize on nodes because of the recursive calls. Every single one is going recompute as nodes + id is going to be unique for any change to nodes. And you can't memoize on an individual node, because although a nodes data might not have changed the data of one of its children might have. This will lead to subtrees not getting recomputed.

@speedskater Do you have any wisdom for us here?

@ronag

This comment has been minimized.

Show comment
Hide comment
@ronag

ronag Sep 25, 2015

Though, this should be a quite common problem, if one follows the idea of normalising the data structure for your stores (i.e. https://github.com/gaearon/normalizr) you end up with the same problem when you need to denormalise your data for rendering your react component graph...

const nodesSelector = createSelector(
  state => state.root.selected,
  state => state.nodes,
  (selected, nodes) =>
    nodes.map((node, id) => node.merge({
      selected: id === selected,
    }))
)

const treeSelector = createSelector(
  state => state.root,
  nodesSelector,
  (root, nodes) =>
    root.merge({
      children: root.children.map((id) => nodes.get(id)),
    })
)

Every time the selection changes one has to re-build the entire tree... this can't be right...

ronag commented Sep 25, 2015

Though, this should be a quite common problem, if one follows the idea of normalising the data structure for your stores (i.e. https://github.com/gaearon/normalizr) you end up with the same problem when you need to denormalise your data for rendering your react component graph...

const nodesSelector = createSelector(
  state => state.root.selected,
  state => state.nodes,
  (selected, nodes) =>
    nodes.map((node, id) => node.merge({
      selected: id === selected,
    }))
)

const treeSelector = createSelector(
  state => state.root,
  nodesSelector,
  (root, nodes) =>
    root.merge({
      children: root.children.map((id) => nodes.get(id)),
    })
)

Every time the selection changes one has to re-build the entire tree... this can't be right...

@ellbee

This comment has been minimized.

Show comment
Hide comment
@ellbee

ellbee Sep 25, 2015

Member

Possibly, although you are the first to bring it up! Is there a good reason to have flattened the tree in the first place?

Member

ellbee commented Sep 25, 2015

Possibly, although you are the first to bring it up! Is there a good reason to have flattened the tree in the first place?

@ronag

This comment has been minimized.

Show comment
Hide comment
@ronag

ronag Sep 25, 2015

Yes, it is much easier to work with the data in the reducer. The flattened structure is much more natural to transform. From my experience that is the general case. The only reason you want it non-flat is to create the react component graph.

This is just a very simplified example.

ronag commented Sep 25, 2015

Yes, it is much easier to work with the data in the reducer. The flattened structure is much more natural to transform. From my experience that is the general case. The only reason you want it non-flat is to create the react component graph.

This is just a very simplified example.

@ronag

This comment has been minimized.

Show comment
Hide comment
@ronag

ronag Sep 25, 2015

I think the "selected" state in a treeview or list is a good example, You don't want to have a "selected" property on every node in the tree. Figuring out which item is selected would be O(n) instead of O(1) when working on the data structure. However, when displaying the data you want it as a graph, thus you want a "reselect" view of the data suited for creating the display.

The only alternative right now is to have 2 parallel data states, which gives me shivers, and also makes updates much more expensive both in terms of complexity and performance, or as my example re-build the entire state view every time something changes which is very slow.

I'm surprised no one else has encountered this issue.

ronag commented Sep 25, 2015

I think the "selected" state in a treeview or list is a good example, You don't want to have a "selected" property on every node in the tree. Figuring out which item is selected would be O(n) instead of O(1) when working on the data structure. However, when displaying the data you want it as a graph, thus you want a "reselect" view of the data suited for creating the display.

The only alternative right now is to have 2 parallel data states, which gives me shivers, and also makes updates much more expensive both in terms of complexity and performance, or as my example re-build the entire state view every time something changes which is very slow.

I'm surprised no one else has encountered this issue.

@ellbee

This comment has been minimized.

Show comment
Hide comment
@ellbee

ellbee Sep 26, 2015

Member

Yes, it is much easier to work with the data in the reducer. The flattened structure is much more natural to transform. From my experience that is the general case.

I do agree with this as a general principle. However, given the arbitrarily deep recursive tree data structure I am not sure that this example is the general case.

The problem as I see it is that you can only see the ids of the immediate children but don't know if any of these children have changed since the last update. Given that, I can't see how to build the tree without starting from the beginning and rebuilding each node every time.

The reason I suggested that a tree might be more suitable is that if you were updating a tree made from Immutable.js maps, for example, changing a node deep in the tree would change the parent nodes up to the root so you would easily be able to see which nodes have a change beneath them.

The only reason you want it non-flat is to create the react component graph.

Seems like a pretty good reason.

I think the "selected" state in a treeview or list is a good example, You don't want to have a "selected" property on every node in the tree. Figuring out which item is selected would be O(n) instead of O(1) when working on the data structure. However, when displaying the data you want it as a graph, thus you want a "reselect" view of the data suited for creating the display.

You could use the redux store to store a reference to the selected node.

The only alternative right now is to have 2 parallel data states, which gives me shivers, and also makes updates much more expensive both in terms of complexity and performance, or as my example re-build the entire state view every time something changes which is very slow.

Instead of 2 parallel data states, you could just model the tree as a tree?

I'm surprised no one else has encountered this issue.

Maybe they modelled their tree as a tree? 😉 Seriously though, if you have any suggestions as to how Reselect could be changed to support this case I would be keen to hear them, as I don't have any ideas.

Member

ellbee commented Sep 26, 2015

Yes, it is much easier to work with the data in the reducer. The flattened structure is much more natural to transform. From my experience that is the general case.

I do agree with this as a general principle. However, given the arbitrarily deep recursive tree data structure I am not sure that this example is the general case.

The problem as I see it is that you can only see the ids of the immediate children but don't know if any of these children have changed since the last update. Given that, I can't see how to build the tree without starting from the beginning and rebuilding each node every time.

The reason I suggested that a tree might be more suitable is that if you were updating a tree made from Immutable.js maps, for example, changing a node deep in the tree would change the parent nodes up to the root so you would easily be able to see which nodes have a change beneath them.

The only reason you want it non-flat is to create the react component graph.

Seems like a pretty good reason.

I think the "selected" state in a treeview or list is a good example, You don't want to have a "selected" property on every node in the tree. Figuring out which item is selected would be O(n) instead of O(1) when working on the data structure. However, when displaying the data you want it as a graph, thus you want a "reselect" view of the data suited for creating the display.

You could use the redux store to store a reference to the selected node.

The only alternative right now is to have 2 parallel data states, which gives me shivers, and also makes updates much more expensive both in terms of complexity and performance, or as my example re-build the entire state view every time something changes which is very slow.

Instead of 2 parallel data states, you could just model the tree as a tree?

I'm surprised no one else has encountered this issue.

Maybe they modelled their tree as a tree? 😉 Seriously though, if you have any suggestions as to how Reselect could be changed to support this case I would be keen to hear them, as I don't have any ideas.

@ronag

This comment has been minimized.

Show comment
Hide comment
@ronag

ronag Sep 26, 2015

I do agree with this as a general principle. However, given the arbitrarily deep recursive tree data structure I am not sure that this example is the general case.

Does it matter if it is arbitrarily or e.g. just a single level deep?

Seriously though, if you have any suggestions as to how Reselect could be changed to support this case I would be keen to hear it, as I don't have any ideas.

The only way I can see to solve this in reselect is if the memoized value was passed into the selector so that one can choose to short circuit the building the view and re-use the previous value.

ronag commented Sep 26, 2015

I do agree with this as a general principle. However, given the arbitrarily deep recursive tree data structure I am not sure that this example is the general case.

Does it matter if it is arbitrarily or e.g. just a single level deep?

Seriously though, if you have any suggestions as to how Reselect could be changed to support this case I would be keen to hear it, as I don't have any ideas.

The only way I can see to solve this in reselect is if the memoized value was passed into the selector so that one can choose to short circuit the building the view and re-use the previous value.

@ellbee

This comment has been minimized.

Show comment
Hide comment
@ellbee

ellbee Sep 26, 2015

Member

Does it matter if it is arbitrarily or e.g. just a single level deep?

Actually, I think it is nesting that causes the problem, arbitrary or not. You could make a custom selector that would work with a single level.

The only way I can see to solve this in reselect is if the memoized value was passed into the selector so that one can choose to short circuit the building the view and re-use the previous value.

Even with the previous state I don't think you can avoid walking the entire tree. However, that does give me an idea that won't avoid the tree walk, but will at least return the same object where child data hasn't changed. I'm going to be out for the rest of the day, but I'll give it a go tomorrow.

Member

ellbee commented Sep 26, 2015

Does it matter if it is arbitrarily or e.g. just a single level deep?

Actually, I think it is nesting that causes the problem, arbitrary or not. You could make a custom selector that would work with a single level.

The only way I can see to solve this in reselect is if the memoized value was passed into the selector so that one can choose to short circuit the building the view and re-use the previous value.

Even with the previous state I don't think you can avoid walking the entire tree. However, that does give me an idea that won't avoid the tree walk, but will at least return the same object where child data hasn't changed. I'm going to be out for the rest of the day, but I'll give it a go tomorrow.

@ronag

This comment has been minimized.

Show comment
Hide comment
@ronag

ronag Sep 26, 2015

but will at least return the same object where child data hasn't changed

Exactly! That was what I was thinking about. That's good enough, just so the entire react render tree doesn't need to re-run and you don't have to re-allocate all that memory. Just haven't been able to realise it yet.

ronag commented Sep 26, 2015

but will at least return the same object where child data hasn't changed

Exactly! That was what I was thinking about. That's good enough, just so the entire react render tree doesn't need to re-run and you don't have to re-allocate all that memory. Just haven't been able to realise it yet.

@ronag

This comment has been minimized.

Show comment
Hide comment
@ronag

ronag Sep 26, 2015

Actually, I think the easiest way to accomplish this is to simply do a connect for the TreeNode react component that would be pretty much perfect in terms of performance. I know it's non-pragmatic redux but it is the simplest solution I can think of.

Modelling the data as a tree inside the reducer just makes everything much more complex in my specific case as the tree is just a view for a data structure that is actually a list (with some plainly visual nested groupings) and 80% of the computations are wasted on constantly flattening the structure for logic as opposed to selecting the view data (neither one is good :/ ).

As far as I understand the pragmatic approach is to model data in the reducer simple and also most appropriate for logic and then use selectors to transform the data to a form appropriate for rendering where you would usually end up with a lot more redundant data.

ronag commented Sep 26, 2015

Actually, I think the easiest way to accomplish this is to simply do a connect for the TreeNode react component that would be pretty much perfect in terms of performance. I know it's non-pragmatic redux but it is the simplest solution I can think of.

Modelling the data as a tree inside the reducer just makes everything much more complex in my specific case as the tree is just a view for a data structure that is actually a list (with some plainly visual nested groupings) and 80% of the computations are wasted on constantly flattening the structure for logic as opposed to selecting the view data (neither one is good :/ ).

As far as I understand the pragmatic approach is to model data in the reducer simple and also most appropriate for logic and then use selectors to transform the data to a form appropriate for rendering where you would usually end up with a lot more redundant data.

@ellbee

This comment has been minimized.

Show comment
Hide comment
@ellbee

ellbee Sep 27, 2015

Member

Here is the idea I was talking about yesterday. It returns the same object, but at the cost of walking the entire tree to build it and every subtree when stringifying, plus the extra memory that getCachedTree will consume.

import { createSelector } from 'reselect';
import assert from 'assert';
import memoize from 'lodash.memoize';

// return a cached tree if it has been seen before
const getCachedTree = memoize(tree => tree, JSON.stringify);

// build the tree
const selectNode = (nodes, id) => {
  return getCachedTree({
    id,
    title: 'Loading...',
    children: nodes[id].children.reduce(
      (acc, id) => Object.assign(acc, {[id]: selectNode(nodes, id)}),
      {}
    )
  })
}

const selector = createSelector(
  state => state.nodes,
  nodes => selectNode(nodes, 1)
);

const state1 = {
  nodes: {
    1: {id: 1, children: [2,3]},
    2: {id: 2, children: [4,5]},
    3: {id: 3, children: [6,7]},
    4: {id: 4, children: []},
    5: {id: 5, children: []},
    6: {id: 6, children: []},
    7: {id: 7, children: []}
  }
};

const state2 = {
  nodes: {
    1: {id: 1, children: [2,3]},
    2: {id: 2, children: [4,5]},
    3: {id: 3, children: [6,7]},
    4: {id: 4, children: []},
    5: {id: 5, children: []},
    6: {id: 6, children: []},
    7: {id: 7, children: []}
  }
};

const tree1 = selector(state1);
const tree2 = selector(state2);
assert(tree1 === tree2);
Member

ellbee commented Sep 27, 2015

Here is the idea I was talking about yesterday. It returns the same object, but at the cost of walking the entire tree to build it and every subtree when stringifying, plus the extra memory that getCachedTree will consume.

import { createSelector } from 'reselect';
import assert from 'assert';
import memoize from 'lodash.memoize';

// return a cached tree if it has been seen before
const getCachedTree = memoize(tree => tree, JSON.stringify);

// build the tree
const selectNode = (nodes, id) => {
  return getCachedTree({
    id,
    title: 'Loading...',
    children: nodes[id].children.reduce(
      (acc, id) => Object.assign(acc, {[id]: selectNode(nodes, id)}),
      {}
    )
  })
}

const selector = createSelector(
  state => state.nodes,
  nodes => selectNode(nodes, 1)
);

const state1 = {
  nodes: {
    1: {id: 1, children: [2,3]},
    2: {id: 2, children: [4,5]},
    3: {id: 3, children: [6,7]},
    4: {id: 4, children: []},
    5: {id: 5, children: []},
    6: {id: 6, children: []},
    7: {id: 7, children: []}
  }
};

const state2 = {
  nodes: {
    1: {id: 1, children: [2,3]},
    2: {id: 2, children: [4,5]},
    3: {id: 3, children: [6,7]},
    4: {id: 4, children: []},
    5: {id: 5, children: []},
    6: {id: 6, children: []},
    7: {id: 7, children: []}
  }
};

const tree1 = selector(state1);
const tree2 = selector(state2);
assert(tree1 === tree2);
@ellbee

This comment has been minimized.

Show comment
Hide comment
@ellbee

ellbee Sep 27, 2015

Member

Modelling the data as a tree inside the reducer just makes everything much more complex in my specific case as the tree is just a view for a data structure that is actually a list (with some plainly visual nested groupings) and 80% of the computations are wasted on constantly flattening the structure for logic as opposed to selecting the view data (neither one is good :/ ).

Oh, OK. I thought from the example that the data structure was simply a tree that had been flattened.

Member

ellbee commented Sep 27, 2015

Modelling the data as a tree inside the reducer just makes everything much more complex in my specific case as the tree is just a view for a data structure that is actually a list (with some plainly visual nested groupings) and 80% of the computations are wasted on constantly flattening the structure for logic as opposed to selecting the view data (neither one is good :/ ).

Oh, OK. I thought from the example that the data structure was simply a tree that had been flattened.

@ronag

This comment has been minimized.

Show comment
Hide comment
@ronag

ronag Sep 27, 2015

Oh, OK. I thought from the example that the data structure was simply a tree that had been flattened.

Well, that sometimes happens when one tries to do a simplified example. Didn't realise it was an important point until after your comments.

ronag commented Sep 27, 2015

Oh, OK. I thought from the example that the data structure was simply a tree that had been flattened.

Well, that sometimes happens when one tries to do a simplified example. Didn't realise it was an important point until after your comments.

@ellbee

This comment has been minimized.

Show comment
Hide comment
@ellbee
Member

ellbee commented Sep 28, 2015

@austinmao

This comment has been minimized.

Show comment
Hide comment
@austinmao

austinmao Nov 23, 2015

I have read through the related issues and am a bit unclear on the specific solution with the combination of a flat structure (a la normalizr) and memoization via reselect. What is the best way to "denormalize" a flattened hierarchical structure for consumption by components? For example, if I want to render a table of all objects from an API call, I would need to convert the flat object to an array. What is the best way to do this?

austinmao commented Nov 23, 2015

I have read through the related issues and am a bit unclear on the specific solution with the combination of a flat structure (a la normalizr) and memoization via reselect. What is the best way to "denormalize" a flattened hierarchical structure for consumption by components? For example, if I want to render a table of all objects from an API call, I would need to convert the flat object to an array. What is the best way to do this?

@oyeanuj

This comment has been minimized.

Show comment
Hide comment
@oyeanuj

oyeanuj Dec 14, 2015

@austinmao: I basically have selectors feeding into each other for every level of normalization. It seems to work fine (except for the problem in #66) but its not uncommon for certain components to have multiple levels of selector composition.

To @austinmao's point, I think it would be great to have a section on the docs that deals with normalized data and best practices when memoizing it.

oyeanuj commented Dec 14, 2015

@austinmao: I basically have selectors feeding into each other for every level of normalization. It seems to work fine (except for the problem in #66) but its not uncommon for certain components to have multiple levels of selector composition.

To @austinmao's point, I think it would be great to have a section on the docs that deals with normalized data and best practices when memoizing it.

@OliverJAsh

This comment has been minimized.

Show comment
Hide comment
@OliverJAsh

OliverJAsh Feb 26, 2018

@oyeanuj Could you provide an example of what you're talking about there?

OliverJAsh commented Feb 26, 2018

@oyeanuj Could you provide an example of what you're talking about there?

@oyeanuj

This comment has been minimized.

Show comment
Hide comment
@oyeanuj

oyeanuj Mar 25, 2018

@OliverJAsh The comment is super old but I think I was referring to something like this where each prop has many levels of selectors feeding into them:

export const getMemberFromRoute = createSelector(
	getMembersState, // <- selector
	getMemberHandle, // <- selector
	( state, handle ) => state && state[handle],
)

export const getMemberNameFromRoute = createSelector(
	getMemberFromRoute,
	member => member && member.name,
)

oyeanuj commented Mar 25, 2018

@OliverJAsh The comment is super old but I think I was referring to something like this where each prop has many levels of selectors feeding into them:

export const getMemberFromRoute = createSelector(
	getMembersState, // <- selector
	getMemberHandle, // <- selector
	( state, handle ) => state && state[handle],
)

export const getMemberNameFromRoute = createSelector(
	getMemberFromRoute,
	member => member && member.name,
)
@natevw

This comment has been minimized.

Show comment
Hide comment
@natevw

natevw Apr 30, 2018

Updated link to "resolved in" issue: reduxjs/redux#815

In that thread @gaearon said:

[…] I think a sane solution is:

  • The component receives its own data via props
  • The component uses connect() to retrieve the data needed to render its children

and pointed to https://stackoverflow.com/questions/25701168/at-what-nesting-level-should-components-read-entities-from-stores-in-flux/25701169#25701169 as a (non-redux) example.

The trade-off to the approach was that "[it] starts to mix smart and dumb components in different levels of the component tree".

natevw commented Apr 30, 2018

Updated link to "resolved in" issue: reduxjs/redux#815

In that thread @gaearon said:

[…] I think a sane solution is:

  • The component receives its own data via props
  • The component uses connect() to retrieve the data needed to render its children

and pointed to https://stackoverflow.com/questions/25701168/at-what-nesting-level-should-components-read-entities-from-stores-in-flux/25701169#25701169 as a (non-redux) example.

The trade-off to the approach was that "[it] starts to mix smart and dumb components in different levels of the component tree".

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment