Major scaling/performance issues with node.addChildren()

[aleventhal]

Expected and actual behavior

Expected: fast performance when using node.addChildren()
Actual: performance degrades drastically as the tree fills up. In the case of the automation inspector I'm writing, where I'm using the tree grid for a log that has grouped log items, first the app begins to take 3+ seconds to responds and ultimately rejects user input.

Steps to reproduce the problem

1. Create a tree with many nodes, 2 levels deep. Add 500 top level nodes, each with 500 child nodes.
2. Add a child to the root

Environment

• Browser type and version: Chrome latest
• jQuery and jQuery UI versions: 3.1.1 and 1.12.1
• Fancytree version: 2.21.0
  enabled/affected extensions:
  Also using filter and table extensions.

What I learned in debugging the problem

First, thank you for such a great library. The ARIA and accessibility feature are especially important to us at Google. I'm using this to develop a Chrome automation API inspector app. You can see it here: https://github.com/aleventhal/automation-inspector

Here are my observations:

• The class attribute is rewritten to nodes that have not changed. In my experience, even though it is counterintuitive, this affects performance more than checking to see if the class needs to be rewritten before doing so. I'm not sure how much of a difference it would make but I believe it would help. I haven't tried to implement this.
• Moreover, every time a node is added to the root, the entire tree is re-rendered. This does not seem necessary. Why not just render the new children? This is probably not the exact right change but it really helped solve my performance issue by a huge amount:

Old code (line 441 of jquery.fancytree.js in addChildren() )

		if( !this.parent || this.parent.ul || this.tr ){
			// render if the parent was rendered (or this is a root node)
			this.render();
		}

New code:

		// --- Begin performance improvement change  ---
		if (!this.parent) {
			// Fast path -- don't render every child of root, just the new ones!
			for(i=0, l=nodeList.length; i<l; i++) {
				nodeList[i].render();
			}
		}
		else if( this.parent.ul || this.tr ){
			// render if the parent was rendered (or this is a root node)
			this.render();
		}
		// --- End performance improvement change  ---

[mar10]

Cool, thanks for the feedback!
I am always very interested in performance improvements and I will try this.
There already is a benchmark suite, in case you didn't notice:
http://wwwendt.de/tech/fancytree/test/unit/test-bench.html

Btw. if you are adding entries in bursts, you could try to temporarily disable updates using tree. enableUpdate().

Would be interesting to see a live demo of your tool.
Since you are talking about using Fancytree for logging: how many nodes (visible and total) are you expect to have max.?
Beyond any optimizations, in my experience browser performance degrades drastically for large tables (event if Fancytree is not involved).

p.s.
Since you seem to be an ARIA expert: if you have suggestions to improve the markup, let me know. I tried to follow the guidelines, but I am not really sure if the current implementation offers the best user experience (on different browsers or screen readers).

[aleventhal]

Nice to hear from you. I know about enableUpdate, but it won't help in this situation as I'm really adding one new child with grandchildren already attached to it. It makes sense that tables would degrade when they get large. That's why, as far as max # of items, I decided to limit the number of top level items, which are currently all collapsed by default, to 20. However, each of those can seem to have a few thousand invisible items. When I profiled the code, it appeared that my theory that rerendering all of the siblings of the added child was causing the biggest performance issues, and my fix did seem to make a difference. Regarding ARIA, I agree, let's work together on this. It's a great start, especially for regular trees. I'll open a separate issue for treegrid.

…

