#619 Made TreeView stable

Post here if you have re-based and finalised code to integrate into master, which was discussed, agreed to and tested in other forums.
DeepSOIC
Posts: 4443
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: #619 Made TreeView stable

Postby DeepSOIC » Thu Mar 16, 2017 10:46 am

Just having some fun :P
chicken-egg-tree.png
chicken-egg-tree.png (116.4 KiB) Viewed 146 times
DeepSOIC
Posts: 4443
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: #619 Made TreeView stable

Postby DeepSOIC » Thu Mar 16, 2017 10:52 am

realthunder wrote:The cyclic check only happens when a free item (i.e. an item at document root) is newly claimed, which already has children. The check needs to visit all its children. That's the only case requiring a check.
Maybe it can be made faster by going the other way around? i.e. when adding an object as child of something, and withdrawing it from root, look up the ultimate parent of something and check if it is the child being added? This way, the performance penalty is proportional to depth of tree, which isn't going to be too big anyway?
DeepSOIC
Posts: 4443
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: #619 Made TreeView stable

Postby DeepSOIC » Thu Mar 16, 2017 10:56 am

realthunder wrote:The cyclic check only happens when a free item (i.e. an item at document root) is newly claimed, which already has children. The check needs to visit all its children. That's the only case requiring a check. We'd be creating new items (without children obviously) for all other cases. So, I think the performance impact should be limited.
So as far as I understand, it's pretty rare, so can be ignored.
realthunder
Posts: 91
Joined: Tue Jan 03, 2017 10:55 am

Re: #619 Made TreeView stable

Postby realthunder » Thu Mar 16, 2017 11:05 am

:lol:

DeepSOIC wrote:Maybe it can be made faster by going the other way around? i.e. when adding an object as child of something, and withdrawing it from root, look up the ultimate parent of something and check if it is the child being added? This way, the performance penalty is proportional to depth of tree, which isn't going to be too big anyway?

I doubt there is any shortcut. When reparenting the root item, you'll never know what's in its children until a full visit.

The performance impact will only kick in when it needs to visit large number of children and find it's actually fine, or only find the cycle at the near end. I'd expect it may have impact on loading large document. Not sure though, if the parent children relationship is saved and not inferred during loading, and loaded in order of parent first, then it should be fine too. But, even if it is the worst, that it has to visit each children recursively (that's factorial n! maybe?), the checking time won't be significant comparing to restoring actually geometry data.

So yeah, I guess it should be fine.
DeepSOIC
Posts: 4443
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: #619 Made TreeView stable

Postby DeepSOIC » Thu Mar 16, 2017 12:44 pm

realthunder wrote:visit each children recursively (that's factorial n! maybe?)
n! !?? If so, it's awful, since factorial of just 13 is already over 1G. And a factorial of 20 will take about 100 years to traverse.
realthunder
Posts: 91
Joined: Tue Jan 03, 2017 10:55 am

Re: #619 Made TreeView stable

Postby realthunder » Thu Mar 16, 2017 3:21 pm

DeepSOIC wrote:
realthunder wrote:visit each children recursively (that's factorial n! maybe?)
n! !?? If so, it's awful, since factorial of just 13 is already over 1G. And a factorial of 20 will take about 100 years to traverse.

Oops, I mean 1+2+3..+n, not multiple, n(n+1)/2. This is the case where all child items are loaded before its parent.
DeepSOIC
Posts: 4443
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: #619 Made TreeView stable

Postby DeepSOIC » Thu Mar 16, 2017 5:22 pm

realthunder wrote:Oops, I mean 1+2+3..+n, not multiple, n(n+1)/2.
Haha, that's just O(n^2), which is a heaven of a difference compared to the factorial :lol: .

I just gave it compound->explode->compound->... torture again, and with tree potentially expandable to about 4 gigaleaves, I had no noticeable slowdown.
User avatar
bernd
Posts: 3868
Joined: Sun Sep 08, 2013 8:07 pm
Location: Zürich, Switzerland

Re: #619 Made TreeView stable

Postby bernd » Sun Mar 19, 2017 11:26 pm

Just tested the branch on Debian Jessie and played a bit. Wow thats cool. The objects in TreeView do no longer jump around :D :D