#619 Made TreeView stable

[DeepSOIC]

Just having some fun

chicken-egg-tree.png (116.4 KiB) Viewed 1358 times

[DeepSOIC]

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]

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]

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]

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]

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]

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 .

I just gave it compound->explode->compound->... torture again, and with tree potentially expandable to about 4 gigaleaves, I had no noticeable slowdown.

[bernd]

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

[NormandC]

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!

[DeepSOIC]

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.