View Issue Details

Related ChangesetsJump to NotesJump to History
IDProjectCategoryView StatusDate SubmittedLast Update
0029302Open CASCADEOCCT:Foundation Classespublic2017-11-08 15:222018-06-29 21:19
Reporterkgv Assigned Tobugmaster  
PrioritynormalSeverityintegration request 
Status closedResolutionfixed 
Target Version7.3.0Fixed in Version7.3.0 
Summary0029302: Foundation Classes, NCollection - optimize iteration of indexed maps
DescriptionNCollection_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.
TagsNo tags attached.
Test case numberNot required

Relationships

related to 0029304 closedbugmaster Draw Harness, DBRep_DrawableShape - fix inappropriate use of unordered map 

Activities

git

2017-11-08 15:26

administrator   ~0072052

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.

git

2017-11-08 17:48

administrator   ~0072057

Branch CR29302 has been updated forcibly by kgv.

SHA-1: 3810e244efe4ecf051296f293909501bd740f40d

git

2017-11-08 18:14

administrator   ~0072063

Branch CR29302 has been updated forcibly by kgv.

SHA-1: 87421db9cd65b17a0f71a4e18caa8e2b39fbdb19

git

2017-11-08 21:28

administrator   ~0072094

Branch CR29302 has been updated forcibly by kgv.

SHA-1: 66bfa24fee489a5e6ee6009612e59543f176547f

kgv

2017-11-08 21:40

developer   ~0072095

Patch is ready for review.

git

2017-11-09 00:13

administrator   ~0072096

Branch CR29302 has been updated forcibly by kgv.

SHA-1: 491d5a2e311c5f2d870729ed8bc0b3bac9686971

git

2017-11-09 06:59

administrator   ~0072097

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.

kgv

2017-11-09 10:35

developer   ~0072102

Test results:

http://jenkins-test-10.nnov.opencascade.com/view/CR29302_1-master-KGV

abv

2017-11-09 12:38

manager   ~0072110

No remarks, please integrate

bugmaster

2017-11-09 12:53

administrator   ~0072111

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

msv

2017-11-10 10:02

developer   ~0072135

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.

git

2017-11-10 12:15

administrator   ~0072161

Branch CR29302 has been deleted by kgv.

SHA-1: 491d5a2e311c5f2d870729ed8bc0b3bac9686971

git

2017-11-10 12:15

administrator   ~0072162

Branch CR29302_1 has been deleted by kgv.

SHA-1: 91fc948ac06d4231f8831fddbf9003198a6ee023

Related Changesets

occt: master 510cb852

2017-11-08 12:25:51

kgv


Committer: bugmaster Details Diff		 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.		 Affected Issues
0029302
mod - src/NCollection/NCollection_BaseMap.cxx Diff File
mod - src/NCollection/NCollection_BaseMap.hxx Diff File
mod - src/NCollection/NCollection_IndexedDataMap.hxx Diff File
mod - src/NCollection/NCollection_IndexedMap.hxx Diff File
mod - src/TCollection/TCollection.cxx Diff File

Issue History

Date Modified Username Field Change
2017-11-08 15:22 kgv New Issue
2017-11-08 15:22 kgv Assigned To => abv
2017-11-08 15:26 git Note Added: 0072052
2017-11-08 17:39 kgv Summary Foundation Classes, NCollection_IndexedMap - optimize unordered iteration => Foundation Classes, NCollection - optimize iteration of indexed maps
2017-11-08 17:48 git Note Added: 0072057
2017-11-08 18:14 git Note Added: 0072063
2017-11-08 21:28 git Note Added: 0072094
2017-11-08 21:40 kgv Note Added: 0072095
2017-11-08 21:40 kgv Status new => resolved
2017-11-09 00:13 git Note Added: 0072096
2017-11-09 06:59 git Note Added: 0072097
2017-11-09 10:17 kgv Relationship added related to 0029304
2017-11-09 10:35 kgv Note Added: 0072102
2017-11-09 12:38 abv Note Added: 0072110
2017-11-09 12:38 abv Assigned To abv => bugmaster
2017-11-09 12:38 abv Status resolved => reviewed
2017-11-09 12:46 bugmaster Test case number => Not required
2017-11-09 12:53 bugmaster Note Added: 0072111
2017-11-09 12:53 bugmaster Status reviewed => tested
2017-11-09 12:54 bugmaster Note Edited: 0072111
2017-11-10 10:02 msv Note Added: 0072135
2017-11-10 10:13 bugmaster Changeset attached => occt master 510cb852
2017-11-10 10:13 bugmaster Status tested => verified
2017-11-10 10:13 bugmaster Resolution open => fixed
2017-11-10 12:15 git Note Added: 0072161
2017-11-10 12:15 git Note Added: 0072162
2018-02-17 23:59 abv Target Version 7.4.0 => 7.3.0
2018-06-29 21:15 aiv Fixed in Version => 7.3.0
2018-06-29 21:19 aiv Status verified => closed