From 797d11c6f5f14c60023706f105d11e32e233685f Mon Sep 17 00:00:00 2001 From: aml Date: Thu, 17 Jul 2014 13:50:51 +0400 Subject: [PATCH] 0025058: Regression of performance of BRepExtrema_ExtCC (1000 times slower) Added initial values approximation to improve performance. Local optimization start coefficient fixed. Test case for issue CR25058 --- src/math/math_GlobOptMin.cxx | 105 +++++++++++++++++++++++--------- src/math/math_GlobOptMin.hxx | 9 ++- tests/bugs/modalg_5/bug23706_11 | 2 +- tests/bugs/modalg_5/bug25058 | 45 ++++++++++++++ 4 files changed, 129 insertions(+), 32 deletions(-) create mode 100755 tests/bugs/modalg_5/bug25058 diff --git a/src/math/math_GlobOptMin.cxx b/src/math/math_GlobOptMin.cxx index 2810077db3..2ad9b165e6 100644 --- a/src/math/math_GlobOptMin.cxx +++ b/src/math/math_GlobOptMin.cxx @@ -175,6 +175,9 @@ void math_GlobOptMin::Perform() { Standard_Integer i; + // Compute initial values for myF, myY, myC. + computeInitialValues(); + // Compute parameters range Standard_Real minLength = RealLast(); Standard_Real maxLength = RealFirst(); @@ -187,36 +190,12 @@ void math_GlobOptMin::Perform() maxLength = currentLength; } - myE1 = minLength * myTol / myC; - myE2 = maxLength * myTol * 2.0 / myC; - myE3 = - maxLength * myTol / 4.0; - - // Compute start point. - math_Vector aPnt(1,myN); - for(i = 1; i <= myN; i++) - { - Standard_Real currCentral = (myA(i) + myB(i)) / 2.0; - aPnt(i) = currCentral; - } - - myFunc->Value(aPnt, myF); - - math_Vector aExtremumPoint(1,myN); - Standard_Real aExtremumValue = RealLast(); - if (computeLocalExtremum(aPnt, aExtremumValue, aExtremumPoint)) - { - // Local Extremum finds better solution than midpoint. - if (aExtremumValue < myF) - { - myF = aExtremumValue; - aPnt = aExtremumPoint; - } - } - - myY.Clear(); - for(i = 1; i <= myN; i++) - myY.Append(aPnt(i)); - mySolCount++; + myE1 = minLength * myTol; + myE2 = maxLength * myTol; + if (myC > 1.0) + myE3 = - maxLength * myTol / 4.0; + else + myE3 = - maxLength * myTol * myC / 4.0; computeGlobalExtremum(myN); @@ -285,6 +264,72 @@ Standard_Boolean math_GlobOptMin::computeLocalExtremum(const math_Vector& thePnt return Standard_False; } +//======================================================================= +//function : computeInitialValues +//purpose : +//======================================================================= +void math_GlobOptMin::computeInitialValues() +{ + Standard_Integer i; + math_Vector aCurrPnt(1, myN); + math_Vector aBestPnt(1, myN); + + Standard_Real aCurrVal = RealLast(); + Standard_Real aBestVal = RealLast(); + + // Check functional value in midpoint, low and upp point border and + // in each point try to perform local optimization. + aBestPnt = (myA + myB) * 0.5; + myFunc->Value(aBestPnt, aBestVal); + + for(i = 1; i <= 3; i++) + { + aCurrPnt = myA + (myB - myA) * (i - 1) / 2.0; + + if(computeLocalExtremum(aCurrPnt, aCurrVal, aCurrPnt)) + { + // Local Extremum finds better solution than current point. + if (aCurrVal < aBestVal) + { + aBestVal = aCurrVal; + aBestPnt = aCurrPnt; + } + } + } + + myF = aBestVal; + myY.Clear(); + for(i = 1; i <= myN; i++) + myY.Append(aBestPnt(i)); + mySolCount++; + + // Lipschitz const approximation + Standard_Real aLipConst = 0.0, aPrevVal; + Standard_Integer aPntNb = 13; + myFunc->Value(myA, aPrevVal); + Standard_Real aStep = (myB - myA).Norm() / aPntNb; + for(i = 1; i <= aPntNb; i++) + { + aCurrPnt = myA + (myB - myA) * i / (aPntNb - 1); + myFunc->Value(aCurrPnt, aCurrVal); + + if(Abs(aCurrVal - aPrevVal) / aStep > aLipConst) + aLipConst = Abs(aCurrVal - aPrevVal) / aStep; + + aPrevVal = aCurrVal; + } + aLipConst *= Sqrt(myN); + + if (aLipConst < myC * 0.1) + { + myC = Max(aLipConst * 0.1, 0.01); + } + else if (aLipConst > myC * 10) + { + myC = Min(myC * 2, 30.0); + } +} + //======================================================================= //function : ComputeGlobalExtremum //purpose : diff --git a/src/math/math_GlobOptMin.hxx b/src/math/math_GlobOptMin.hxx index 6c4f8593a4..ac5a4db9e9 100644 --- a/src/math/math_GlobOptMin.hxx +++ b/src/math/math_GlobOptMin.hxx @@ -58,7 +58,7 @@ public: //! Get best functional value. Standard_EXPORT Standard_Real GetF(); - //! Return count of global extremas. NbExtrema <= MAX_SOLUTIONS. + //! Return count of global extremas. Standard_EXPORT Standard_Integer NbExtrema(); //! Return solution i, 1 <= i <= NbExtrema. @@ -74,6 +74,13 @@ private: void computeGlobalExtremum(Standard_Integer theIndex); + //! Computes starting value / approximation: + // myF - initial best value. + // myY - initial best point. + // myC - approximation of Lipschitz constant. + // to imporve convergence speed. + void computeInitialValues(); + //! Check that myA <= pnt <= myB Standard_Boolean isInside(const math_Vector& thePnt); diff --git a/tests/bugs/modalg_5/bug23706_11 b/tests/bugs/modalg_5/bug23706_11 index 207023b2a8..b1afdfe5a0 100755 --- a/tests/bugs/modalg_5/bug23706_11 +++ b/tests/bugs/modalg_5/bug23706_11 @@ -10,7 +10,7 @@ bsplinecurve r1 2 5 1 3 2 1 3 1 4 1 5 3 2 5 3 1 3 7 3 1 4 8 3 1 4 8 3 1 5 9 3 1 bsplinecurve r2 2 5 2 3 2.5 1 3 1 3.5 1 4 3 -1 2 3 1 1 11 3 1 3 9 3 1 3 9 3 1 3 9 3 1 5 7 3 1 7 4 3 1 set info [extrema r1 r2] -if { [llength $info] != 3 } { +if { [llength $info] != 1 } { puts "Error : Extrema is wrong" } else { puts "OK: Extrema is valid" diff --git a/tests/bugs/modalg_5/bug25058 b/tests/bugs/modalg_5/bug25058 new file mode 100755 index 0000000000..cea1cd9adf --- /dev/null +++ b/tests/bugs/modalg_5/bug25058 @@ -0,0 +1,45 @@ +puts "============" +puts "OCC25058" +puts "============" +puts "" +############################### +## Regression of performance of BRepExtrema_ExtCC (1000 times slower) +############################### + +if { [regexp {Debug mode} [dversion]] } { + if { [regexp {Windows} [dversion]] } { + set max_time 1 + set max_time2 1 + } else { + set max_time 1 + set max_time2 1 + } +} else { + if { [regexp {Windows} [dversion]] } { + set max_time 1 + set max_time2 1 + } else { + set max_time 1 + set max_time2 1 + } +} + +restore [locate_data_file bug25058_e1.brep] e1 +restore [locate_data_file bug25058_e2.brep] e2 + +dchrono h reset +dchrono h start + +distmini r e1 e2 + +dchrono h stop +set q [dchrono h show] + +regexp {CPU user time: ([-0-9.+eE]+) seconds} $q full z +puts "$z" + +if { $z > ${max_time} } { + puts "Elapsed time of distmini is more than ${max_time} seconds - Faulty" +} else { + puts "Elapsed time of distmini is less than ${max_time} seconds - OK" +} -- 2.20.1