Sketcher performance - where do those CPU cycles go.

About the development of the Part Design module/workbench. PLEASE DO NOT POST HELP REQUESTS HERE!
Forum rules
Be nice to others! Respect the FreeCAD code of conduct!
acolomitchi
Posts: 34
Joined: Tue Dec 06, 2022 1:41 am
Location: Melbourne, Australia
Contact:

Re: Sketcher performance - where do those CPU cycles go.

Post by acolomitchi »

user1234 wrote: Sun Jan 01, 2023 6:28 pm On the other CAD, with relative precision, i worked before, all elements under the tolerances vanishes.
Ugh... they may leave some gaps into a poly-curve that is supposed to be continuous/closed => topological damage.
Actually, it may happen even with a CAD based on the absolute precision if the precision is lower than what the geometry kernel considers as "is same".
acolomitchi
Posts: 34
Joined: Tue Dec 06, 2022 1:41 am
Location: Melbourne, Australia
Contact:

Re: Sketcher performance - where do those CPU cycles go.

Post by acolomitchi »

Experimentation and some preliminary results ( @DeepSOIC @abdullah ) on scaling up the angle constraints to size constraints

So far:
  • "modernized" a bit of the code (using hypot instead of sqrt(x^2, y^2), introducing lerp - based on std::fma - instead on linCombi, ...)
  • filled-in what I saw as some gaps in the DeriVector2 - added crossProd, rotateCCW_D, rotate CW_D and some other minor thingies
  • converted most of the non-trivial constraints to the use of DeriVector2 maths (I used the errorgrad(double* err, double* grad, double* param) pattern). Still have a few (e.g. I converted PointOnEllipseand some others but not yet PointOnHyperbola, I'll need to sweep again for others). I guess they worked fine before and they would not have needed the DeriVector2 arithmetic, but the amount of lines of code dropped and the readability jumped)
No hard promise, but I'll likely round all up next weekend and send a pull request for you to review and maybe merge.

================

Now, about those angle constraints, I used the DeriVector2 arithmetic to transform ConstraintL2LAngle and ConstraintP2PAngle from radians to size/dimensions errors - the constraints for which one has info about the element of size without residing on hacks.
The good news is that my modification work - my additions to the DeriVector2 arithmetic are correctly coded.
Performance-wise, the results are... underwhelming, at least as perceived from using the UI. The "UI dragging" on the...
  • line elements involved in constraints - unchanged
  • points that define those line - slightly choppier/jumpier
This seems to suggest that whatever potential improvements of "radians->size" one the solver convergence rate the "bring everything on a uniform OoM scale" are negated by extra convergence steps required to get everything under the 1Å tolerance.

(My apologies in advance if I'm stating the obvious in what's following, I'm still getting my head adjusted to the specifics of the geometric constraints solving)

If the "express everything in dimension units" is to be still pursued, for squeezing some extra performance, one will need to use the approach of
  1. scale down everything at some reasonable dimensions. Use power-of-two scaling factors, so that the scaling will have an effect only on the exponent of the IEEE754 and lets their mantissa unaffected (not that the sqrt(sum(square_distances)) cares much about linear FP errors, but anyway why make matters worse?)
  2. solve
  3. restore the initial scale
One needs to note that the above is actually equivalent to using a relative tolerance. Because if I'm asking 1e-10 tolerance but I'm scaling everything down before using a 1e-3 factor, after going through the steps above one will get a solution that's good within a 1e-7 tolerance.
It may still worth pursuing for sketches > 100m sizes and/or if one is willing to sacrifice some precision to the altar of performance gods.
User avatar
DeepSOIC
Veteran
Posts: 7896
Joined: Fri Aug 29, 2014 12:45 am
Location: used to be Saint-Petersburg, Russia

Re: Sketcher performance - where do those CPU cycles go.

Post by DeepSOIC »

acolomitchi wrote: Tue Jan 03, 2023 12:42 am I used the DeriVector2 arithmetic to transform ConstraintL2LAngle and ConstraintP2PAngle from radians to size/dimensions errors
I haven't seen how you actually did that, but i have worries. If the error is just angles, the solver sees that only rotationg the lines will help to reduce the error, which is good. Now, if you somehow include the lengths of these lines into the error function, the solver will see that reducing the length of the lines is also a perfectly valid way of reducing the error, which may make it tempting for the solver to converge to a degenerate solution where the length of a line is zero. I think it's bad.
acolomitchi
Posts: 34
Joined: Tue Dec 06, 2022 1:41 am
Location: Melbourne, Australia
Contact:

Re: Sketcher performance - where do those CPU cycles go.

Post by acolomitchi »

DeepSOIC wrote: Tue Jan 03, 2023 12:33 pm
acolomitchi wrote: Tue Jan 03, 2023 12:42 am I used the DeriVector2 arithmetic to transform ConstraintL2LAngle and ConstraintP2PAngle from radians to size/dimensions errors
Now, if you somehow include the lengths of these lines into the error function, the solver will see that reducing the length of the lines is also a perfectly valid way of reducing the error, which may make it tempting for the solver to converge to a degenerate solution where the length of a line is zero. I think it's bad.
I did include the lengths and their derivatives, the solver didn't succumb to temptation in my tests - nothing out of the ordinary, even if I went to test angles made by using the axes and extremely acute angles (1.5° was the lowest that I tested with)
Could you suggest a test case with increased seduction power, please?
DeepSOIC wrote: Tue Jan 03, 2023 12:33 pm I haven't seen how you actually did that,...
Easy fix, head to https://github.com/acolomitchi/FreeCAD/ ... len-fruits , I just pushed it for your convenience.

In particular, the helper functions for L2LAngle and P2PAngle constraints is angleErrorGrad (Constraints.cpp:57) using avgLineExtentScaling (Constraints.cpp:38) as the scale for the (normalized with derivatives) directions of the two lines.
Mark Szlazak
Posts: 439
Joined: Tue Apr 04, 2017 6:06 pm
Location: SF Bay Area, California

Re: Sketcher performance - where do those CPU cycles go.

Post by Mark Szlazak »

Any progress on this?
User avatar
andrecaldas
Posts: 300
Joined: Fri Jan 27, 2023 8:45 pm
Contact:

Re: Sketcher performance - where do those CPU cycles go.

Post by andrecaldas »

Here is a newbe talking about things he do not understand, again...

As I understand, the Sketcher evolved in such a way that SketchObject contains a Sketch.

The SketchObject holds the user given information: constraints, geometries and external geometries. Then, when it wants to solve, it passes the information to Sketch. In its turn, Sketch builds up the data structure needed by the solver.

It seems to me that everytime you sneeze, SketchObject calls Sketch::setUpSketch just as if a brand new Sketch was created. No information is reused. Sketch resets everything and builds up everything again.

I think there is no need to call GCS::initSolution if you didn't even change any constraints.

If I am not totally wrong (again), and not missing anything (again!), then the problem looks like:

Code: Select all

for (int i = 0; i < 1000000; ++i)
{
  do_stuff(); // Do stuff that do not change the result of the heavy operation below.
  very_havy_operation_that_could_be_outside_the_loop();
}
Besides that, further optimization would be to have something like GCS::updateInitSolution. A method that would take into account only changes in a specific constraint.
User avatar
andrecaldas
Posts: 300
Joined: Fri Jan 27, 2023 8:45 pm
Contact:

Re: Sketcher performance - where do those CPU cycles go.

Post by andrecaldas »

Also, notice that GCS::initSolution explicitly checks hasDiagnosis before calling the slow diagnosis().

But Sketch::setUpSketcher() clears hasDiagnosis everytime (Sketch::clear() --- GCS::System::clear() --- hasDiagnosis = false).
acolomitchi
Posts: 34
Joined: Tue Dec 06, 2022 1:41 am
Location: Melbourne, Australia
Contact:

Re: Sketcher performance - where do those CPU cycles go.

Post by acolomitchi »

acolomitchi wrote: Tue Jan 03, 2023 12:42 am Experimentation and some preliminary results ( @DeepSOIC @abdullah ) on scaling up the angle constraints to size constraints

...

No hard promise, but I'll likely round all up next weekend and send a pull request for you to review and maybe merge.
Apologies, fate hasn't been kind enough to allow me keeping the no-hard-promise I made half a year ago.
Ups and downs as one would expect in life, but my most serious down found me in emergency and asking myself what I intent to do with the shorter-than-one-thought time of life that one may be granted ahead. And I'm afraid tackling the FC Sketcher's solver is losing in the priority competition, at least for now.

Bits of info and thoughts that I had in mind for playing in the solver's playground, offered to whom may care:

- A review on geometric constraint solving - interesting bits around "constraint state diagnosis may go astray close the err minimum" and consideration/approaches involving the topology of constraints. Of course, being a review, is choke full of citations.

- would have plugged in an automatic differentiation package and fooled around with the Hessian a bit - it's likely sparse enough anyhow. In any case, the "most of the error are distances except for the angles, but we're treating them all the same" and "we're computing the distances by sqrt/hypot, but then doing the hypot again when computing the Jacobian" are two things that tasted unnaturally bitter to me.
Post Reply