#619 Made TreeView stable
- DeepSOIC
- Veteran
- Posts: 7896
- Joined: Fri Aug 29, 2014 12:45 am
- Location: used to be Saint-Petersburg, Russia
Re: #619 Made TreeView stable
Just having some fun
- DeepSOIC
- Veteran
- Posts: 7896
- Joined: Fri Aug 29, 2014 12:45 am
- Location: used to be Saint-Petersburg, Russia
Re: #619 Made TreeView stable
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?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.
- DeepSOIC
- Veteran
- Posts: 7896
- Joined: Fri Aug 29, 2014 12:45 am
- Location: used to be Saint-Petersburg, Russia
Re: #619 Made TreeView stable
So as far as I understand, it's pretty rare, so can be ignored.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.
-
- Veteran
- Posts: 2190
- Joined: Tue Jan 03, 2017 10:55 am
Re: #619 Made TreeView stable
I doubt there is any shortcut. When reparenting the root item, you'll never know what's in its children until a full visit.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?
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
- Veteran
- Posts: 7896
- Joined: Fri Aug 29, 2014 12:45 am
- Location: used to be Saint-Petersburg, Russia
Re: #619 Made TreeView stable
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 wrote:visit each children recursively (that's factorial n! maybe?)
-
- Veteran
- Posts: 2190
- Joined: Tue Jan 03, 2017 10:55 am
Re: #619 Made TreeView stable
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 wrote: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 wrote:visit each children recursively (that's factorial n! maybe?)
- DeepSOIC
- Veteran
- Posts: 7896
- Joined: Fri Aug 29, 2014 12:45 am
- Location: used to be Saint-Petersburg, Russia
Re: #619 Made TreeView stable
Haha, that's just O(n^2), which is a heaven of a difference compared to the factorial .realthunder wrote:Oops, I mean 1+2+3..+n, not multiple, n(n+1)/2.
I just gave it compound->explode->compound->... torture again, and with tree potentially expandable to about 4 gigaleaves, I had no noticeable slowdown.
Re: #619 Made TreeView stable
Just tested the branch on Debian Jessie and played a bit. Wow thats cool. The objects in TreeView do no longer jump around
Re: #619 Made TreeView stable
Hello,
Would you please have a look at this topic and tell me if I'm making wrong assumptions? In which case I apologize.
Re: Odd behaviour with Part Design Boolean/Part Fusion operations https://forum.freecadweb.org/viewtopic. ... 46#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!
Would you please have a look at this topic and tell me if I'm making wrong assumptions? In which case I apologize.
Re: Odd behaviour with Part Design Boolean/Part Fusion operations https://forum.freecadweb.org/viewtopic. ... 46#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
- Veteran
- Posts: 7896
- Joined: Fri Aug 29, 2014 12:45 am
- Location: used to be Saint-Petersburg, Russia
Re: #619 Made TreeView stable
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.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,