GeomAPI_ExtremaCurveCurve hangs on parallel b-spline curves

Dear msv,

All possible improvements, from my point of view, were integrated in scope of #0026075 bug. Now it works very slow, but not hangs (~ 22 seconds on my workstation). Is this result acceptable, or additional investigations are needed?

Fix for #0026075 helped a lot, it prevented O(n^3) computations on upper levels of extrema calculation. However, now the test Case 1 takes about 20 sec instead of 7 sec for OCCT 6.7.0.
Now it is needed to eliminate O(n^2) computation on the level of math_GlobOptMin.

Branch [archived branch] has been created by Participant.

[revision removed]


Detailed log of new commits:

Author: aml
Date: Thu Jun 18 09:02:24 2015 +0300

    0026184: GeomAPI_ExtremaCurveCurve hangs on parallel b-spline curves
    
    Class CellFilterNDim added.
    Class CellFulterNDim used in GlobOptMin to improve performance in case of many solutions.
    Memory leak eliminated.

Dear msv,

Please check current state of branch CR26184. On my workstation Case 1 work 5.5 seconds instead of 20+ seconds.

Remarks:

src\math\math_GlobOptMin.hxx
- In line 82, myCurrent is assigned a result of subtraction with another object. It means that first time the method Inspect will work correct, but other calls it will check not the intended distance.

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

[revision removed]

Dear msv,

Please check updated branch CR26184.

The lines 82-89:

    math_Vector aDiff(1, Dimension);
    aDiff = myCurrent - theObject;

    Standard_Real aSqDist = 0.0;
    for(Standard_Integer anIdx = 1; anIdx <= Dimension; anIdx++)
    {
      aSqDist += aDiff(anIdx) * aDiff(anIdx);
    }

can be written more shorter:

    Standard_Real aSqDist = (myCurrent - theObject).Norm2();

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

[revision removed]

Dear msv,

Remark fixed. Please check.

Reviewed.

Dear Commenter 1,
Branch CR26184 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: 28 (25 on master)
Windows: 0 (0 on master)

products component :
Linux: 37 (37 on master)
Windows: 0 (0 on master)

There are new additional compilation warnings on Linux platform:
http://jenkins-test-01.nnov.opencascade.com:8080/user/mnt/my-views/view/A_mnt_warnings/portlet/dashboard_portlet_17008/job/CR26184-master_build_occt_linux/1/warnings17Result/package.-671474530/file.1763641746/

NCollection_CellFilterNDim.hxx:195, GNU C Compiler 4 (gcc), Priority: Normal
when initialized here [-Wreorder]

NCollection_CellFilterNDim.hxx:259, GNU C Compiler 4 (gcc), Priority: Normal
'NCollection_Array1 NCollection_CellFilterNDim::Cell::index' [-Wreorder]

NCollection_CellFilterNDim.hxx:260, GNU C Compiler 4 (gcc), Priority: Normal
'NCollection_CellFilterNDim::Cell::Objects' will be initialized after [-Wreorder]

Regressions/Differences/Improvements:
No regressions/differences

Testing cases:
http://occt-tests/CR26184-master-occt-64/Debian70-64/bugs/fclasses/bug26184_1.html
http://occt-tests/CR26184-master-occt-64/Windows-64-VC10/bugs/fclasses/bug26184_1.html
bugs fclasses bug26184_1: OK

http://occt-tests/CR26184-master-occt-64/Debian70-64/bugs/fclasses/bug26184_2.html
http://occt-tests/CR26184-master-occt-64/Windows-64-VC10/bugs/fclasses/bug26184_2.html
bugs fclasses bug26184_2: OK

Testing on Linux:
occt component :
Total MEMORY difference: 98097451 / 98442814 [-0.35%]
Total CPU difference: 18436.180000000124 / 18602.25000000014 [-0.89%]
products component :
Total MEMORY difference: 24214681 / 24316064 [-0.42%]
Total CPU difference: 8261.950000000012 / 7858.430000000035 [+5.13%]

