MantisBT - Open CASCADE
View Issue Details
0032539Open CASCADE[OCCT] OCCT:Modeling Algorithmspublic2021-08-17 17:322021-09-27 13:32
asuraven 
msv 
normalminor 
resolvedopen 
 
[OCCT] 7.6.0* 
perf\modalg\bug32539_1 perf\modalg\bug32539_2
0032539: Modeling Algorithms - Parallelize BRepExtrema_DistShapeShape algorithm
Parallelize the algorithm to increase performance.
Add -parallel option to distmini DRAW command
not required
No tags attached.
related to 0031942verified bugmaster Modeling Algorithms - add possibility to abort the BRepExtrema_DistShapeShape algorithm 
related to 0032552verified smoskvin Modeling Algorithms - BRepExtrema_DistShapeShape algorithm consumes too much memory 
xlsx CR32549 compare_1.xlsx (11,225) 2021-08-30 17:35
https://tracker.dev.opencascade.org/
7z bug32539_1.7z (163,659) 2021-09-20 17:33
https://tracker.dev.opencascade.org/
Issue History
2021-08-17 17:32asuravenNew Issue
2021-08-17 17:32asuravenAssigned To => asuraven
2021-08-17 17:33asuravenRelationship addedrelated to 0031942
2021-08-18 18:33szyTarget VersionUnscheduled => 7.6.0*
2021-08-18 18:33szyStatusnew => assigned
2021-08-19 13:40asuravenNote Added: 0103302
2021-08-23 11:33szyNote Edited: 0103302bug_revision_view_page.php?bugnote_id=103302#r25645
2021-08-23 18:48asuravenNote Added: 0103346
2021-08-25 10:59asuravenNote Added: 0103429
2021-08-25 18:59asuravenNote Added: 0103437
2021-08-26 19:50asuravenNote Added: 0103442
2021-08-27 18:37gitNote Added: 0103457
2021-08-27 19:37asuravenNote Added: 0103458
2021-08-30 13:14gitNote Added: 0103534
2021-08-30 13:59gitNote Added: 0103535
2021-08-30 14:07gitNote Added: 0103536
2021-08-30 14:25asuravenFile Added: CR32549 compare_1.xlsx
2021-08-30 14:29asuravenNote Added: 0103537
2021-08-30 14:29asuravenAssigned Toasuraven => msv
2021-08-30 14:29asuravenStatusassigned => feedback
2021-08-30 15:12kgvNote Added: 0103539
2021-08-30 15:12kgvNote Edited: 0103539bug_revision_view_page.php?bugnote_id=103539#r25649
2021-08-30 16:07gitNote Added: 0103550
2021-08-30 16:07gitNote Added: 0103551
2021-08-30 17:34asuravenNote Added: 0103552
2021-08-30 17:35asuravenFile Deleted: CR32549 compare_1.xlsx
2021-08-30 17:35asuravenFile Added: CR32549 compare_1.xlsx
2021-08-30 22:48kgvNote Added: 0103565
2021-08-30 22:50kgvNote Added: 0103566
2021-09-01 17:49msvNote Added: 0103642
2021-09-01 18:20msvAssigned Tomsv => asuraven
2021-09-01 18:20msvStatusfeedback => assigned
2021-09-01 18:35asuravenNote Added: 0103645
2021-09-01 18:35asuravenRelationship addedrelated to 0032552
2021-09-03 20:25asuravenNote Added: 0103740
2021-09-06 18:57asuravenNote Added: 0103876
2021-09-07 19:11asuravenNote Added: 0103903
2021-09-08 20:16asuravenNote Added: 0103931
2021-09-09 13:06gitNote Added: 0103935
2021-09-10 15:07gitNote Added: 0103986
2021-09-10 19:20asuravenNote Added: 0103991
2021-09-13 18:02asuravenNote Added: 0104066
2021-09-14 19:34asuravenNote Added: 0104080
2021-09-20 17:30gitNote Added: 0104238
2021-09-20 17:32asuravenTest case number => perf\modalg\bug32539_1 perf\modalg\bug32539_2
2021-09-20 17:33asuravenFile Added: bug32539_1.7z
2021-09-21 13:44gitNote Added: 0104257
2021-09-21 15:08asuravenNote Added: 0104260
2021-09-21 16:46gitNote Added: 0104271
2021-09-21 18:33gitNote Added: 0104275
2021-09-22 11:39gitNote Added: 0104287
2021-09-22 15:31asuravenNote Added: 0104290
2021-09-22 15:31asuravenAssigned Toasuraven => kgv
2021-09-22 15:31asuravenStatusassigned => resolved
2021-09-22 15:31asuravenSteps to Reproduce Updatedbug_revision_view_page.php?rev_id=25769#r25769
2021-09-23 11:14kgvNote Added: 0104308
2021-09-23 13:49kgvNote Added: 0104310
2021-09-23 14:01gitNote Added: 0104311
2021-09-23 14:02asuravenNote Added: 0104312
2021-09-24 17:54kgvAssigned Tokgv => msv
2021-09-27 11:42gitNote Added: 0104391
2021-09-27 13:32asuravenNote Added: 0104397

