Improve performance of the IntPolyh_MaillageAffinage algorithm

Branch [archived branch] has been created by Author.

[revision removed]


Detailed log of new commits:

Author: Author
Date: Fri Apr 7 07:43:44 2017 +0300

    0028639: Improve performance of the IntPolyh_MaillageAffinage algorithm
    
    The following improvements have been made:
    1. Linking edges to triangles while creating the edges.
    2. Replacing the array of couples of intersecting triangles with the list to avoid unnecessary allocations of memory.
    3. Using the algorithm of unbalanced binary tree when looking for pairs of interfering triangles.
    4. Building bounding boxes for the triangles only once and then reusing it.
    5. Making the simple methods of the IntPolyh_Point, IntPolyh_Edge, IntPolyh_Triangle, IntPolyh_Couple classes inline.

Dear Mikhail, could you please review the branch CR28639?

Local testing of that branch has shown the following improvements comparing to the master:

CPU boolean bcut_complex G2: 2.5 / 5.328125 [-53.08%]
CPU boolean bcut_complex N9: 0.671875 / 3.40625 [-80.28%]
CPU boolean bfuse_complex F1: 1.625 / 2.953125 [-44.97%]
CPU boolean bfuse_complex F2: 3.46875 / 6.09375 [-43.08%]
CPU boolean bfuse_complex F8: 1.9375 / 2.90625 [-33.33%]
CPU boolean bopcommon_complex D8: 8 / 16.703125 [-52.10%]
CPU boolean bopcommon_complex D9: 8.03125 / 16.6875 [-51.87%]
CPU boolean bopcommon_complex E5: 0.28125 / 1.546875 [-81.82%]
CPU boolean bopcommon_complex E6: 0.28125 / 1.5 [-81.25%]
CPU boolean bopcut_complex E1: 7.484375 / 16.328125 [-54.16%]
CPU boolean bopcut_complex E2: 7.625 / 16.125 [-52.71%]
CPU boolean bopcut_complex E7: 0.265625 / 1.5625 [-83.00%]
CPU boolean bopcut_complex E8: 0.28125 / 1.5 [-81.25%]
CPU boolean bopcut_complex P8: 5.46875 / 10.109375 [-45.90%]
CPU boolean bopfuse_complex C9: 7.546875 / 16.203125 [-53.42%]
CPU boolean bopfuse_complex D1: 7.71875 / 16.359375 [-52.82%]
CPU boolean bopfuse_complex D6: 0.265625 / 1.5 [-82.29%]
CPU boolean bopfuse_complex D7: 0.3125 / 1.5 [-79.17%]
CPU boolean bopfuse_complex J7: 1.46875 / 3.40625 [-56.88%]
CPU boolean bopfuse_simple ZP6: 2 / 5.015625 [-60.12%]
CPU boolean bsection R9: 1.84375 / 3.5625 [-48.25%]
CPU boolean gdml_private ZG4: 1.34375 / 36.921875 [-96.36%]
CPU boolean gdml_public A9: 4.078125 / 9.171875 [-55.54%]
CPU bugs modalg_1 buc60462_1: 1.875 / 3.59375 [-47.83%]
CPU bugs modalg_1 bug18186: 1.484375 / 2.28125 [-34.93%]
CPU bugs modalg_1 bug19071: 0.515625 / 1.109375 [-53.52%]
CPU bugs modalg_2 bug335: 0.453125 / 1.75 [-74.11%]
CPU bugs modalg_3 bug600: 4.59375 / 112.953125 [-95.93%]
CPU bugs modalg_4 bug697_2: 2.828125 / 4.15625 [-31.95%]
CPU bugs modalg_4 bug697_4: 2.96875 / 4.34375 [-31.65%]
CPU bugs modalg_4 bug697_7: 2.96875 / 4.296875 [-30.91%]
CPU bugs modalg_4 bug697_8: 2.96875 / 4.328125 [-31.41%]
CPU bugs modalg_5 bug25456: 2.6875 / 11.453125 [-76.53%]
CPU bugs modalg_6 bug22609: 1.1875 / 2.078125 [-42.86%]
CPU bugs modalg_6 bug26450: 3.765625 / 6.421875 [-41.36%]
CPU bugs modalg_6 bug26535: 2.1875 / 3 [-27.08%]
CPU bugs modalg_6 bug26621: 29.640625 / 42.59375 [-30.41%]
CPU bugs modalg_6 bug26848: 4.859375 / 113 [-95.70%]
CPU bugs modalg_6 bug26938_1: 4.03125 / 6.09375 [-33.85%]
CPU bugs modalg_6 bug26938_4: 3.3125 / 4.703125 [-29.57%]
CPU bugs modalg_6 bug27615: 29.859375 / 36.640625 [-18.51%]
CPU bugs modalg_6 bug27746_1: 5.890625 / 9.953125 [-40.82%]
CPU bugs moddata_1 bug152_1: 0.4375 / 10.40625 [-95.80%]
CPU bugs moddata_1 bug152_2: 0.453125 / 9.09375 [-95.02%]
CPU bugs moddata_2 bug228: 8.03125 / 16.640625 [-51.74%]
CPU bugs moddata_3 bug599: 4.765625 / 112.515625 [-95.76%]
CPU chamfer dist_angle_complex C1: 1.09375 / 3.03125 [-63.92%]
CPU chamfer dist_angle_sequence C1: 1.625 / 2.734375 [-40.57%]
CPU chamfer dist_dist_complex C1: 0.875 / 2.578125 [-66.06%]
CPU chamfer dist_dist_sequence C1: 1.609375 / 2.8125 [-42.78%]
CPU chamfer equal_dist_complex C1: 1.140625 / 3.0625 [-62.76%]
CPU chamfer equal_dist_sequence C1: 1.3125 / 2.71875 [-51.72%]
CPU perf modalg bug19793_2: 19.546875 / 55.59375 [-64.84%]
CPU prj base C7: 0.359375 / 2.5625 [-85.98%]
CPU prj base C8: 0.9375 / 6.03125 [-84.46%]
CPU prj base D1: 0.46875 / 3.1875 [-85.29%]
CPU prj base D2: 0.609375 / 4.09375 [-85.11%]
CPU prj base D4: 0.171875 / 0.828125 [-79.25%]
CPU prj base D5: 0.21875 / 1.09375 [-80.00%]
CPU prj base D8: 1.125 / 7.703125 [-85.40%]
CPU prj base D9: 0.3125 / 2.203125 [-85.82%]
CPU prj base E2: 0.125 / 0.78125 [-84.00%]
CPU prj base E3: 0.453125 / 2.4375 [-81.41%]
CPU prj base E4: 0.1875 / 1.4375 [-86.96%]
CPU prj base E5: 0.28125 / 1.4375 [-80.43%]
CPU prj base E6: 0.453125 / 2.5625 [-82.32%]
CPU prj base E7: 0.359375 / 2.171875 [-83.45%]
CPU prj base F5: 0.25 / 1.328125 [-81.18%]
CPU prj base F7: 0.25 / 1.25 [-80.00%]
CPU prj base G1: 0.1875 / 0.84375 [-77.78%]
CPU prj base G2: 0.09375 / 0.65625 [-85.71%]
CPU prj base G3: 0.28125 / 1.59375 [-82.35%]
CPU prj base G4: 0.34375 / 1.890625 [-81.82%]
CPU prj base G5: 0.515625 / 2.984375 [-82.72%]
CPU prj base G6: 0.484375 / 3.515625 [-86.22%]
CPU prj base G8: 0.1875 / 1.171875 [-84.00%]
CPU prj base G9: 0.140625 / 0.890625 [-84.21%]
CPU prj base H1: 0.25 / 1.21875 [-79.49%]
CPU prj base H2: 0.34375 / 2.046875 [-83.21%]
CPU prj base H4: 0.40625 / 2.40625 [-83.12%]
CPU prj base H5: 0.96875 / 7.078125 [-86.31%]
CPU prj base H6: 0.625 / 4.953125 [-87.38%]
CPU prj base H7: 0.625 / 4.703125 [-86.71%]
CPU prj base H8: 0.34375 / 2.203125 [-84.40%]
CPU prj base H9: 0.375 / 2.578125 [-85.45%]
CPU prj base I1: 0.359375 / 2.28125 [-84.25%]
CPU prj base I2: 0.3125 / 2.21875 [-85.92%]
CPU prj base I3: 1.421875 / 10.546875 [-86.52%]
CPU prj base I4: 0.46875 / 3.5 [-86.61%]