Testing on Windows:
occt component :
http://occt-tests/CR26184-master-occt-64/Windows-64-VC10/diff-Windows-64-VC10.html
CPU perf bop boxholes: 46.3946974 / 28.3609818 [+63.59%]
CPU mesh advanced_shading B5: 100.8390464 / 56.9247649 [+77.14%]
CPU mesh advanced_incmesh_parallel B5: 42.9314752 / 24.6793582 [+73.96%]
CPU mesh advanced_mesh B5: 43.9298816 / 25.2565619 [+73.93%]
CPU mesh advanced_incmesh A3: 4.6332297 / 2.9328188 [+57.98%]
CPU mesh advanced_incmesh B5: 47.112302 / 26.1457676 [+80.19%]
CPU bugs moddata_1 bug22759: 610.275912 / 281.7846063 [+116.58%]
CPU bugs moddata_1: 768.2893248999981 / 419.2214872999983 [+83.27%]
CPU bugs modalg_1 bug1665: 2.340015 / 1.4664094 [+59.57%]
CPU bugs mesh bug25378_2_2: 3.8688248 / 2.2308143 [+73.43%]
CPU bugs mesh bug25469_3: 1.404009 / 0.2808018 [+400.00%]

Total MEMORY difference: 56668055 / 56783760 [-0.20%]
Total CPU difference: 18962.514353798568 / 17621.202155698844 [+7.61%]

products component :
Total MEMORY difference: 15546076 / 15550884 [-0.03%]
Total CPU difference: 6918.160746899995 / 6414.932721099968 [+7.84%]

There are no differences in images found by testdiff.

Branch [archived branch] has been updated by Participant.

[revision removed]


Detailed log of new commits:

Author: mkv
Date: Thu Jun 25 15:24:29 2015 +0300

    Test cases for issue CR26184

Dear aml,
could you please review following test cases
bugs fclasses bug26184_1, bug26184_2

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

[revision removed]

Dear Commenter 1,

I have built OCCT master and CR26184 on my PC in x64 Release config and run the problematic tests several times. I have noted no difference in CPU time between these two branches (within some tolerance).

So, if the measurements sometimes differ it means the tests or the whole testing procedure are not stable.

Dear mkv,

I
Performance regressions:
I have checked problem cases and got same results as msv on my workstation.

II
Test case 26184_1 and 26184_2 insignificantly changed and pushed into 26184 branch. Added printout in OK state.

II
Compilation warnings are fixed.
Please check compilation warnings on updated 26184 branch.
Full testing not needed.

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

[revision removed]

Dear Commenter 1,
Branch CR26184 was rebased on current master of occt git-repository.
[revision removed]

Branch [archived branch] has been updated by Participant.

[revision removed]


Detailed log of new commits:

Author: mkv
Date: Mon Jun 29 14:36:55 2015 +0300

    Small correction of test cases for issue CR26184

Dear Commenter 1,
Branch CR26184 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: 25 (25 on master)
Windows: 0 (0 on master)

products component :
Linux: 37 (37 on master)
Windows: 0 (0 on master)

Regressions/Differences/Improvements:
No regressions/differences

Testing cases:
http://occt-tests/CR26184-master-occt-64/Debian70-64/bugs/fclasses/bug26184_1.html
http://occt-tests/CR26184-master-occt-64/Windows-64-VC10/bugs/fclasses/bug26184_1.html
bugs fclasses bug26184_1: OK

http://occt-tests/CR26184-master-occt-64/Debian70-64/bugs/fclasses/bug26184_2.html
http://occt-tests/CR26184-master-occt-64/Windows-64-VC10/bugs/fclasses/bug26184_2.html
bugs fclasses bug26184_2: OK

Testing on Linux:
occt component :
Total MEMORY difference: 97732843 / 98578636 [-0.86%]
Total CPU difference: 18287.54000000029 / 18377.700000000114 [-0.49%]
products component :
Total MEMORY difference: 24229180 / 24220652 [+0.04%]
Total CPU difference: 8118.320000000004 / 7858.560000000034 [+3.31%]

Testing on Windows:
occt component :
Total MEMORY difference: 56577685 / 56608178 [-0.05%]
Total CPU difference: 17452.939477099408 / 17353.520039798845 [+0.57%]
products component :
Total MEMORY difference: 15546126 / 15550857 [-0.03%]
Total CPU difference: 6315.497683699977 / 6303.984809899965 [+0.18%]

There are no differences in images found by testdiff.

Branch [archived branch] has been deleted by Participant.

[revision removed]