treeWalker is walking all nodes

[murrayju]

I'm using 3.0.0-beta.1. It seems that my provided treeWalker generator is being walked to visit every node in the tree, even though most of the nodes are not visible (collapsed).

Is this how it is intended to function, or am I missing something? My use case involves a tree that is very large and very deep, and computing the nodes is somewhat expensive. Users only visit a small subset of the nodes at a time, so my hope was that the treeWalker would only visit the visible nodes and save a bunch of unnecessary computation.

As it is, there is a very noticeable (few seconds) delay on expanding/collapsing nodes (because the walks the tree again).

[murrayju]

To follow up on this: I modified my generator such that it doesn't produce the child nodes for a parent that is collapsed. This seems to solve my performance problem, but it makes the built-in expanded/collapsed state management useless, and requires me to provide a new treeWalker to rerender the entire tree every time a node is toggled. This really feels far from optimal. I'd like to understand if I'm missing something, or if this is the intended design.

[Lodin]

Hi @murrayju

It seems that my provided treeWalker generator is being walked to visit every node in the tree, even though most of the nodes are not visible (collapsed).

The treeWalker generator is designed to be flexible. If you don't want to provide all the tree data at once, you could use the async approach (code, demo). So the user will get only the information they requested while the tree won't suffer from unnecessary data processing.

There is a very noticeable (few seconds) delay on expanding/collapsing nodes (because the walks the tree again).

Actually, only the 2.x.x version used treeWalker both for tree building and for node expanding/collapsing operations. The 3.0.0 version introduces a new approach when the treeWalker is used only for tree building. So it shouldn't affect the expanding/collapsing which uses the internal tree walk based on pointers. Could that be possible that you are using the 2.x.x version instead of 3.x.x?

However, unfortunately, for the very large trees, there still may be some delay on collapsing/expanding because the tree needs to walk through all the nodes to create (or, more importantly, re-create) the correct list of nodes to display in the virtual table. To fix that case, I would suggest considering the async approach as well.

[murrayju]

Could that be possible that you are using the 2.x.x version instead of 3.x.x?

No, definitely on v3. I just didn't explain what I meant very well. My approach was to use useCallback to produce a new treeWalker whenever the expandedKeys change (since my tree walker only walks the children of nodes that are expanded, it has to change when the expanded state changes). This in turn causes react-vtree to rerender the whole tree.

I chose this as the better of two evils, since the alternative (treeWalker always provides the complete tree) is way slower than only walking the expanded nodes of a mostly collapsed tree.

To fix that case, I would suggest considering the async approach as well.

I'll take a look at the async option, thanks. I shied away from this at first, since my data isn't truly "async", it is all in memory already.

---

I created this ticket mostly because I find it surprising that the library should have to walk the generator for nodes that are not visible. Perhaps you are optimizing for something else that I'm not aware of? I could look into making a fork if my use case is just different from others, but I'd like to understand why yours is designed this way first.

[Lodin]

Perhaps you are optimizing for something else that I'm not aware of?

The initial goal was to optimize the display of the tree. When the treeWalker works, it creates an internal representation of a tree that consists of two elements: a tree object connected via pointers (parent-child-sibling) and an array of node ids to send to the react-window virtual table.

Whenever the treeWalker is changed, the internal representation is re-created from scratch. That's a very time- and resource-consuming operation because there is a lot of memory allocation for objects and the array. So I recommend using it either once at the start or via an async approach. If it is essential to not freeze the whole UI during the tree building, it is also possible to specify a placeholder property that will make tree construction asynchronous. So you can just show the user a spinner until the tree is prepared. The approach is described here (code, demo).

For expanding/collapsing, the internal tree walk is used. As I described above, it just walks over the tree using the pointers and updates the tree node visibility state. However, in my previous explanation, I made a mistake: not all the nodes are visited during that walk but only a subtree of a node that is triggered. When the walk is over, the prepared sub-array is injected via Array.prototype.splice into the main react-window array. If you have big branches, that may take some time but according to my experiments, the lag is not big and happens mostly because of GC.

Hope that explanation will help you.