Notes
(0103302)
asuraven   
2021-08-19 13:40   
(edited on: 2021-08-23 11:33)


(0103346)
asuraven   
2021-08-23 18:48   
(0103429)
asuraven   
2021-08-25 10:59   
(0103437)
asuraven   
2021-08-25 18:59   
(0103442)
asuraven   
2021-08-26 19:50   
(0103457)
git   
2021-08-27 18:37   
Branch CR32539 has been created by asuraven.

SHA-1: 8d42d728fdd923b068aba806df915407cd7aaf24


Detailed log of new commits:

Author: asuraven
Date: Fri Aug 27 18:34:31 2021 +0300

    0032539: Parallelize distance pair

Author: asuraven
Date: Fri Aug 27 13:06:02 2021 +0300

    0032539: using std::vector

Author: asuraven
Date: Thu Aug 26 18:41:05 2021 +0300

    0032539: Optimize vertex dist

Author: asuraven
Date: Wed Aug 25 21:19:00 2021 +0300

    0032539: Parallelize distance

Author: asuraven
Date: Wed Aug 25 12:23:13 2021 +0300

    0032539: Optimize vert/vert dist + throw to break

Author: asuraven
Date: Wed Aug 18 20:23:07 2021 +0300

    0032539: Modeling Algorithms - Parallelize BRepExtrema_DistShapeShape algorithm
(0103458)
asuraven   
2021-08-27 19:37   
(0103534)
git   
2021-08-30 13:14   
Branch CR32539 has been updated forcibly by asuraven.

SHA-1: 4382336060e3a7aa4b3f09aa942749c82f21b623
(0103535)
git   
2021-08-30 13:59   
Branch CR32539 has been updated forcibly by asuraven.

SHA-1: df96ada625c120cba4c348225402d565da933572
(0103536)
git   
2021-08-30 14:07   
Branch CR32539_1 has been created by asuraven.

SHA-1: ab714c353af012d5fa0bc1635ef5384676630447


Detailed log of new commits:

Author: asuraven
Date: Wed Aug 18 20:23:07 2021 +0300

    0032539: Modeling Algorithms - Parallelize BRepExtrema_DistShapeShape algorithm
(0103537)
asuraven   
2021-08-30 14:29   
Michael, could you please make your remarks for current issue's code
(0103539)
kgv   
2021-08-30 15:12   
> RAM using, MB
> BRepExtrema_DistShapeShape::Perform() time, s
These metrics are confusing without description of testing methodology.
Please clarify which counter has been collected for "RAM using" - "meminfo heap", "meminfo wset", or something else?

Why there is such a huge memory consumption difference compared to master (2.9 GB -> 152 MB)?

> master/single
Normally, comparison chart should show a change from old (current) to new (patch), while your table shows the opposite.

(0103550)
git   
2021-08-30 16:07   
Branch CR32539 has been updated forcibly by asuraven.

SHA-1: f3f1887f5a605226bd0536534754a01a4d3f56e1
(0103551)
git   
2021-08-30 16:07   
Branch CR32539_1 has been updated forcibly by asuraven.

