Reduce necessity of tree full tree walk

[issacgerges]

I was curious if you had considered any performance optimizations around the need for a full tree walk. I think one of the great parts of the iterator model is that you have the ability to progressively walk the tree as the user scrolls.

Couple this with the consistent height of elements, and it's possible to calculate what element you need to start iterating from to service any request.

Curious if performance optimizations like those were ever intended to be a part of react-vtree or if that's not the problem you're trying to solve.

[Lodin]

I thought about this idea while creating the library. However, there is a fundamental problem hidden in the JS iterator protocol that makes it impossible to implement.

The fact is that the idea works fine when you are scrolling down. Iterator gives you new elements, and everything is ok. However, if you suddenly decide to scroll up, what should the iterator do? It cannot stop until the iteration is over; it has no previous method. It just cannot iterate backward.

In the end, I couldn't get any idea of how to implement the two-way iteration. react-window solves this by incrementing/decrementing the current array index and extracting the necessary element directly from the array. But this approach is impossible for the tree structure. If you have any idea, feel free to share it! I would be glad to take a fresh look at this issue.

[issacgerges]

I think there might be options here.

The first is a pagination model, where you can scrub the iterator around to any arbitrary index. Knowing the size of items and the momentum of the scroll, you should be able to reason about where to start

   iter.next(); //0th index
   iter.next(); //1st index
   iter.next(10);  //10th index
   iter.next(); //11th index

Demo here: https://jsfiddle.net/6Lu5dxkp/5/

The second is similar to the first, but actually lets you scrub by a relative amount (adding the ability to walk backward)

   iter.next(); //0th index
   iter.next(); //1st index
   iter.next();  //2nd index
   iter.next(-1); //1st index

Demo here: https://jsfiddle.net/60efjbow/

I think there may even be a last option, which is a bit more convoluted but uses two iterators and some shared state. So imagine a class that encapsulated a forwards and backward iterators that exposed a next and previous which could manage the state to scrub either when the direction was changed. (If the backward iterator scrubs back 20 elements, then when we start moving forward we need to scrub the forward iterator to that element before calling next)

[Lodin]

Thanks for examples, I have gone through them and have some thoughts.

First of all, they are focusing on arrays. The problem is that the tree is not an array. If we work with arrays, we don't even need the iterator because react-window has excellent support for them via the React component that receives the current index as property and decides how to render the appropriate element.

So, let's get through the conditions we have.

• A tree with any structure. We cannot impose a structure we would like to have on users because it will force them to convert the data before using the Tree component.
• A react-window interface that works with arrays only. In the bottom line, it has only the number of indexes, the row height, and a row component that decides by index what to display.
• A node state system that allows the user to decide when to display the subtree of the specific node.

The current library mechanism works in the following way:

• When the component is mounted, the treeWalker generator goes around the tree, collects all the nodes the user wants to display by default, and prepares an array that will serve as a source of truth for react-window.
• Then react-windows displays nodes from the prepared array using the Node component, which is wrapped in the default Row component (can be altered via the rowComponent property). For static trees, everything ends here, and they don't use the rest of the library.
• If the tree is dynamic, the node state system enters the scene. The Node component receives a toggle function that fires the node toggle event. treeWalker goes around the tree again, but the node the event is fired for will have a different openness state. Based on this state, users decide if they need to yield the node's children (in other words, if those children are displayed).

To reduce the necessity of the array in the middle, we need to solve the following issues:

• How can we get the amount of the currently displaying tree nodes to send them as itemCount for react-window?
• How can we associate the react-window index with the specific tree node and re-associate it on the toggle event when the amount of displaying nodes is changed?
• How can we go outward from within the tree if we get the node by it's associated index? E.g., we have a tree data structure with the three-level nesting. We have a grand-child node; how can we get its parent or grand-parent?

Probably, this is not the full list of questions to solve, but for now, I don't have answers for them. And I would be glad to see some ideas on them.

[Lodin]

Due to lack of recent activity I'm closing this issue. Feel free to reopen it if you have some fresh thoughts.

[Lodin]

Reopening the issue to get it visible for users who have the same thoughts and questions.

[AlokBisht]

@Lodin thanks for reopening the issue. I read the thread. So another basic question is, can we convert tree walk to only ask for data when that node is scrolled into the view , once data for a node is generated, keep it until treewalker object is changed, and we end up recomputting everything??

[Lodin]

@AlokBisht, yes, that's what I've done in fix/performance-on-big-data branch (diff). And while it helps improving the performance a bit, it is still restricted with the necessity to re-create the array of node IDs according to the openness state of nodes. So, basically, the algorithm breaks to the following steps:

1. Initial step. Runs only when the treeWalker changes (it also means that the tree data is changed). It is defined by refresh boolean value sent as the parameter to the treeWalker function. If the refresh is true I have to give the component the new node data.

const isOpened = yield refresh
  ? { // This is the data returned on initial step
      id,
      isLeaf: node.children.length === 0,
      isOpenByDefault: true,
      name: node.name,
      nestingLevel,
    }
  : id;

2. Visibility update step. Runs each time the node open/close action is performed. refresh is false, and I need to return only the ID of the node which goes to the array that is used as a source for the react-vtree. This array's existence seems inevitable to me because it is necessary for displaying visible nodes. Each time the node opens and closes its children have to be shown or hidden, and I haven't found another way except for running the treeWalker each time to get IDs of visible components. Hidden components are just not traversed.

The tree traversing is the bottleneck as I can see. Traversing the whole tree of such size and creating a giant array freezes page for the noticeable time. I already changed the treeWalker example: it uses pointers instead of a stack but it still takes too much time to work. So I would be glad to hear any thoughts on how to reduce the complexity of this operation.

[AlokBisht]

TBH, I don't have any valuable suggestion right now. I'm taking the code and trying it now. btw what is the performance gain on your branch? did you create any matrix or anything?

[Lodin]

As I already mentioned in #30, I believe I have solved the performance issues with the tree updates. It still takes some time to build the tree from scratch but at least you may be free from UI freezing when nodes open/close.

@AlokBisht, sorry, no metrics for the performance, I'm checking the speed by hands only.