The list shows only the most noticeable improvements.

Branch [archived branch] has been updated forcibly by Author.

[revision removed]

The Branch [archived branch] has been rebased on current master.

Branch [archived branch] has been updated forcibly by Author.

[revision removed]

Remarks:

src\IntPolyh\FILES
- keep alphabit sorting of list of files.

src\IntPolyh\IntPolyh_Edge.hxx
src\IntPolyh\IntPolyh_Point.hxx
src\IntPolyh\IntPolyh_Couple.hxx
src\IntPolyh\IntPolyh_Triangle.hxx
- As you are changing 90% of the source code rename fields according to coding rules.

src\IntPolyh\IntPolyh_Couple.hxx
- 53: it returns integer, so it is not TRUE.
- 58: "the angle of between", "of" is extra.

src\IntPolyh\IntPolyh_CoupleMapHasher.hxx
- DEFINE_STANDARD_ALLOC is not needed.

src\IntPolyh\IntPolyh_Triangle.hxx
- get rid of "if" statements in GetEdgeNumber, SetEdge, GetEdgeOrientation, SetEdgeOrientation, GetNextTriangle2, LinkEdges2Triangle, SetEdgeAndOrientation by replacing fields p1,p2,p3,e1,e2,e3,oe1,oe2,oe3 with C arrays p[3], e[3], oe[3].
- compact boolean flags using bit fields.

