Improve Search Performance with large number of nodes

[mrchief]

Based on feedback from here and here, need to improve search performance.

[josvegit]

The structure of the data I was talking about is the following (I'll try to get actual data tomorrow, its very late for me now (from sweden))

X1 = {
value: xxx
label: yyy,
filterString: zzz,
children: [Y1, Y2,, Y3....]
}

The top level array is a bunch of Xa elements, 25 to be exact. Each Xa element has a bunch of children. These children have children of their own. A basic tree structure.

I think the maximum depth is not that big, prob 5-6 levels. But each levels can have lots of children. Just looking through the data now, the first 3 of the 25 top level nodes have 71, 230, 33 children. These in turn have children etc

I guess the tree is short but wide rather than deep and thin (if that even makes sense..)

I'm going to bed now

[mrchief]

I tried generating large dataset but all tools crapped out (some had node limits, some managed to bring mighty chrome to its knees). Guess I'll have to wait for your inputs. :)

[josvegit]

scrambledData.txt

Try this, its a json => the data begins under data.children.

it has the form => {label: XX, value: YY, type: ZZZ, children: [list of other entities]}

go https://jsonlint.com/ here and copy it in to get the ide of the structure. Let me know if there is anything else you need, like my code or something

[mrchief]

Thanks for this. I'll start digging into it.

[mrchief]

Just wanted to update on this - I did some performance profiling and found that:

• The tree nodes already handle virtual rendering (render only whats visible) but when searching, it tries to render all matching nodes and that's where it chokes if you have 1000s of nodes.

• Even with current approach to virtual rendering, the performance will suffer if a expanded node has 100s of children.

The solution (which is also an item on the roadmap) is to use virtual lists - i.e. only render what's visible at all times (during searchMode, or even when a node is expanded). The difference is that of day & night.

Bad news is, I've tried all existing off the shelve components and none of them can be used as-is.

The ones I tried are:

• react-virtualized - too big, has lot of things but we don't need most of it. Completely breaks backward-compatibility, search mode shows blank rows since it wraps every list item with static height.
• react-tiny-virtual-list - smaller, same issues as above.
• react-virtual-list - simplest, most backward-compatible of all. Barring one style issue, it works perfectly without requiring to change the current markup structure. But this and this are blockers.

I'll try to get in touch with the developer and see if he's willing to accept/merge my PRs quickly. Else, I'll have to fork and roll my own.

[josvegit]

Your doing gods work man, ill see if I can try also. You have a branch or something for it ?

[mrchief]

Yes, take a look at perf-tweaks branch. I've pushed stable bits so far (there are few required props warnings but you can ignore them - I'll get to them later).

Updates so far:

• Use PureComponents to reduce wasteful renders - brings down tree reconciliation time from ~40ms to ~5ms on my box. Useful but not much since the tree virtualizes a lot already.
• A story with large tree to play with. Its slow right now. So when it's not, you know you've fixed the issue! :)
• I played with react-virtual-list but stashed those changes. I also tried to roll something tailor-made to the component but that's also stashed as it wasn't very stable.

Happy hacking!

[josvegit]

Nice, ill have a go at it this weekend

[mrchief]

Just pushed a change with infinite loader. This seems the most promising so far. One issue I've found so far is that upon checkbox change, it closes the dropdown. Need to dig deeper.

[josvegit]

Cool ill have a look later today

[josvegit]

sry did not have time to look at it, lots of stuff going on, ill try next weekend

[mrchief]

No worries. I got it working (albeit with a funny effect as you check/uncheck nodes, if you've scrolled). I'm refactoring some of the code to use PureComponents. Tests are screaming at me now.

[mrchief]

Pushed a working cut. There's few finishing touches to be done but its mostly there. Here's a SS of the scroll effect:

Also, the tests for tree (where it does a full mount(<Tree ... />)) error out with out of memory exception. react-infinite-scroll-component seems to be the problem here (as without it, the tests work just fine).

For the scroll effect - I think it'd need a bigger refactor to eliminate - basically the tree, once rendered, should not be re-rendered during search. To do so, tree rendering, updation of sibling/parent nodes etc will have to move down, to the tree component.

For the test - I can workaround it but I wonder if the tests are pointing towards a potential problem. The 3rd party component itself doesn't have much tests.

Another approach would be to not use any 3rd party component. Instead, render first 100 nodes and have a "load more" item at the end. Rationale being that the bottleneck occurs during first few keystrokes while searching, as it tries to render all matching nodes (15k). By rendering the first 100, we eliminate that bottleneck.

And in most cases, user will type 3-4 chars at least before settling down - at which point the list will be a reasonable size - well below the choke point.

While this lacks the "cool" factor of infinite scroller, it provides a leaner component, less 3rd party dependencies and avoids above hassles.

If there is a demand in future to have something like infinite scroller, we can add it later. But for now, it gets a viable solution out the door.

Thoughts?

/cc @toofff @Gregcop1

[josvegit]

dude your my hero, I would tell you what company is using this component (it is a big one) but with that info and that half ass scrambled data a smart person like yourself would have much too much information :)

[mrchief]

This just landed in v1.11.0. Thanks for the patience @josvegit!

[hoffiez]

Don't understand how to make this feature work. How to enable scrolling? I set max-height in the css for the ".infinite-scroll-component" - the scrollbar appears, but new items don't appear when scrolling to the bottom. Thus, the results are truncated to 100 items. Version ^2.3.6

[mrchief]

@hoffiez You can take a look at the CSS in the demo. You don't need to do anything if you're bringing in the base CSS and not overriding everything.

[mrchief]

If the issues still persists, I'd suggest creating a new issue with a CodeSandbox.

[hoffiez]

@hoffiez You can take a look at the CSS in the demo. You don't need to do anything if you're bringing in the base CSS and not overriding everything.

Fixed by adding max-height and overflow-y: auto in the CSS for the .dropdown-content element instead of .infinite-scroll-component. Now the scrolling works fine, thanks!

I didn't have it worked by default because I used the material-design example from here https://dowjones.github.io/react-dropdown-tree-select/#/story/with-material-design-styles where infinite scrolling was not implemented as I guess.

[gandhis1]

Fixed by adding max-height and overflow-y: auto in the CSS for the .dropdown-content element instead of .infinite-scroll-component. Now the scrolling works fine, thanks!

The problem here is that if you have an inline search box, then adding the scrolling to dropdown-content makes the search box disappear, which isn't ideal

[mrchief]

Hey @gandhis1 - please open a new issue with a codesandbox to reproduce it. Commenting on a closed issue is not the right place for this.