MantisBT - Open CASCADE
View Issue Details
0029302Open CASCADE[OCCT] OCCT:Foundation Classespublic2017-11-08 15:222018-06-29 21:19
kgv 
bugmaster 
normalintegration request 
closedfixed 
 
[OCCT] 7.3.0[OCCT] 7.3.0 
Not required
0029302: Foundation Classes, NCollection - optimize iteration of indexed maps
NCollection_IndexedMap is used regularly as replacement of NCollection_Map which allows iterating Keys preserving the same order, as they has been added to the map.

The main idea of NCollection_IndexedMap is providing a fast lookup of Keys already defined in the map (the job of NCollection_Map) and storing the order of these Keys (e.g. some plain array of Keys) - so basically it should work like a combination of two kinds of collections within single interface.

Unfortunately, current implementation is more complicated than it can be expected. Instead of using array for accessing Keys by Index, NCollection_IndexedMap behaves like NCollection_DoubleMap<TheKeyType,int> with limited flexibility (continuous indexation) and modified iteration behavior.

The main pitfall of current implementation is a noticeable overhead for accessing Keys by Index numbers - basically, it requires computation of HashCode and iteration through indices having the same Hash code. Since iterator is implemented as accessing Keys by incremented Index number, the iteration of this collection also implies additional overhead comparing to iteration of NCollection_Map.

For some algorithms (computing bounding box, for example), preserving the order while iterating all items within NCollection_IndexedMap is not required, considering that ordered access is still required for other operations with the same collection. In this case, providing an unordered Iterator can be a useful feature to avoid wasting CPU resources without real need.

Alternative improvement would be redesigning NCollection_IndexedMap so that it will stop pretending being Double Map specialization, and will allocate array of nodes for indexed access independently from number of buckets.
No tags attached.
related to 0029304closed bugmaster Draw Harness, DBRep_DrawableShape - fix inappropriate use of unordered map 
Issue History
2017-11-08 15:22kgvNew Issue
2017-11-08 15:22kgvAssigned To => abv
2017-11-08 15:26gitNote Added: 0072052
2017-11-08 17:39kgvSummaryFoundation Classes, NCollection_IndexedMap - optimize unordered iteration => Foundation Classes, NCollection - optimize iteration of indexed maps
2017-11-08 17:48gitNote Added: 0072057
2017-11-08 18:14gitNote Added: 0072063
2017-11-08 21:28gitNote Added: 0072094
2017-11-08 21:40kgvNote Added: 0072095
2017-11-08 21:40kgvStatusnew => resolved
2017-11-09 00:13gitNote Added: 0072096
2017-11-09 06:59gitNote Added: 0072097
2017-11-09 10:17kgvRelationship addedrelated to 0029304
2017-11-09 10:35kgvNote Added: 0072102
2017-11-09 12:38abvNote Added: 0072110
2017-11-09 12:38abvAssigned Toabv => bugmaster
2017-11-09 12:38abvStatusresolved => reviewed
2017-11-09 12:46bugmasterTest case number => Not required
2017-11-09 12:53bugmasterNote Added: 0072111
2017-11-09 12:53bugmasterStatusreviewed => tested
2017-11-09 12:54bugmasterNote Edited: 0072111bug_revision_view_page.php?bugnote_id=72111#r18104
2017-11-10 10:02msvNote Added: 0072135
2017-11-10 10:13bugmasterChangeset attached => occt master 510cb852
2017-11-10 10:13bugmasterStatustested => verified
2017-11-10 10:13bugmasterResolutionopen => fixed
2017-11-10 12:15gitNote Added: 0072161
2017-11-10 12:15gitNote Added: 0072162
2018-02-17 23:59abvTarget Version7.4.0* => 7.3.0
2018-06-29 21:15aivFixed in Version => 7.3.0
2018-06-29 21:19aivStatusverified => closed

Notes
(0072052)
git   
2017-11-08 15:26   
Branch CR29302 has been created by kgv.

SHA-1: 26cfa263782931625e7cf5f337a7989860919b50


Detailed log of new commits:

Author: kgv
Date: Wed Nov 8 15:25:51 2017 +0300

    0029302: Foundation Classes, NCollection_IndexedMap - optimize unordered iteration
    
    NCollection_IndexedMap now accesses Key by Index number without computing Hash code.

