MantisBT
Mantis Bug Tracker Workflow

View Issue Details Jump to Notes ] Related Changesets ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0029302Open CASCADE[OCCT] OCCT:Foundation Classespublic2017-11-08 15:222018-06-29 21:19
Reporterkgv 
Assigned Tobugmaster 
PrioritynormalSeverityintegration request 
StatusclosedResolutionfixed 
PlatformOSOS Version
Product Version 
Target Version[OCCT] 7.3.0Fixed in Version[OCCT] 7.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
Attached Files

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

-  Notes
(0072052)
git (administrator)
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 (administrator)
2017-11-08 17:48

Branch CR29302 has been updated forcibly by kgv.

SHA-1: 3810e244efe4ecf051296f293909501bd740f40d
(0072063)
git (administrator)
2017-11-08 18:14

Branch CR29302 has been updated forcibly by kgv.

SHA-1: 87421db9cd65b17a0f71a4e18caa8e2b39fbdb19
(0072094)
git (administrator)
2017-11-08 21:28

Branch CR29302 has been updated forcibly by kgv.

SHA-1: 66bfa24fee489a5e6ee6009612e59543f176547f
(0072095)
kgv (developer)
2017-11-08 21:40

Patch is ready for review.
(0072096)
git (administrator)
2017-11-09 00:13

Branch CR29302 has been updated forcibly by kgv.

SHA-1: 491d5a2e311c5f2d870729ed8bc0b3bac9686971
(0072097)
git (administrator)
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 (developer)
2017-11-09 10:35

Test results:

http://jenkins-test-10.nnov.opencascade.com/view/CR29302_1-master-KGV [^]
(0072110)
abv (manager)
2017-11-09 12:38

No remarks, please integrate
(0072111)
bugmaster (administrator)
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 (developer)
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 (administrator)
2017-11-10 12:15

Branch CR29302 has been deleted by kgv.

SHA-1: 491d5a2e311c5f2d870729ed8bc0b3bac9686971
(0072162)
git (administrator)
2017-11-10 12:15

Branch CR29302_1 has been deleted by kgv.

SHA-1: 91fc948ac06d4231f8831fddbf9003198a6ee023

- Related Changesets
occt: master 510cb852
Timestamp: 2017-11-08 12:25:51
Author: 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.
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 View Revisions
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 user533 Fixed in Version => 7.3.0
2018-06-29 21:19 user533 Status verified => closed


Copyright © 2000 - 2018 MantisBT Team
Powered by Mantis Bugtracker