MantisBT
Mantis Bug Tracker Workflow

View Issue Details Jump to Notes ] Related Changesets ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0026184Open CASCADE[OCCT] OCCT:Modeling Algorithmspublic2015-05-05 14:302016-04-20 15:48
Reportermsv 
Assigned Tobugmaster 
PrioritynormalSeveritymajor 
StatusclosedResolutionfixed 
PlatformOSOS Version
Product Version[OCCT] 6.9.0 
Target Version[OCCT] 7.0.0Fixed in Version[OCCT] 7.0.0 
Summary0026184: GeomAPI_ExtremaCurveCurve hangs on parallel b-spline curves
DescriptionGeomAPI_ExtremaCurveCurve hangs on specified cases. In both cases the curves represent b-spline curves going along parallel direct lines.
Actually, it is not an infinite loop, but too large computation complexity. The Finder gives ~ 856025 number of solutions. It leads to internal several cycles 856000 * 856000 ==> it seems too much huge.
Steps To Reproduce# Case 1
restore Curve_Extrema_1_12971.brep a1
restore Curve_Extrema_2_12971.brep a2
mkcurve c1 a1
mkcurve c2 a2
cpulimit 20
dchrono h reset; dchrono h start
extrema c1 c2
dchrono h stop; dchrono h show
cpulimit
regexp {CPU user time: (\d*)} [dchrono h show] dummy sec
if {$sec > 10} {
  error "Error: too long computation time $sec seconds"
}

# Case 2
restore Curve_Extrema_1_13767.brep a1
restore Curve_Extrema_2_13767.brep a2
mkcurve c1 a1
mkcurve c2 a2
cpulimit 20
dchrono h reset; dchrono h start
extrema c1 c2
dchrono h stop; dchrono h show
cpulimit
regexp {CPU user time: (\d*)} [dchrono h show] dummy sec
if {$sec > 10} {
  error "Error: too long computation time $sec seconds"
}
TagsNo tags attached.
Test case numberbugs fclasses bug26184_1, bug26184_2
Attached Files7z file icon data.7z (15,061 bytes) 2015-05-05 14:30

- Relationships
duplicate of 0026075closedbugmaster Make Extrema_GenExtCC return IsParallel flag in case of parallel curves 
parent of 0026395closedbugmaster Merge clasees NCollection_CellFilter_NDim and NCollection_CellFilter 
parent of 0026593closedbugmaster Coding rules - revert compatibility of NCollection_CellFilter constructor with old code 
related to 0026269assignedaml Extrema package revision 

-  Notes
(0042015)
aml (developer)
2015-06-08 12:12
edited on: 2015-06-08 12:12

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?

(0042030)
msv (developer)
2015-06-08 16:26

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.
(0042233)
git (administrator)
2015-06-18 16:31

Branch CR26184 has been created by aml.

SHA-1: d35867eeb2eb606087026e3c6e194aec6d600342


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.
(0042234)
aml (developer)
2015-06-18 16:32

Dear msv,

Please check current state of branch CR26184. On my workstation Case 1 work 5.5 seconds instead of 20+ seconds.
(0042263)
msv (developer)
2015-06-19 12:42

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.
(0042352)
git (administrator)
2015-06-23 14:19

Branch CR26184 has been updated forcibly by aml.

SHA-1: 35657ca475fa2ef801029dec48d632d99980e4c5
(0042353)
aml (developer)
2015-06-23 14:20

Dear msv,

Please check updated branch CR26184.
(0042404)
msv (developer)
2015-06-24 11:21

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();

(0042406)
git (administrator)
2015-06-24 11:49

Branch CR26184 has been updated forcibly by aml.

SHA-1: 409db09a2bbcd473514beec3ab3b4bc8dfd8c88c
(0042407)
aml (developer)
2015-06-24 11:52

Dear msv,

Remark fixed. Please check.
(0042409)
msv (developer)
2015-06-24 12:17

Reviewed.
(0042449)
mkv (tester)
2015-06-25 15:26

Dear BugMaster,
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.
SHA-1: 25c4fd694f748915ede0235b7dd0d696464e1cbf

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.
(0042450)
git (administrator)
2015-06-25 15:27

Branch CR26184 has been updated by mkv.

SHA-1: 831d391e7c73af5e1ebe81f47de1570b31c14f46


Detailed log of new commits:

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

    Test cases for issue CR26184

(0042451)
mkv (tester)
2015-06-25 15:27

Dear aml,
could you please review following test cases
bugs fclasses bug26184_1, bug26184_2
(0042471)
git (administrator)
2015-06-26 08:26

Branch CR26184 has been updated forcibly by aml.

SHA-1: 459145b709fce8982bc994f3b36323566f3f1184
(0042487)
msv (developer)
2015-06-26 12:06

Dear bugmaster,

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.
(0042488)
aml (developer)
2015-06-26 12:26

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.
(0042509)
git (administrator)
2015-06-26 18:17

Branch CR26184 has been updated forcibly by mkv.

SHA-1: a1482fbe0fa4484e10e135c52249e4c7ce30719f
(0042545)
mkv (tester)
2015-06-29 14:01

Dear BugMaster,
Branch CR26184 was rebased on current master of occt git-repository.
SHA-1: a1482fbe0fa4484e10e135c52249e4c7ce30719f
(0042548)
git (administrator)
2015-06-29 14:37

Branch CR26184 has been updated by mkv.

