Slow (Quick-)Type hierarchy for large trees.

[jukzi]

Simple reproducer:

class LargeTree {

	interface I0 {}
	interface I1 extends I0 {}
	interface I2 extends I1, I0 {}
	interface I3 extends I2, I1 {}
	interface I4 extends I3, I2 {}
	interface I5 extends I4, I3 {}
	interface I6 extends I5, I4 {}
	interface I7 extends I6, I5 {}
	interface I8 extends I7, I6 {}
	interface I9 extends I8, I7 {}
	interface I10 extends I9, I8 {}
	interface I11 extends I10, I9 {}
	interface I12 extends I11, I10 {}
	interface I13 extends I12, I11 {}
	interface I14 extends I13, I12 {}
	interface I15 extends I14, I13 {}
	interface I16 extends I15, I14 {}
	interface I17 extends I16, I15 {}
	interface I18 extends I17, I16 {}
	interface I19 extends I18, I17 {}
	interface I20 extends I19, I18 {}
//	interface I21 extends I20, I19 {}
//	interface I22 extends I21, I20 {}
//	interface I23 extends I22, I21 {}
//	interface I24 extends I23, I22 {}
//	interface I25 extends I24, I23 {}
//	interface I26 extends I25, I24 {}
//	interface I27 extends I26, I25 {}
//	interface I28 extends I27, I26 {}
//	interface I29 extends I28, I27 {}
//	interface I30 extends I29, I28 {}
}

On windows ~ 12 seconds to crtl-t I20. Seems to be a non ending story for already I30 - O(2^n) ?

My Vote: by default JDT should not try to expand more then constant number of nodes.
Probably Initial maximum number of elements would be a usefull limit:

[jukzi]

@raghucssit WDYT?

[jukzi]

Or just do not auto-expand nodes that are already expanded elsewhere in the tree? @fedejeanne

[fedejeanne]

Or just do not auto-expand nodes that are already expanded elsewhere in the tree? @fedejeanne

That would make sense for me since those items don't bring much information with them, but I think it is just a patch, right? I mean the real problem is that opening big trees is slow (vi-eclipse/Eclipse-Platform#123) and this solution would translate to "create smaller trees".

In any case, if that approach is a quick win then I am all for it.

[jukzi]

quick win then I am all for it.

Quick but huge win! for so large trees it's only a matter of moderate n to get problems no matter how fast it is. Can you provide such PR?

[fedejeanne]

Can you provide such PR?

Not at the moment but I already pinged some of my students which I know took a look at the issue.

One really quick win would be:

... but I assume that's out of the question?

[jukzi]

... but I assume that's out of the question?

yes, no way

[raghucssit]

@raghucssit WDYT?

Good idea, It avoids UI freeze. I will create a PR.

[raghucssit]

I tried with limit set to 10. It seems to work fine. Hopefully no tests will have problem..!!

[fedejeanne]

I tried with limit set to 10. It seems to work fine. Hopefully no tests will have problem..!!

@raghucssit this approach doesn't solve the problem described in #1830 (comment) because that specific hierarchy has "only" 1 child. The problem is that expanding that child also expands the children and that ends up creating and expanding about 17.000 items.

In order to reproduce the error, you should use the snippet provided in this Issue

[raghucssit]

I tried with limit set to 10. It seems to work fine. Hopefully no tests will have problem..!!

@raghucssit this approach doesn't solve the problem described in #1830 (comment) because that specific hierarchy has "only" 1 child. The problem is that expanding that child also expands the children and that ends up creating and expanding about 17.000 items.

In order to reproduce the error, you should use the snippet provided in this Issue

I think Viewer Limit is applied to all levels of the tree. so in the second level also only limited number of items will be shown.
I have created PR. Please check if it works as expected.

[jukzi]

A limit per Node will not solve the issue the issue with a binary tree (i.e. only 2 children per node) that still has a huge amount of nodes in total. We could add both: 1. limit per node and 2. not autoexpand nodes twice in a tree.

[fedejeanne]

A limit per Node will not solve the issue the issue with a binary tree (i.e. only 2 children per node) that still has a huge amount of nodes in total. We could add both: 1. limit per node and 2. not autoexpand nodes twice in a tree.

Exactly. See #1831 (review)

[raghucssit]

A limit per Node will not solve the issue the issue with a binary tree (i.e. only 2 children per node) that still has a huge amount of nodes in total. We could add both: 1. limit per node and 2. not autoexpand nodes twice in a tree.

autoexpand should be set false. otherwise it's like a loop.
Another possibility is to limit this autoexpand to viewer limit. That needs to investigated.
Currently I am busy on some other task. I will check it later.