#619 Made TreeView stable

Merged, abandoned or rejected pull requests are moved here to clear the main Pull Requests forum.
DeepSOIC
Posts: 4670
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 276 times
DeepSOIC
Posts: 4670
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: 4670
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: 151
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: 4670
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: 151
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: 4670
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: 3924
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
User avatar
NormandC
Posts: 12262
Joined: Sat Feb 06, 2010 9:52 pm
Location: Québec, Canada

Re: #619 Made TreeView stable

Postby NormandC » Sat Apr 01, 2017 11:26 pm

Hello,

Would you please have a look at this topic and tell me if I'm making wrong assumptions? In which case I apologize. :oops:

Re: Odd behaviour with Part Design Boolean/Part Fusion operations https://forum.freecadweb.org/viewtopic.php?f=3&t=21607&p=168246#p168246

tl;dr: bringing an inactive Body into an active one using a Boolean operation feature seems to create a second instance of the "imported" Body. IMO this is not desired, and I don't remember seeing this behaviour before. I thought this might be a side effect of the treeview changes, but I am not a developer.

As for the two other issues I mention, I doubt they are related.

I'll try to compile FreeCAD from a prior commit to test...

Thanks!
DeepSOIC
Posts: 4670
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: #619 Made TreeView stable

Postby DeepSOIC » Sat Apr 01, 2017 11:51 pm

NormandC wrote:tl;dr: bringing an inactive Body into an active one using a Boolean operation feature seems to create a second instance of the "imported" Body. IMO this is not desired,
This is desired IMO, because visibility of body used for boolean operation does not depend on visibility of the body that contains the Boolean operation. But according to code, Part shouldn't claim the used body as child anymore, so there is likely a bug somewhere.