src\IntPolyh\IntPolyh_Triangle.cxx
- The method IntPolyh_Triangle::BoundingBox is to be optimized:
  - use cached isDegenerated flag;
  - avoid enlarge and setting gap on repeated calls.

src\IntPolyh\IntPolyh_MaillageAffinage.cxx
- 178: make it private.
- In the method TriangleCompare now it became useless to check the number of contacts by NbTTC. So, the lines 3200-3202, 3231-3232 are to be removed.

src\IntPolyh\IntPolyh_MaillageAffinage.hxx
- Remove declaration of not implemented method GetArrayOfSP.
- Remove unused field TStartPoints.
- Remove unused class IntPolyh_ArrayOfStartPoints.hxx
- Remove unused methods:
 TriangleComparePSP
 StartPointsCalcul.
 NextStartingPointsResearch
 StartingPointsResearch

Branch [archived branch] has been updated by Author.

[revision removed]


Detailed log of new commits:

Author: Author
Date: Thu Apr 20 11:41:41 2017 +0300

    Correction of the *IntPolyh_Triangle* class.
    
    Upgrade guide has been updated with the removed methods.

Author: Author
Date: Wed Apr 19 16:36:01 2017 +0300

    Correction of the *IntPolyh_Point* class.

Author: Author
Date: Wed Apr 19 16:21:45 2017 +0300

    Correction of the *IntPolyh_Edge* class.

Author: Author
Date: Wed Apr 19 16:00:20 2017 +0300

    Correction of the clas *IntPolyh_Couple*.

Author: Author
Date: Wed Apr 19 14:58:28 2017 +0300

    // Corrections according to remarks;
    
    * The method *IntPolyh_Triangle::SetEdgeandOrientation* has been removed as unused;
    * The following methods of the *IntPolyh_MaillageAffinage* have been removed as unused:
     - *LinkEdges2Triangles*;
     - *TriangleEdgeContact2*;
     - *StartingPointsResearch2*;
     - *NextStartingPointsResearch2*;
     - *TriangleComparePSP*;
     - *StartPointsCalcul*.