SHA-1: ec63dc41ad2538e12a5a8e1977ae69db2f48470e
(0103552)
asuraven   
2021-08-30 17:34   
> Why there is such a huge memory consumption difference compared to master (2.9 GB -> 152 MB)?
This difference is so big because the new function DistanceVertVert() is being used instead DistanceMapMap(). The DistanceVertVert() function does not create a map of distances between points of a very large (n^2) size
(0103565)
kgv   
2021-08-30 22:48   
-                                             const Message_ProgressRange& theRange = Message_ProgressRange());

+                                             const Message_ProgressRange& theRange = Message_ProgressRange(),

+                                             const Standard_Boolean theIsMultiThread = Standard_False);


I doubt that it is worth overloading class constructor further - user would better using an empty constructor and Perform() method.

-  Standard_EXPORT Standard_Boolean Perform(const Message_ProgressRange& theRange = Message_ProgressRange());

+  Standard_EXPORT Standard_Boolean Perform(const Message_ProgressRange& theRange = Message_ProgressRange(),

+                                           const Standard_Boolean theIsMultiThread = Standard_False);


It is unusual passing multithreaded parameter to Perform() method and making any arguments after Progress Indicator.
I guess that storing multithreading flag as class argument defined by a dedicated setter would be better.

+    myMutex.reset(new Standard_HMutex());
...
+    myMutex = NULL;

myMutex is a normal Handle object - .Nullify() and normal assignment is a preferred syntax for Handles.

+  VertexTask(Standard_Integer theFirtsIndex,
+             Standard_Integer theLastIndex,
+             std::vector<BRepExtrema_SolutionElem>* theSolutionsShape1,
+             std::vector<BRepExtrema_SolutionElem>* theSolutionsShape2,
+             const TopTools_IndexedMapOfShape* theMap1,
+             const TopTools_IndexedMapOfShape* theMap2,
+             const std::vector<Bnd_Box>* theLBox1,
+             const std::vector<Bnd_Box>* theLBox2,
+             const Message_ProgressRange theRange,
+             Standard_Boolean* theIsBreak,
+             Standard_Real* theDistRef,
+             Standard_Real theEps,
+             Handle(Standard_HMutex) theMutex)

This constructor is completely unreadable - please define individual properties setters instead.

+
+  Standard_Integer myFirtsIndex;
+  Standard_Integer myLastIndex;
+  std::vector<BRepExtrema_SolutionElem>* mySolutionsShape1;

Public structure fields are normally named without "my" prefix and starts with upper case.

+        Standard_Atomic_CompareAndSwap((int*) *theTask.myIsBreak, Standard_False, Standard_True);