Author: kgv
Date: Thu Nov 2 15:36:20 2017 +0300

    0029290: Visualization, TKOpenGl - allow defining Light source per ZLayer
    
    Graphic3d_CLight is now defined as a class inheriting Standard_Transient,
    so that it's fields now should be accessed through methods.
    Graphic3d_CLight::IsEnabled() - new property allowing to disable light source everywhere.
    Confusing aliases OpenGl_Light and Graphic3d_ListOfCLight.Graphic3d_ListOfCLight have been removed.
    
    Graphic3d_ZLayerSettings::Lights() - light sources list is now property of ZLayer.
    When defined, it overrides light sources defined for View/Viewer.
    
    Graphic3d_ListOfCLight is now passed by Handle.

Author: kgv
Date: Thu Nov 2 16:29:17 2017 +0300

    0029292: Coding Rules - remove Graphic3d_Vector duplicating gp_XYZ
    
    Graphic3d_Vector has been replaced by gp_Pnt/gp_XYZ/gp_Dir depending on context.
(0072057)
git   
2017-11-08 17:48   
Branch CR29302 has been updated forcibly by kgv.

SHA-1: 3810e244efe4ecf051296f293909501bd740f40d
(0072063)
git   
2017-11-08 18:14   
Branch CR29302 has been updated forcibly by kgv.

SHA-1: 87421db9cd65b17a0f71a4e18caa8e2b39fbdb19
(0072094)
git   
2017-11-08 21:28   
Branch CR29302 has been updated forcibly by kgv.

SHA-1: 66bfa24fee489a5e6ee6009612e59543f176547f
(0072095)
kgv   
2017-11-08 21:40   
Patch is ready for review.
(0072096)
git   
2017-11-09 00:13   
Branch CR29302 has been updated forcibly by kgv.

SHA-1: 491d5a2e311c5f2d870729ed8bc0b3bac9686971
(0072097)
git   
2017-11-09 06:59   
Branch CR29302_1 has been created by kgv.

SHA-1: 91fc948ac06d4231f8831fddbf9003198a6ee023


Detailed log of new commits:

Author: kgv
Date: Wed Nov 8 15:25:51 2017 +0300

    0029302: Foundation Classes, NCollection - optimize iteration of indexed maps
    
    NCollection_IndexedMap and NCollection_IndexedDataMap
    now access Key by Index number without computing Hash code.
    IndexedMapNode::myNext2 and IndexedDataMapNode::myNext2 fields
    have been removed, so that indexed map now may utilize less memory.
    
    TCollection::NextPrimeForMap() has been extended upto 2038431745
    (almost full signed 32-bit integer range),
    and NCollection_BaseMap::mySaturated property has been removed.
    
    NCollection_IndexedDataMap::RemoveFromIndex(), FindKey(), FindFromIndex(),
    ChangeFromIndex() - removed duplicating checks for out of range input.
(0072102)
kgv   
2017-11-09 10:35   
Test results:

http://jenkins-test-10.nnov.opencascade.com/view/CR29302_1-master-KGV [^]
(0072110)
abv   
2017-11-09 12:38   
No remarks, please integrate
(0072111)
bugmaster   
2017-11-09 12:53   
(edited on: 2017-11-09 12:54)
Combination -
OCCT branch : CR29302_1 SHA-1: 91fc948ac06d4231f8831fddbf9003198a6ee023
Products branch : master
was compiled on Linux, MacOS and Windows platforms and tested on optimize mode.

Number of compiler warnings:
No new/fixed warnings

Regressions/Differences/Improvements:
No regressions/differences

CPU differences:
Linux:
OCCT
Total CPU difference: 20646.64000000041 / 20729.730000000465 [-0.40%]
Products
Total CPU difference: 7914.580000000072 / 7934.790000000087 [-0.25%]
Windows:
OCCT
Total CPU difference: 18565.35140789848 / 18506.86663299847 [+0.32%]
Products
Total CPU difference: 8024.7850405999425 / 7981.338762099939 [+0.54%]

Image differences :
No differences that require special attention

Memory differences :
No differences that require special attention

(0072135)
msv   
2017-11-10 10:02   
My small remark:
If you made the argument theNbBuckets in the method NCollection_BaseMap::EndResize obsolete, why didn't you removed it from the signature at all? It would make the code where EndResize is used more understandable.
(0072161)
git   
2017-11-10 12:15   
Branch CR29302 has been deleted by kgv.

SHA-1: 491d5a2e311c5f2d870729ed8bc0b3bac9686971
(0072162)
git   
2017-11-10 12:15   
Branch CR29302_1 has been deleted by kgv.

SHA-1: 91fc948ac06d4231f8831fddbf9003198a6ee023