View Issue Details

IDProjectCategoryView StatusLast Update
0028569Open CASCADEOCCT:Foundation Classespublic2021-09-20 10:48
Reporteragv Assigned Toagv  
PrioritynormalSeveritytweak 
Status assignedResolutionopen 
Product Version7.0.0 
Target Version7.7.0 
Summary0028569: Improve the performance of 2d classifier (CSLib_Class2d)
DescriptionCurrent implementation of this algorithm uses plain iteration through a given array of points therefore the complexity is O(n). The performance will be significatly improved if we store sqrt(n) bounding boxes each containing sqrt(n) points; the expected complexity becomes O(sqrt(n)).
Steps To ReproduceN/A
TagsNo tags attached.
Test case number

Activities

msv

2017-03-17 19:11

developer   ~0064415

Please provide your solution.

git

2017-07-27 16:35

administrator   ~0068801

Branch CR28569 has been created by agv.

SHA-1: 2924e11c37bfb0587d864cb744f841a36db6aa42


Detailed log of new commits:

Author: agv
Date: Thu Jul 27 16:34:17 2017 +0300

    0028569: Improve the performance of 2d classifier (CSLib_Class2d)
    
    changes: CSLib_Class2d (header and source file)

msv

2017-07-27 16:57

developer   ~0068804

Jenkins job is created
http://jenkins-test-10.nnov.opencascade.com:8080/view/CR28569-master-MSV/

msv

2017-07-27 17:16

developer   ~0068805

Remarks:

- Please put information about the matter of the patch into commit message (something like in the description of this bug).

src/CSLib/CSLib_Class2d.cxx
- After the line 70 add comments with short description of the approach.

msv

2017-07-27 17:24

developer   ~0068806

Dear Alexander, the following compilation error is found under VC10:
src\CSLib\CSLib_Class2d.cxx(72) : error C3861: 'log2': identifier not found

git

2017-07-27 20:32

administrator   ~0068823

Branch CR28569 has been updated by agv.

SHA-1: 6356dc649016697dee25a086967a69440422a04a


Detailed log of new commits:

Author: agv
Date: Thu Jul 27 20:32:31 2017 +0300

    0028569: Improve the performance of 2d classifier (CSLib_Class2d)
    
    Previous implementation of this algorithm used plain iteration through a given array of points therefore the complexity was O(n). The performance is significatly improved by storing sqrt(n) bounding boxes each containing sqrt(n) points; the expected complexity is now O(sqrt(n)).

msv

2017-07-28 09:49

developer   ~0068824

No more remarks to the code, let's wait for test results.

git

2017-07-30 14:51

administrator   ~0068869

Branch CR28569 has been updated forcibly by inv.

SHA-1: a16fd3862a689913c076cc82a969318d7619fde5

msv

2017-07-31 12:08

developer   ~0068887

Last edited: 2017-07-31 12:08

Dear Alexander,
There are regressions, both on tests behaviors and on performance.
OCCT:
http://occt-tests/CR28569-master-MSV-OCCT/Windows-64-VC10/diff_summary.html
Products:
http://occt-tests/CR28569-master-MSV-Products/Windows-64-VC10/diff_summary.html

Issue History

Date Modified Username Field Change
2017-03-17 17:30 agv New Issue
2017-03-17 17:30 agv Assigned To => abv
2017-03-17 17:31 agv Assigned To abv => msv
2017-03-17 19:11 msv Note Added: 0064415
2017-03-17 19:11 msv Assigned To msv => agv
2017-03-17 19:11 msv Status new => assigned
2017-03-17 19:11 msv Product Version => 7.0.0
2017-03-17 19:12 msv Severity minor => tweak
2017-07-20 12:10 msv Target Version 7.2.0 => 7.3.0
2017-07-27 16:35 git Note Added: 0068801
2017-07-27 16:39 agv Assigned To agv => msv
2017-07-27 16:39 agv Status assigned => resolved
2017-07-27 16:39 agv Steps to Reproduce Updated
2017-07-27 16:57 msv Note Added: 0068804
2017-07-27 17:16 msv Note Added: 0068805
2017-07-27 17:16 msv Assigned To msv => agv
2017-07-27 17:16 msv Status resolved => assigned
2017-07-27 17:24 msv Note Added: 0068806
2017-07-27 20:32 git Note Added: 0068823
2017-07-27 20:33 agv Assigned To agv => msv
2017-07-28 09:49 msv Note Added: 0068824
2017-07-28 09:49 msv Assigned To msv => abv
2017-07-28 09:49 msv Status assigned => resolved
2017-07-28 09:49 msv Assigned To abv => msv
2017-07-30 14:51 git Note Added: 0068869
2017-07-31 12:08 msv Note Added: 0068887
2017-07-31 12:08 msv Assigned To msv => agv
2017-07-31 12:08 msv Status resolved => assigned
2017-07-31 12:08 msv Note Edited: 0068887
2018-02-25 21:09 abv Target Version 7.3.0 => 7.4.0
2019-07-10 22:29 abv Target Version 7.4.0 => 7.5.0
2020-09-11 16:13 utverdov Target Version 7.5.0 => 7.6.0
2021-09-20 10:48 kgv Target Version 7.6.0 => 7.7.0