You shouldn't reinterpret cast a "bool" type (1 byte) to "int" (4 bytes).
Practically speaking there is no much benefit in using Standard_Atomic_CompareAndSwap here at all for a trivial assignment, as returned value is never used.
Assignments to bool and 32-bit types are always written/read atomically on all modern CPU architectures even without explicit atomic operations.
Moreover your then accesses to variable without any atomic operations.
This would work as expected just by declaring a variable "volatile" just to avoid compiler overoptimization in a loop,
which is still a valid use case for a volatile keyword in C++20 (apart from it's deprecation in C++ for some other cases).

+          else if (fabs(aDistTool.DistValue() - myDistRef) < myEps)
...
+        if (aDist < myDistRef - myEps || fabs (aDist - myDistRef) < myEps)

Abs()

+  if (myMutex.IsNull())
+  {
+  Message_ProgressRange aBoxRange(aTwinScope.Next());
+    Message_ProgressScope aBoxScope(aBoxRange, NULL, aCount1);

Broken indentation.

+    OSD_Parallel::ForEach(aTaskArray.begin(), aTaskArray.end(), DistancePairFunctor(), Standard_False);


Why using ForEach() instead of preferred For() for an array collection?

+      const gp_Pnt& aPnt = BRep_Tool::Pnt(aVertex);

Unexpected reference to returned temporary variable.

+    SolidTreatmentMulty(theShape, theVertexMap, theRange);

Multi?

+        if ((*it).Dist() > myDistRef + myEps)

it->Dist()

+  if (n >= 5 && strncmp(a[4], "-", 1))

Please avoid implicit cast of integer to bool.

+  Standard_Boolean anIsMultiThread = Standard_False;

isMultiThread

-  BRepExtrema_SeqOfSolution SeqSolShape1;
-  BRepExtrema_SeqOfSolution SeqSolShape2;
+  std::vector<BRepExtrema_SolutionElem> SeqSolShape1;
+  std::vector<BRepExtrema_SolutionElem> SeqSolShape2;

Why this change is necessary in this patch?
I haven't found any indexed access to these collections within multi-threaded code.
Iteration loop within TRI_SOLUTION could be trivially replaced by BRepExtrema_SeqOfSolution::Iterator.
(0103566)
kgv   
2021-08-30 22:50   
> This difference is so big because the new function DistanceVertVert() is being used instead DistanceMapMap().
> The DistanceVertVert() function does not create a map of distances between points of a very large (n^2) size
This change looks localized, so it would be worthwhile extracting it to a separate bug.
(0103642)
msv   
2021-09-01 17:49   
src/BRepCheck/BRepCheck_Analyzer.cxx
The changes are not relevant.

src/BRepTest/BRepTest_ExtremaCommands.cxx
  if (n >= 5 && strncmp(a[4], "-", 1))

Use a[4][0] != '-' instead of strncmp

  for (Standard_Integer anAI = 4; anAI < n; anAI++)

If deflection parameter is given then anAI must start from 5.

    for (Standard_Integer i1 = 0; i1 < dst.NbSolution(); i1++)

You must not change the index of the first solution.

src/BRepExtrema/BRepExtrema_DistShapeShape.cxx

Do not change sequence to vector. It is better to use NCollection_IncAllocator to initialize sequence in order to facilitate its destruction.

The flag myIsBreak is not needed. You may always get it from any progress scope.

  if (theIsMultiThread && myMutex.IsNull())
  {
    myMutex.reset(new Standard_HMutex());
  }
  else
  {
    myMutex = NULL;
  }

The logic is incorrect: if theIsMultiThread is true and myMutex is not null myMutex will be nullified.
(0103645)
asuraven   
2021-09-01 18:35   
(0103740)
asuraven   
2021-09-03 20:25   
(0103876)
asuraven   
2021-09-06 18:57   
(0103903)
asuraven   
2021-09-07 19:11   
(0103931)
asuraven   
2021-09-08 20:16   
(0103935)
git   
2021-09-09 13:06   
Branch CR32539_3 has been created by asuraven.

SHA-1: 15b0446033f94179a66a1ee80f1f96e92c6351f9


Detailed log of new commits:

Author: asuraven
Date: Wed Sep 8 18:34:28 2021 +0300

    0032539: ForEach -> For: DistancePair

Author: asuraven
Date: Wed Sep 8 18:41:11 2021 +0300

    0032539: Debug log

Author: asuraven
Date: Wed Sep 8 17:18:11 2021 +0300

    0032539: ForEach -> For: stage 1

Author: asuraven
Date: Tue Sep 7 14:20:30 2021 +0300

    0032539: change DistanceTask order

Author: asuraven
Date: Fri Sep 3 20:29:32 2021 +0300

    0032539: fix remarks 1

Author: asuraven
Date: Wed Aug 18 20:23:07 2021 +0300

    0032539: Modeling Algorithms - Parallelize BRepExtrema_DistShapeShape algorithm
(0103986)
git   
2021-09-10 15:07   
Branch CR32539_3 has been updated forcibly by asuraven.

SHA-1: b91ea2b8477f949136f6cbeadca4e3758f71e15b
(0103991)
asuraven   
2021-09-10 19:20   
(0104066)
asuraven   
2021-09-13 18:02   
(0104080)
asuraven   
2021-09-14 19:34   
(0104238)
git   
2021-09-20 17:30   
Branch CR32539_5 has been created by asuraven.

SHA-1: 7cebe097771dae0d93186d5457d80f99e6d8467e


Detailed log of new commits:

Author: asuraven
Date: Wed Aug 18 20:23:07 2021 +0300

    0032539: Modeling Algorithms - Parallelize BRepExtrema_DistShapeShape algorithm
(0104257)
git   
2021-09-21 13:44   
Branch CR32539_5 has been updated forcibly by asuraven.

SHA-1: 8465baf152af477b1c6488d43716e3e9e91e01c9
(0104260)
asuraven   
2021-09-21 15:08   
(0104271)
git   
2021-09-21 16:46   
Branch CR32539_5 has been updated forcibly by asuraven.

SHA-1: 015a5e33d454fff30e1ba80386c89c891c5ad203
(0104275)
git   
2021-09-21 18:33   
Branch CR32539_5 has been updated forcibly by asuraven.

SHA-1: 92309d7f94712383c962f29ce2c836c4f18a2f8c
(0104287)
git   
2021-09-22 11:39   
Branch CR32539_5 has been updated forcibly by asuraven.

SHA-1: 7b8ec84d792c7a9759d9a742aaf9b4abc46bb3ff
(0104290)
asuraven   
2021-09-22 15:31   
Kirill, please review the branch CR32539_5
Tests results are here:
http://jenkins-test-occt/view/CR32539_5-master-ASURAVEN/view/COMPARE/ [^]
(0104308)
kgv   
2021-09-23 11:14   
   }
+  //! If isMultiThread == Standard_True then computation will be performed in parallel.
+  void SetMultiThread(Standard_Boolean theIsMultiThread)
+  {
+    myIsMultiThread = theIsMultiThread;
+  }

While adding a setter, please add getter as well with documented default value.
Methods should be separated by an empty line.

+  const Message_ProgressRange& myRange;

Such class fields will generate compiler warnings due to inability to generate assign operator.
Please either use "const Message_ProgressRange*" or ensure to explicitly remove assign operator / copy constructor marked with Standard_DELETE attribute.
Why this myRange is necessary at all? It is a misconception storing it as a class field, and it seems to be unsued anyway.

+  //! isMultiThread - computation will be performed in parallel if Standard_True
   Standard_EXPORT Standard_Boolean Perform(const Message_ProgressRange& theRange = Message_ProgressRange());


Method doesn't have such argument.

+  //! Parameters F and A are not used in computation and are obsolete. 
   Standard_EXPORT BRepExtrema_DistShapeShape(const TopoDS_Shape& Shape1,

Please use Doxygen tags @param to document arguments and make sure that all arguments are documented.

-      BoxCalculation (myMapV1, myBV1);
-      BoxCalculation (myMapE1, myBE1);
-      BoxCalculation (myMapF1, myBF1);
+      BoxCalculation(myMapV1, myBV1);
+      BoxCalculation(myMapE1, myBE1);
+      BoxCalculation(myMapF1, myBF1);

Unrelated and unexpected change.

 }
 
+
+
 //=======================================================================

Please don't add more than a single empty line between blocks.

+    for (Standard_Integer i = 0; i < ArrayOfArrays->Value(theIndex).Size(); i++)
+    {
+      if (!aScope.More())
+      {
+        break;
+      }
...
+      if (*IsDone)
+      {
+        break;
+      }

`return` will be clear in this context than `break`.
(0104310)
kgv   
2021-09-23 13:49   
(0104311)
git   
2021-09-23 14:01   
Branch CR32539_5 has been updated forcibly by asuraven.

SHA-1: c38874189330112189e5dc4efb62698d5ca27f76
(0104312)
asuraven   
2021-09-23 14:02   
Remarks fixed
(0104391)
git   
2021-09-27 11:42   
Branch CR32539_5 has been updated forcibly by asuraven.

SHA-1: cd349df9d8033a84c4c713ee30bc650a0508ddcd
(0104397)
asuraven   
2021-09-27 13:32   
new tests results: http://jenkins-test-occt/view/CR32539_5-master-ASURAVEN/view/COMPARE/ [^]