On Wed, Mar 22, 2017 at 4:52 PM, Martin Wendt ***@***.***> wrote: Cool, thanks for the feedback! I am always very interested in performance improvements and I will try this. There already is a benchmark suite, in case you didn't notice: http://wwwendt.de/tech/fancytree/test/unit/test-bench.html Btw. if you are adding entries in bursts, you could try to temporarily disable updates using tree. enableUpdate() <http://wwwendt.de/tech/fancytree/doc/jsdoc/Fancytree.html#enableUpdate>. Would be interesting to see a live demo of your tool. Since you are talking about using Fancytree for logging: how many nodes (visible and total) are you expect to have max.? Beyond any optimizations, in my experience browser performance degrades drastically for large tables (event if Fancytree is not involved). p.s. Since you seem to be an ARIA expert: if you have suggestions to improve the markup, let me know. I tried to follow the guidelines, but I am not really sure if the current implementation <http://wwwendt.de/tech/fancytree/demo/sample-aria.html> offers the best user experience (on different browsers or screen readers). — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#708 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABUAZiJ5TrvIXt2sYrMIMIY8G2POBfs8ks5roYokgaJpZM4Mlfor> .

[mar10]

Thanks, I will look into it.
It would be good to have a benchmark to compare optimization results.
I tried to create 500x500 nodes (500 nodes top-level, 250k overall), the top-level nodes being collapsed.
I measured ~2-3 seconds. Adding another top-level node took ~20ms.
Even if I did not yet apply your patch, that seems to be faster than the effect you are describing?
I assume, timings may be inacurate, because the JS code is done, but the browser still has not finished rendering. I am going to experiment a bit more...

[aleventhal]

Right, I'm talking about several seconds delay for each additional child being added. Sounds like I'll need to get you more info. What happens if the top level nodes are not collapsed? I know that this is going to be slow partially due to it being a huge table in general, and that's a lot for the browser. Aaron

…

On Fri, Mar 24, 2017 at 3:39 AM Martin Wendt ***@***.***> wrote: Thanks, I will look into it. It would be good to have a benchmark to compare optimization results. I tried to create 500x500 nodes (500 nodes top-level, 250k overall), the top-level nodes being collapsed. I measured ~2-3 seconds. Adding another top-level node took ~20ms. Even if I did not yet apply your patch, that seems to be faster than the effect you are describing? I assume, timings may be inacurate, because the JS code is done, but the browser still has not finished rendering. I am going to experiment a bit more... — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#708 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABUAZoId6Y-LL0d_kusErTmjLDar0A6_ks5ro3NDgaJpZM4Mlfor> .

[mar10]

I added a benchmark to the suite the seems to better simulate the case.
Don't know if this matches your timings better...

It makes a difference, if the nodes are collapsed/unrendered, collapsed/rendered, or expanded. Your optimization seems to work best in the latter case.

	for( var i=0; i<20; i++ ) {
	// 	node.children[i].render(true, true);
		node.children[i].setExpanded(true);
	}

bench_issue_708.pdf

Would you like to make a PR?