SHA-1: 047003511069c9b5989cebbbce1364216ab642db


Detailed log of new commits:

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

    Small correction of test cases for issue CR26184

(0042549)
mkv (tester)
2015-06-29 14:38

Dear BugMaster,
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.
SHA-1: a1482fbe0fa4484e10e135c52249e4c7ce30719f

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.
(0044214)
git (administrator)
2015-08-14 10:57

Branch CR26184 has been deleted by inv.

SHA-1: 047003511069c9b5989cebbbce1364216ab642db

- Related Changesets
occt: master 4b65fc77
Timestamp: 2015-07-02 10:52:41
Author: aml
Committer: bugmaster
Details ] Diff ]
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.

Test cases for issue CR26184

Small correction of test cases for issue CR26184
mod - src/math/math_GlobOptMin.cxx Diff ] File ]
mod - src/math/math_GlobOptMin.hxx Diff ] File ]
mod - src/NCollection/FILES Diff ] File ]
add - src/NCollection/NCollection_CellFilterNDim.hxx Diff ] File ]
mod - src/QABugs/QABugs_19.cxx Diff ] File ]
add - tests/bugs/fclasses/bug26184_1 Diff ] File ]
add - tests/bugs/fclasses/bug26184_2 Diff ] File ]
mod - tests/bugs/mesh/bug25378_1_1 Diff ] File ]
mod - tests/bugs/moddata_2/bug567 Diff ] File ]

- Issue History
Date Modified Username Field Change
2015-05-05 14:30 msv New Issue
2015-05-05 14:30 msv Assigned To => msv
2015-05-05 14:30 msv File Added: data.7z
2015-05-05 14:31 msv Relationship added duplicate of 0026075
2015-05-20 15:51 msv Assigned To msv => aml
2015-05-20 15:55 msv Status new => assigned
2015-05-26 13:54 aml Relationship added related to 0026269
2015-06-08 12:12 aml Note Added: 0042015
2015-06-08 12:12 aml Assigned To aml => msv
2015-06-08 12:12 aml Status assigned => feedback
2015-06-08 12:12 aml Note Edited: 0042015 View Revisions
2015-06-08 16:26 msv Note Added: 0042030
2015-06-08 16:26 msv Assigned To msv => aml
2015-06-08 16:26 msv Status feedback => assigned
2015-06-18 16:31 git Note Added: 0042233
2015-06-18 16:32 aml Note Added: 0042234
2015-06-18 16:32 aml Assigned To aml => msv
2015-06-18 16:32 aml Status assigned => resolved
2015-06-19 12:42 msv Note Added: 0042263
2015-06-19 12:42 msv Assigned To msv => aml
2015-06-19 12:42 msv Status resolved => assigned
2015-06-23 14:19 git Note Added: 0042352
2015-06-23 14:20 aml Note Added: 0042353
2015-06-23 14:20 aml Assigned To aml => msv
2015-06-23 14:20 aml Status assigned => resolved
2015-06-24 11:21 msv Note Added: 0042404
2015-06-24 11:21 msv Assigned To msv => aml
2015-06-24 11:21 msv Status resolved => assigned
2015-06-24 11:49 git Note Added: 0042406
2015-06-24 11:52 aml Note Added: 0042407
2015-06-24 11:52 aml Assigned To aml => msv
2015-06-24 11:52 aml Status assigned => resolved
2015-06-24 12:17 msv Note Added: 0042409
2015-06-24 12:17 msv Assigned To msv => bugmaster
2015-06-24 12:17 msv Status resolved => reviewed
2015-06-24 16:54 mkv Assigned To bugmaster => mkv
2015-06-25 15:26 mkv Note Added: 0042449
2015-06-25 15:26 mkv Assigned To mkv => aml
2015-06-25 15:26 mkv Status reviewed => assigned
2015-06-25 15:27 git Note Added: 0042450
2015-06-25 15:27 mkv Note Added: 0042451
2015-06-25 15:27 mkv Test case number => bugs fclasses bug26184_1, bug26184_2
2015-06-26 08:26 git Note Added: 0042471
2015-06-26 12:06 msv Note Added: 0042487
2015-06-26 12:26 aml Note Added: 0042488
2015-06-26 12:26 aml Assigned To aml => mkv
2015-06-26 12:26 aml Status assigned => feedback
2015-06-26 18:17 git Note Added: 0042509
2015-06-29 14:01 mkv Note Added: 0042545
2015-06-29 14:37 git Note Added: 0042548
2015-06-29 14:38 mkv Note Added: 0042549
2015-06-29 14:38 mkv Assigned To mkv => bugmaster
2015-06-29 14:38 mkv Status feedback => tested
2015-07-03 15:27 bugmaster Changeset attached => occt master 4b65fc77
2015-07-03 15:27 bugmaster Status tested => verified
2015-07-03 15:27 bugmaster Resolution open => fixed
2015-07-03 15:31 bugmaster Target Version 7.1.0 => 7.0.0
2015-07-07 09:27 kgv Relationship added parent of 0026395
2015-08-14 10:57 git Note Added: 0044214
2015-08-24 15:06 kgv Relationship added parent of 0026593
2016-04-20 15:44 aiv Fixed in Version => 7.0.0
2016-04-20 15:48 aiv Status verified => closed


Copyright © 2000 - 2021 MantisBT Team
Powered by Mantis Bugtracker