Dear Mikhail, please review the updated branch. Do not pay too much attention to commit messages, they will be updated in the final branch with single commit.

Branch [archived branch] has been created by Author.

[revision removed]


Detailed log of new commits:

Author: Author
Date: Fri Apr 7 07:43:44 2017 +0300

    0028639: Improve performance of the IntPolyh_MaillageAffinage algorithm
    
    The following improvements have been made:
    1. Linking edges to triangles while creating the edges.
    2. Replacing the array of couples of intersecting triangles with the list to avoid unnecessary allocations of memory.
    3. Using the algorithm of unbalanced binary tree when looking for pairs of interfering triangles.
    4. Building bounding boxes for the triangles only once and then reusing it.
    5. Making the simple methods of the IntPolyh_Point, IntPolyh_Edge, IntPolyh_Triangle, IntPolyh_Couple classes inline.
    6. The following methods of the *IntPolyh_Triangle* class have been removed as unused:
      - *CheckCommonEdge*
      - *SetEdgeandOrientation*
      - *MultipleMiddleRefinement2*.
    7. The method *IntPolyh_Triangle::TriangleDeflection* has been replaced with the *IntPolyh_Triangle::ComputeDeflection*.
    8. The following methods of the *IntPolyh_MaillageAffinage* class have been removed as unused:
      - *LinkEdges2Triangles*;
      - *TriangleEdgeContact2*;
      - *StartingPointsResearch2*;
      - *NextStartingPointsResearch2*;
      - *TriangleComparePSP*;
      - *StartPointsCalcul*.

Remarks:

src\IntPolyh\IntPolyh_Couple.hxx
src\IntPolyh\IntPolyh_Point.hxx
- Using of bit field is unjustified for only one variable.

src\IntPolyh\IntPolyh_Triangle.cxx
- in the method IntPolyh_Triangle::Dump, pass int argument to printf instead of bool.

Branch [archived branch] has been updated by Author.

[revision removed]


Detailed log of new commits:

Author: Author
Date: Fri Apr 21 12:08:17 2017 +0300

    // Corrections according to remarks.

Done. Please review the git branch CR28639_1.

Reviewed.

Branch [archived branch] has been updated forcibly by Participant.

[revision removed]

Dear Commenter 1,
Branch CR28639_1 from occt git-repository (and master from products git-repository) was compiled on Linux, MacOS and Windows platforms and tested on Release mode.
[revision removed]

Number of compiler warnings:

occt component :
Linux: 0 (0 on master)
Windows: 0 (0 on master)
MacOS : 0 (0 on master)

products component :
Linux: 64 (64 on master)
Windows: 0 (0 on master)
MacOS : 1195

Regressions/Differences/Improvements:
No regressions/differences

Testing cases:
Not needed

Testing on Linux:
occt component :
Total MEMORY difference: 91790382 / 91810384 [-0.02%]
Total CPU difference: 18996.680000000324 / 19561.10000000033 [-2.89%]
products component :
Total MEMORY difference: 31249691 / 31264414 [-0.05%]
Total CPU difference: 5414.379999999983 / 5400.509999999974 [+0.26%]
Testing on Windows:
occt component :
Total MEMORY difference: 58037467 / 58034445 [+0.01%]
Total CPU difference: 17316.891004998637 / 18122.277367698553 [-4.44%]
products component :
Total MEMORY difference: 22650125 / 22611847 [+0.17%]
Total CPU difference: 5318.339291699976 / 5410.192680499973 [-1.70%]

There are no differences in images found by testdiff.

Dear Commenter 1,
Branch CR28639_1 is TESTED.

Branch [archived branch] has been updated by Author.

[revision removed]


Detailed log of new commits:

Author: Author
Date: Fri Apr 28 12:23:04 2017 +0300

    // Elimination of the warning.

Branch [archived branch] has been deleted by Participant.

[revision removed]

Branch [archived branch] has been deleted by Participant.

[revision removed]