Another thing you might try is to remove markup when nodes are collapsed, and see if it makes a difference, when your is used for a while:

	$("#tree").fancytree({
		collapse: function(event, data) {
			data.node.discardMarkup();
		},

[aleventhal]

Hi Martin, I uploaded a PR for something else related to click-to-focus. I'm ready to begin this PR, but I wanted to mention that I agree that this is really only a problem when nodes are expanded. I see this comment in the jquery.fancytree.js in two places * <li>If a node was created/removed, node.render() must be called <i>on the parent</i>. My thinking is that this is necessary in order to rerender the collapse/expand icon. Basically when we go from 0 children to some, or vice-versa, Fancytree will have to toggle whether the icon is visible. I tried looking back into the code to see if this was why, but I couldn't figure it out. The reason my patch is ok, I think, is that the root node isn't rendered anyway, so there is no collapse/expand icon. Whether the parent of the added/removed child is the root node or node or not, I don't think rendering all the siblings of the current item should be necessary. Doesn't it seem like enough to render the parent, but not to do so recursively? - Aaron

…

On Sat, Mar 25, 2017 at 10:57 AM Martin Wendt ***@***.***> wrote: I added a benchmark to the suite <https://github.com/mar10/fancytree/blob/master/test/unit/test-bench.js#L351> the seems to better simulate the case. Don't know if this matches your timings better... It makes a difference, if the nodes are collapsed/unrendered, collapsed/rendered, or expanded. Your optimization seems to work best in the latter case. for( var i=0; i<20; i++ ) { // node.children[i].render(true, true); node.children[i].setExpanded(true); } bench_issue_708.pdf <https://github.com/mar10/fancytree/files/870116/bench_issue_708.pdf> Would you like to make a PR? Another thing you might try is to remove markup when nodes are collapsed, and see if it makes a difference, when your is used for a while: $("#tree").fancytree({ collapse: function(event, data) { data.node.discardMarkup(); }, — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#708 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABUAZr0ZI6NkRIgGZDfIrsHLwDVkVBFjks5rpStKgaJpZM4Mlfor> .

[aleventhal]

Uploaded a second PR for the new addChildren() improvements. Passes automated tests and some minor manual testing.

…

On Fri, Mar 31, 2017 at 12:27 PM Aaron Leventhal ***@***.***> wrote: Hi Martin, I uploaded a PR for something else related to click-to-focus. I'm ready to begin this PR, but I wanted to mention that I agree that this is really only a problem when nodes are expanded. I see this comment in the jquery.fancytree.js in two places * <li>If a node was created/removed, node.render() must be called <i>on the parent</i>. My thinking is that this is necessary in order to rerender the collapse/expand icon. Basically when we go from 0 children to some, or vice-versa, Fancytree will have to toggle whether the icon is visible. I tried looking back into the code to see if this was why, but I couldn't figure it out. The reason my patch is ok, I think, is that the root node isn't rendered anyway, so there is no collapse/expand icon. Whether the parent of the added/removed child is the root node or node or not, I don't think rendering all the siblings of the current item should be necessary. Doesn't it seem like enough to render the parent, but not to do so recursively? - Aaron On Sat, Mar 25, 2017 at 10:57 AM Martin Wendt ***@***.***> wrote: I added a benchmark to the suite <https://github.com/mar10/fancytree/blob/master/test/unit/test-bench.js#L351> the seems to better simulate the case. Don't know if this matches your timings better... It makes a difference, if the nodes are collapsed/unrendered, collapsed/rendered, or expanded. Your optimization seems to work best in the latter case. for( var i=0; i<20; i++ ) { // node.children[i].render(true, true); node.children[i].setExpanded(true); } bench_issue_708.pdf <https://github.com/mar10/fancytree/files/870116/bench_issue_708.pdf> Would you like to make a PR? Another thing you might try is to remove markup when nodes are collapsed, and see if it makes a difference, when your is used for a while: $("#tree").fancytree({ collapse: function(event, data) { data.node.discardMarkup(); }, — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#708 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABUAZr0ZI6NkRIgGZDfIrsHLwDVkVBFjks5rpStKgaJpZM4Mlfor> .

[mar10]

I don't think that the test suite covers all use cases, but anyway: looks good to me.
I merged your changes, thanks! Let's see, what happens.
Concerning the

node.render() must be called on the parent.

comment: I believe that was also related to cases where the children list was modified directly. The render() method also takes care to keep the <li> order order in sync with the model's node list, for example.

[mar10]

PR was merged

[marczi]

I think with this modification in version 2.22 the insertBefore parameter for addChildren is buggy. Let's say I have 3 elements and I'd like to add a node before the 3rd one. Now the node is added to the correct position in the "children" list, but it is always renderer as it were added after the last node. It is working correctly in version 2.21

[aleventhal]

I put up a PR to fix this but keep the optimization.

[marczi]

Thanks for your fix, but unfortunately it still seems to be a little buggy (now it is better than it used to be). The most simple use case is to create a tree with a single node and try to add a second node before this first node. In version 2.21 the newly added node appears correctly before the original single node, but in 2.22.1 it appears after that. The only workaround is to call render(true) on the root node.