View Issue Details

Related ChangesetsJump to NotesJump to History
IDProjectCategoryView StatusDate SubmittedLast Update
0026184Open CASCADEOCCT:Modeling Algorithmspublic2015-05-05 14:302016-04-20 15:48
ReportermsvAssigned Tobugmaster  
PrioritynormalSeveritymajor 
Status closedResolutionfixed 
Product Version6.9.0 
Target Version7.0.0Fixed in Version7.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 Files

  • data.7z (15,061 bytes)

Relationships

duplicate of 0026075 closedbugmaster Make Extrema_GenExtCC return IsParallel flag in case of parallel curves 
parent of 0026395 closedbugmaster Merge clasees NCollection_CellFilter_NDim and NCollection_CellFilter 
parent of 0026593 closedbugmaster Coding rules - revert compatibility of NCollection_CellFilter constructor with old code 
related to 0026269 closedbugmaster Modeling Data - Analytical extrema does not take into account trimmed input data 

Activities

msv

2015-05-05 14:30

developer  

data.7z (15,061 bytes)

aml

2015-06-08 12:12

developer   ~0042015

Last edited: 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?

msv

2015-06-08 16:26

developer   ~0042030

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.

git

2015-06-18 16:31

administrator   ~0042233

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.

aml

2015-06-18 16:32

developer   ~0042234

Dear msv,

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

msv

2015-06-19 12:42

developer   ~0042263

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.

git

2015-06-23 14:19

administrator   ~0042352

Branch CR26184 has been updated forcibly by aml.

SHA-1: 35657ca475fa2ef801029dec48d632d99980e4c5

aml

2015-06-23 14:20

developer   ~0042353

Dear msv,

Please check updated branch CR26184.

msv

2015-06-24 11:21

developer   ~0042404

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

git

2015-06-24 11:49

administrator   ~0042406

Branch CR26184 has been updated forcibly by aml.

SHA-1: 409db09a2bbcd473514beec3ab3b4bc8dfd8c88c

aml

2015-06-24 11:52

developer   ~0042407

Dear msv,

Remark fixed. Please check.

msv

2015-06-24 12:17

developer   ~0042409

Reviewed.

mkv

2015-06-25 15:26

tester   ~0042449

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.

git

2015-06-25 15:27

administrator   ~0042450

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

mkv

2015-06-25 15:27

tester   ~0042451

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

git

2015-06-26 08:26

administrator   ~0042471

Branch CR26184 has been updated forcibly by aml.

SHA-1: 459145b709fce8982bc994f3b36323566f3f1184

msv

2015-06-26 12:06

developer   ~0042487

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.

aml

2015-06-26 12:26

developer   ~0042488

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.

git

2015-06-26 18:17

administrator   ~0042509

Branch CR26184 has been updated forcibly by mkv.

SHA-1: a1482fbe0fa4484e10e135c52249e4c7ce30719f

mkv

2015-06-29 14:01

tester   ~0042545

Dear BugMaster,
Branch CR26184 was rebased on current master of occt git-repository.
SHA-1: a1482fbe0fa4484e10e135c52249e4c7ce30719f

git

2015-06-29 14:37

administrator   ~0042548

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

mkv

2015-06-29 14:38

tester   ~0042549

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.

git

2015-08-14 10:57

administrator   ~0044214

Branch CR26184 has been deleted by inv.

SHA-1: 047003511069c9b5989cebbbce1364216ab642db

Related Changesets

occt: master 4b65fc77

2015-07-02 10:52:41

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		 Affected Issues
0026184
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
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