MantisBT
Mantis Bug Tracker Workflow

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0027074Community[OCCT] OCCT:Modeling Datapublic2016-01-13 09:452017-08-29 09:36
ReporterRoman Lygin 
Assigned Toabv 
PrioritynormalSeverityfeature 
StatusfeedbackResolutionopen 
PlatformOSOS Version
Product Version[OCCT] 7.0.0 
Target VersionFixed in Version 
Summary0027074: Support of multi-span cache in Geom[2d]Adaptor
DescriptionOCC 7.0 moved B-Spline cache from the curve/surface classes (Geom[2d]_BSplineCurve, Geom_BSplineSurface) to Geom[2d]_Adaptor - see 0024682.

As discussed here (start with http://dev.opencascade.org/index.php?q=node/1138#comment-688 [^]), this exposes opportunity to increase performance by maintaining multi-cache (or multi-span cache) when Taylor's expansion coefficients are cached not only for the latest computed span but for N latest computed spans. This will improve cases of poor locality of points being computed (e.g. in triangulation algorithm or some user-specific owns) - see discussions:
- http://www.opencascade.com/content/bsplclibbohm [^]
- http://www.opencascade.com/content/speed-depends-number-faces. [^]

As touched in the discussions, the parameter N can be capped by some default and/or user-defined value (e.g. provided in Geom[2d]_Adaptor), i.e. it does not need to ensure that *all* spans are cached. Primary concern is memory footprint growth in the scenarios when the life span of the adaptor is significant enough.
Steps To ReproduceRefer to http://www.opencascade.com/content/bsplclibbohm [^] and http://www.opencascade.com/content/speed-depends-number-faces. [^] Take some arbitrary multi-span B-Spline and compare performance of evaluation of sample points with poor and good locality.

With multi-span cache these scenarios should differ much less than with single span cache.
TagsNo tags attached.
Test case number
Attached Files

- Relationships
parent of 0028240closedapn Open CASCADE Avoid redundant search for span index in evaluation of BSpline cache 
related to 0027491closedbugmaster Community Modeling Data - document thread-safety behavior of GeomAdaptor_Curve 

-  Notes
(0055644)
git (administrator)
2016-07-01 17:16

Branch CR27074 has been created by azv.

SHA-1: c976ed5f47d492cecc0fff95e9384e7b9702900a


Detailed log of new commits:

Author: azv
Date: Fri Jun 24 08:51:43 2016 +0300

    0027074: Support of multi-span cache in Geom[2d]Adaptor
    
    7. Fix regressions
    8. Optimizations for single-span cache
    9. Remove unused constructors in BSpl*Lib_Cache classes
    10. Optimize PeriodicNormalization function

Author: azv
Date: Mon Jun 20 16:58:16 2016 +0300

    0027074: Support of multi-span cache in Geom[2d]Adaptor
    
    5. Multi-span cache for curves.
    6. Renew cache when loading same curve/surface into adaptor.

Author: azv
Date: Tue Jun 14 17:07:21 2016 +0300

    0027074: Support of multi-span cache in Geom[2d]Adaptor
    
    1. Multi-span cache for surfaces.
    2. Move PeriodicNormalization from Cache to BSplCLib.
    3. Revision of BSplSLib_Cache and small improvements.
    4. Test command and synthetic test case to compare results for different number of cached spans.
(0055758)
git (administrator)
2016-07-08 14:49

Branch CR27074 has been updated forcibly by azv.

SHA-1: 99fdd72039bbfc25dffda0fad31387fa86b373e9
(0055797)
git (administrator)
2016-07-11 11:15

Branch CR27074 has been updated forcibly by azv.

SHA-1: d1ae6c9e4e4fd987d451569aa766b46d1a49a621
(0055799)
azv (developer)
2016-07-11 11:17

Dear Mikhail,

Could you, please, review branch CR27074.

Performance differences on some test cases, I have observed on my workstation (Intel Core i5-3700, 8GB RAM), are following:
bugs modalg_1 bug10160_7: 17.004109 / 14.6328938 [+16.20%]
bugs modalg_4 bug8842_7: 5.3976346 / 7.9716511 [-32.29%]
bugs modalg_5 bug23884: 4.3524279 / 7.8936506 [-44.86%]
bugs modalg_5 bug23892: 6.24004 / 10.5768678 [-41.00%]
bugs modalg_5 bug24208_13: 3.2916211 / 4.1808268 [-21.27%]
bugs modalg_5 bug24208_2: 2.6364169 / 3.6348233 [-27.47%]
bugs modalg_5 bug24208_6: 4.1652267 / 5.3976346 [-22.83%]
bugs modalg_5 bug24208_9: 2.0904134 / 2.8860185 [-27.57%]
bugs modalg_5 bug25742_1: 4.0404259 / 6.2088398 [-34.92%]
bugs modalg_6 bug26288: 16.2709043 / 21.2005359 [-23.25%]
bugs modalg_6 bug27167: 2.2932147 / 3.744024 [-38.75%]
bugs moddata_1 bug22759: 45.0218886 / 39.4214527 [+14.21%]
bugs moddata_1 bug54: 26.0989673 / 22.1365419 [+17.90%]
bugs step bug55: 33.0254117 / 29.2189873 [+13.03%]
de step_2 U4: 0.936006 / 20.9977346 [-95.54%]
de step_4 E6: 15.6001 / 13.0728838 [+19.33%]


Synthetic test case for evaluation of B-spline surfaces with multi-span cache:

* non-rational B-spline surface:
1-span cache  1.31506386423
5-span cache  0.243223187455
10-span cache 0.242868635163
25-span cache 0.251981716894


* rational B-spline surface:
1-span cache  1.45808923198
5-span cache  0.261591107817
10-span cache 0.259468273958
25-span cache 0.264532483823


Degraded time of some tests execution is caused by frequent rebuilding of caches and overhead costs for cache searching. I think these problems may be fixed by high level algorithms (changing number of cached spans or deactivating of caching).
(0055803)
git (administrator)
2016-07-11 11:33

Branch CR27074 has been updated by azv.

SHA-1: 56b324d11ab5ea229de687f235455ab6e3cfcfec


Detailed log of new commits:

Author: azv
Date: Mon Jul 11 11:34:28 2016 +0300

    Note in upgrade.md about multi-span implementation

(0055805)
Roman Lygin (developer)
2016-07-11 12:12

Performance regressions of up to 44% may not be accepted. The users should get the benefit out of the box, without a need to "fix high level algorithms".

If you believe that efficient implementation may not be provided at reasonable costs then the fix is just not worth it and single cache must be retained.
(0055807)
msv (developer)
2016-07-11 12:36

Dear Roman, regression is up to +19.33%, not 44%.
(0055810)
Roman Lygin (developer)
2016-07-11 12:49

Dear Mikhail,

I was referring to this line, assuming that you are comparing a base line with a current version (i.e. 4.35 vs 7.89 respectively):

bugs modalg_5 bug23884: 4.3524279 / 7.8936506 [-44.86%].

If it is another way around and the worst case is a drop of 19.33% then the point still holds - this is too much to accept.
(0055815)
Roman Lygin (developer)
2016-07-11 14:03

Further 2 cents.

I am not familiar with SparseArray (and how efficient it is about deletion operations) but you apparently could use std::list instead of mixing NCollection_SparceArray and _List.

Also note that SetLatestCache() called from FindCache() iterates twice:
1. HasValue()
2. SpanArray::Iterator

Using STL you could do this in one pass:

        struct Cache{};
        typedef std::pair <int, Cache> IndexedCache;
        std::list<IndexedCache, NCollection_StdAllocator<IndexedCache>> myList;

        int aSpanIndex = ...;
        auto anIt = std::find_if (myList.begin(), myList.end(), [&] (const IndexedCache& theCache)
            { return theCache.first == aSpanIndex; });
        if (anIt != myList.end()) { //exists, move to end
            myList.push_back (*anIt);
            myList.erase (anIt);
        }

But more importantly why do you need to physically move (Remove/Append) nodes at all? It looks like you could avoid dynamic (re)allocation at all, something like:

- have fixed vector of pairs {span_index, cache} - VC
- have fixed sorted vector of indices_into_VC sorted in the LRU manner - VI (i.e. values in VI are indices in the range [0, VC.size)). 0th corresponds to the last used span_index.
- at parameter U you evaluate span_index. Iterate in VI to find if span_index is in VC. Given that VI is sorted in LRU manner then it is highly probable you will find a match.
- If there is match then you simply update VI
- If there is no match then you replace a cache in VC at position VI.back and update VI

The above algorithm allows to avoid (or to significantly minimize) dynamic allocation.
(0055847)
msv (developer)
2016-07-12 12:05

Remarks:

src\Geom2dAdaptor\Geom2dAdaptor_Curve.cxx
src\GeomAdaptor\GeomAdaptor_Curve.cxx
src\GeomAdaptor\GeomAdaptor_Surface.cxx

- myCacheIsUsed is not initialized in constructors.
- myBezierFlatKnots is not needed, it is extra field, instead it is better to use automatic Array1.
- The next block is better to rewrite:
      if (myCacheIsUsed && myCurveCache.IsNull())
        CreateCache();
      if (myCurveCache.IsNull())
        myCurve->D0(U, P);
      else // use cached data
        myCurveCache->D0(U, P);
=>
      if (myCacheIsUsed)
      {
        if (myCurveCache.IsNull())
          CreateCache();
        myCurveCache->D0(U, P);
      }
      else
        myCurve->D0(U, P);
- It is better to not create cache in SetMaxSpansCached(). Instead, store myMaxSpans instead of myCacheIsUsed, and set number of spans in the cache when the cache is created, or here if the cache is not null.

src\BSplCLib\BSplCLib.hxx
src\BSplCLib\BSplCLib.cxx

- Use the method ElCLib::InPeriod instead of creation of a new similar one PeriodicNormalization.

src\BSplCLib\BSplCLib_Cache.hxx
src\BSplSLib\BSplSLib_Cache.hxx

- Why the methods accept simple type arguments by const reference?
  Standard_EXPORT void BuildCache(const Standard_Integer& theDegree,
                                  const Standard_Boolean& thePeriodic,
                                  const TColStd_Array1OfReal& theFlatKnots,
                                  const Standard_Integer& theCachedSpan,
                                  const TColgp_Array1OfPnt2d& thePoles2d,
                                  const TColStd_Array1OfReal* theWeights = NULL);
  Please change it to accept const values.
  The same is for methods D0, D1, etc.

src\BSplCLib\BSplCLib_Cache.cxx

- Please change constructor to use initializers instead of the body. Make sure to initialize all fields.

src\BSplCLib\BSplCLib_MultiSpanCacheStorage.hxx

- 70: irrelevant comment.
- 83: return simple type by value.

src\BSplCLib\BSplCLib_MultiSpanCacheStorage.gxx

- 18: must use the argument instead of constant
- in SetLatestCache, if myMaxSpansCount == 1 it returns false and will enforce cache rebuild.

src\BSplCLib\BSplCLib_MultiSpanCache.hxx
src\BSplSLib\BSplSLib_MultiSpanCache.hxx

- Change methods to accept simple types by values instead of references.
- 118, 135: possible type mismatch when passing parameter thePoles to the constructor of base class.

tests\perf\bspline\multispan

- 64: Elapsed => CPU
(0055852)
git (administrator)
2016-07-12 15:38

Branch CR27074 has been updated by azv.

SHA-1: 97740857fc8d361e2a0984008c8154be05ee0beb


Detailed log of new commits:

Author: azv
Date: Tue Jul 12 15:37:17 2016 +0300

    Remarks accomplishment

Author: azv
Date: Tue Jul 12 13:53:55 2016 +0300

    Use LocalArray instead of SparseArray

(0055854)
azv (developer)
2016-07-12 15:40

Dear Roman,

Thanks for your participation and useful comments, they are taken into account. Please see updated branch CR27074. Performance comparison will be shared later.


Dear Mikhail,

Could you, please, review updated state of branch CR27074. Almost all remarks are considered.

>> - in SetLatestCache, if myMaxSpansCount == 1 it returns false and will enforce cache rebuild.
This has been done consciously, because if the index of last used span is not correspond to the given parameter, we really need to update cache.

>> src\BSplCLib\BSplCLib_MultiSpanCache.hxx
>> - 118, 135: possible type mismatch when passing parameter thePoles to the constructor of base class.
This should not lead to warnings, but I have explicitly defined template parameters for the base class in the latest commit.
(0055877)
git (administrator)
2016-07-13 07:38

Branch CR27074 has been updated forcibly by azv.

SHA-1: 3f4ddcc1f7ce80257b4f5bd2c5887ca878332ffc
(0055882)
msv (developer)
2016-07-13 10:53

Remarks to commit "Use LocalArray instead of SparseArray":

- try using the function memmove_s instead of iterations in ShiftCachedSpans.
- I think the field myLastCache is extra. The implementation can easily do without it.
(0055883)
msv (developer)
2016-07-13 11:23

More remarks:

in adaptors:

- myCacheIsUsed is not needed, the condition "myMaxSpansCached>0" replaces it. Initialize myMaxSpansCached with BSplCLib_MultiSpanCacheStorage::MAX_SPANS_COUNT. In this case you will not need to make branch in CreateCache(), lines 606 and 616.

src\BSplCLib\BSplCLib_MultiSpanCacheStorage.hxx

- make the constant MAX_SPANS_COUNT public, as it is used in public API.
- 37-49: move private part below the public one.
(0055903)
git (administrator)
2016-07-14 11:40

Branch CR27074 has been updated forcibly by azv.

SHA-1: 368355f10566ba70e1c57832e8d12a6073f244df
(0055934)
git (administrator)
2016-07-15 11:38

Branch CR27074 has been updated by azv.

SHA-1: cdb82b7490d6a193758b15ebbacb89cfd3c055ba


Detailed log of new commits:

Author: azv
Date: Fri Jul 15 11:39:19 2016 +0300

    Remarks accomplishment (part 2)

(0055949)
git (administrator)
2016-07-15 15:43

Branch CR27074_LC has been created by azv.

SHA-1: 79e2707dd008081969228a4bb2741f21d621f8c1


Detailed log of new commits:

Author: azv
Date: Fri Jul 15 15:43:32 2016 +0300

    0027074: Support of multi-span cache in Geom[2d]Adaptor
    
    1. Multi-span cache for curve and surfaces.
    2. Revision of BSplSLib_Cache and small improvements.
    3. Test command and synthetic test case to compare results for different number of cached spans.
    4. Renew cache when loading same curve/surface into adaptor.
    5. Optimizations for single-span cache
    6. Remove unused constructors in BSpl*Lib_Cache classes
    7. Allocate cache on first call, not when loading a curve/surface
    8. Option in adaptors to disable caching
    9. Note in upgrade.md about multi-span implementation
(0055950)
azv (developer)
2016-07-15 15:43

Branch CR27074_LC contains latest changes. Some results are shown below. This branch dedicated to approach with limited number of cached spans, which may be controlled by user. Another approach will be represented a little bit later, it will store cache for each span where B-spline is requested to evaluate.

bugs mesh bug25378_3_3: 14.7108943 / 17.3473112 [-15.20%]
bugs mesh bug25806: 27.6277771 / 31.4654017 [-12.20%]
bugs modalg_2 bug5157_1: 47.7987064 / 53.0715402 [-9.94%]
bugs modalg_2 bug5157_2: 47.6895057 / 53.0559401 [-10.11%]
bugs modalg_4 bug8842_7: 5.2884339 / 7.8468503 [-32.60%]
bugs modalg_5 bug23884: 4.212027 / 7.7376496 [-45.56%]
bugs modalg_5 bug23892: 5.928038 / 10.4208668 [-43.11%]
bugs modalg_6 bug26132: 7.1136456 / 8.0964519 [-12.14%]
bugs modalg_6 bug26288: 16.2865044 / 21.1693357 [-23.07%]
bugs step bug24024: 35.4590273 / 39.4994532 [-10.23%]
de step_2 J9: 5.2728338 / 6.084039 [-13.33%]
de step_2 U4: 0.9984064 / 20.748133 [-95.19%]
heal split_angle_advanced ZG1: 13.728088 / 15.4596991 [-11.20%]
mesh advanced_incmesh B5: 17.4253117 / 19.9993282 [-12.87%]


Regarding perfomance regressions described above, current results are:
bugs modalg_1 bug10160_7: 14.6016936 / 14.6328938 [-0.21%]
bugs moddata_1 bug22759: 37.0658376 / 39.4214527 [-5.98%]
bugs moddata_1 bug54: 22.4953442 / 22.1365419 [+1.62%]
bugs step bug55: 29.484189 / 29.2189873 [+0.90%]
de step_4 E6: 13.1508843 / 13.0728838 [+0.59%]
(0056175)
git (administrator)
2016-07-22 13:43

Branch CR27074_ULC has been created by azv.

SHA-1: 316e46719a9242cc456aa1cc97141553cbb3641c


Detailed log of new commits:

Author: azv
Date: Fri Jul 15 15:43:32 2016 +0300

    0027074: Support of multi-span cache in Geom[2d]Adaptor
    
    The multi-span cache is stored as matrix (for surface) or vector (for curves) of caches. Each cell corresponds to a span. The cache is initialized on first call and destroyed when adaptor is destroyed.
    
    1. Multi-span cache for curve and surfaces.
    2. Revision of BSplSLib_Cache and small improvements.
    3. Renew cache when loading same curve/surface into adaptor.
    4. Optimizations for single-span cache
    5. Remove unused constructors in BSpl*Lib_Cache classes
    6. Allocate cache on first call, not when loading a curve/surface
    7. Note in upgrade.md about multi-span implementation
(0056213)
git (administrator)
2016-07-26 10:02

Branch CR27074_LC has been updated forcibly by azv.

SHA-1: f2b4d89d471d7f72ffbd2de31cf67662fac6607f
(0056214)
azv (developer)
2016-07-26 10:02

Comparison results of some test cases for two approaches of multi-cache storage are represented below.

CR27074_LC: Multi-span cache contains limited number of cached spans for curve/surface. Maximal quntity of caches may be managed by user through corresponging methods of adaptors. In case of add new cache when all cells are already filled, the least recently used cache is replaced.

CR27074_ULC: Multi-span cache may store caches for all spans in worst case. This approach stores cells for each span on curve/surface. The span is cached at first request. This approach is more greedy to memory.

CPU differences:
        Test case                          Master          CR2074_LC             CR27074_ULC
boolean bcut_complex P6                  16.7077071   14.4300925 [-13.63%]   11.2476721 [-32.68%] 
boolean bopcommon_complex D1             10.2336656    9.2976596 [ -9.15%]    9.2976596 [ -9.15%] 
boolean bopcommon_complex D6             11.2632722    9.1728588 [-18.56%]    9.6408618 [-14.40%] 
boolean bopcut_complex N4                 4.3836281    3.588023  [-18.15%]    3.3072212 [-24.56%] 
boolean bopfuse_complex C8               13.572087    11.9496766 [-11.95%]   11.5908743 [-14.60%] 
bugs fclasses bug22980                    4.68003      1.8408118 [-60.67%]    1.6692107 [-64.33%] 
bugs heal bug25712                      202.0836954  189.385214  [ -6.28%]  170.5714934 [-15.59%] 
bugs mesh bug25378_1_3                  186.7019968  162.7714434 [-12.82%]  168.7462817 [ -9.62%] 
bugs mesh bug25378_3_3                   17.2849108   14.2428913 [-17.60%]   16.8169078 [ -2.71%] 
bugs modalg_1 bug10160_2                 13.0104834   12.8544824 [ -1.20%]   11.1852717 [-14.03%] 
bugs modalg_1 bug10160_3                 12.2928788   11.4036731 [ -7.23%]   10.5456676 [-14.21%] 
bugs modalg_1 bug10160_4                 12.3708793   11.6376746 [ -5.93%]   10.6860685 [-13.62%] 
bugs modalg_1 bug10160_9                 14.5704934   13.4316861 [ -7.82%]   12.7296816 [-12.63%] 
bugs modalg_1 bug10160_10                14.6796941   13.6188873 [ -7.23%]   12.7764819 [-12.96%] 
bugs modalg_2 bug22770_11                 5.9592382    5.6316361 [ -5.50%]    4.9140315 [-17.54%] 
bugs modalg_2 bug23100                    6.1152392    6.084039  [ -0.51%]    4.4304284 [-27.55%] 
bugs modalg_2 bug5157_1                  66.6280271   54.7095507 [-17.89%]   40.56026   [-39.12%] 
bugs modalg_2 bug5157_2                  67.236431    54.6783505 [-18.68%]   40.5134597 [-39.74%] 
bugs modalg_3 bug698                    166.7026686  150.2601632 [ -9.86%]   66.1132238 [-60.34%] 
bugs modalg_4 bug697_2                    4.4460285    3.744024  [-15.79%]    3.3852217 [-23.86%] 
bugs modalg_4 bug697_4                    4.6488298    3.9936256 [-14.09%]    3.5724229 [-23.15%] 
bugs modalg_4 bug697_7                    4.6020295    4.4304284 [ -3.73%]    3.6036231 [-21.69%] 
bugs modalg_4 bug697_8                    4.5708293    3.9156251 [-14.33%]    3.6348233 [-20.48%] 
bugs modalg_4 bug8842_7                   7.9248508    5.0856326 [-35.83%]    3.7284239 [-52.95%] 
bugs modalg_5 bug23884                    7.9092507    4.0716261 [-48.52%]    3.3072212 [-58.19%] 
bugs modalg_5 bug23892                   10.5612677    5.772037  [-45.35%]    3.6972237 [-64.99%] 
bugs modalg_5 bug24208_2                  3.7284239    2.1684139 [-41.84%]    2.5272162 [-32.22%] 
bugs modalg_5 bug24208_3                  2.8704184    1.9656126 [-31.52%]    2.1216136 [-26.09%] 
bugs modalg_5 bug24208_4                  4.0716261    2.6364169 [-35.25%]    2.9328188 [-27.97%] 
bugs modalg_5 bug24208_6                  5.4132347    3.5568228 [-34.29%]    3.9468253 [-27.09%] 
bugs modalg_5 bug24208_9                  2.8548183    1.716011  [-39.89%]    2.0436131 [-28.42%] 
bugs modalg_5 bug24208_10                 2.1684139    1.4820095 [-31.65%]    1.7316111 [-20.14%] 
bugs modalg_5 bug24208_11                 3.276021     2.0592132 [-37.14%]    2.3712152 [-27.62%] 
bugs modalg_5 bug24208_13                 4.1652267    2.7768178 [-33.33%]    3.2136206 [-22.85%] 
bugs modalg_5 bug25742_1                  6.3492407    3.9156251 [-38.33%]    3.7752242 [-40.54%] 
bugs modalg_6 bug26288                   21.3253367   15.6781005 [-26.48%]   15.8029013 [-25.90%] 
bugs modalg_6 bug26717                   34.32022     29.952192  [-12.73%]   13.6656876 [-60.18%] 
bugs modalg_6 bug26952_1                  8.6580555    6.7860435 [-21.62%]    6.3492407 [-26.67%] 
bugs modalg_6 bug26952_2                  7.4256476    6.0060385 [-19.12%]    5.7564369 [-22.48%] 
bugs modalg_6 bug27167                    3.7908243    2.2152142 [-41.56%]    2.2152142 [-41.56%] 
bugs modalg_6 bug27341                    5.3664344    4.4148283 [-17.73%]    4.056026  [-24.42%] 
bugs modalg_6 bug27341_202                2.4336156    1.8564119 [-23.72%]    1.6692107 [-31.41%] 
bugs modalg_6 bug27341_205                3.4164219    2.7456176 [-19.63%]    2.5116161 [-26.48%] 
bugs modalg_6 bug27341_207                2.9328188    2.2464144 [-23.40%]    2.0124129 [-31.38%] 
bugs moddata_1 bug22759                  43.212277    37.2218386 [-13.86%]   35.4746274 [-17.91%] 
bugs moddata_3 bug25179                 765.7777088  692.9252418 [ -9.51%]  733.7975038 [ -4.18%] 
bugs step bug24024                       39.6866544   33.8210168 [-14.78%]   34.5542215 [-12.93%] 
de step_2 U4                             20.8105334    0.9516061 [-95.43%]    0.8892057 [-95.73%] 
de step_3 A6                             10.4676671   10.2648658 [ -1.94%]    8.0496516 [-23.10%] 
de step_3 A7                             10.4988673   10.3740665 [ -1.19%]    8.3148533 [-20.80%] 
de step_3 B5                            118.716761   112.4611209 [ -5.27%]  115.908743  [ -2.37%] 
de step_4 I1                            350.6434477  327.0560965 [ -6.73%]  316.2764274 [ -9.80%] 
heal surface_to_revolution_advanced A2   16.7701075   14.5392932 [-13.30%]   13.7436881 [-18.05%] 
heal surface_to_revolution_advanced ZE8  64.3036122   56.0979596 [-12.76%]   53.664344  [-16.55%] 
heal surface_to_revolution_advanced ZE9  67.2520311   59.4987814 [-11.53%]   55.3491548 [-17.70%] 
mesh advanced_incmesh B5                 18.9385214   16.3957051 [-13.43%]   18.7513202 [ -0.99%] 
mesh advanced_incmesh B8                  3.0576196    2.2308143 [-27.04%]    1.9344124 [-36.73%] 
mesh advanced_mesh B5                    18.2989173   16.3957051 [-10.40%]   18.0025154 [ -1.62%] 
mesh advanced_mesh B8                     3.2136206    2.2620145 [-29.61%]    1.9500125 [-39.32%] 
mesh advanced_shading B5                 49.3743165   41.6366669 [-15.67%]   45.7550933 [ -7.33%] 
mesh standard_mesh N2                     5.5380355    4.6332297 [-16.34%]    4.0872262 [-26.20%] 
mesh standard_mesh O3                     8.1900525    5.4444349 [-33.52%]    5.0700325 [-38.10%] 


Top differences of memory are presented for CR27074_ULC only, because limited multi-span cache does not show significant deviation.

MEMORY differences:
     Test case             Master    CR27074_ULC
boolean bopcut_complex N4   50109   61957 [23.64%]
boolean bopsection D4       36560   47069 [28.74%]
bugs modalg_1 bug10160_1   257485  314296 [22.06%]
bugs modalg_1 bug10160_2   270858  349273 [28.95%]
bugs modalg_1 bug10160_3   257488  314300 [22.06%]
bugs modalg_1 bug10160_4   257487  314299 [22.06%]
bugs modalg_1 bug10160_5   150616  193151 [28.24%]
bugs modalg_1 bug10160_6   183020  254709 [39.17%]
bugs modalg_1 bug10160_7   150617  193151 [28.24%]
bugs modalg_1 bug10160_8   150627  193145 [28.23%]
bugs modalg_1 bug10160_9   122898  152323 [23.94%]
bugs modalg_1 bug10160_10  129465  171021 [32.10%]
bugs modalg_1 bug10160_11  122899  152325 [23.94%]
bugs modalg_1 bug10160_12  122904  152329 [23.94%]
bugs modalg_5 bug25828_1     5971    6647 [11.32%]
bugs modalg_5 bug25828_2     5969    6644 [11.31%]


Synthetic test cases (perf bspline multispan) are introduced for both approaches to show potential profit of multi-span cache. Test cases are different, so their results cannot be compared directly.

CR27074_LC:
Single-span cache           5.0388323
Multi-span cache (5 spans)  0.7020045
                 (10 spans) 0.7332047
                 (25 spans) 0.780005


CR27074_ULC:
Single-span cache 5.0232322
Multi-span cache  0.5772037
(0056215)
azv (developer)
2016-07-26 10:12

Dear Mikhail,

Could you, please, review branches CR27074_LC and CR27074_ULC? We need to choose most appropriate approach for integration to Master.

As you can see, unlimited cache (CR27074_ULC) is faster in general, but there are some cases, the limited cache is better. On the other hand, unlimited cache requires more memory.
(0056409)
msv (developer)
2016-08-03 10:51

Let's keep with CR27074_ULC. Please make there corrections as we agreed.
(0056501)
git (administrator)
2016-08-05 15:10

Branch CR27074_ULC has been updated by azv.

SHA-1: 2151c67443ee202b6fc0a552fd35c4ce9ec82412


Detailed log of new commits:

Author: azv
Date: Fri Aug 5 14:12:36 2016 +0300

    Remarks

(0056502)
git (administrator)
2016-08-05 15:20

Branch CR27074_ULC_1 has been created by azv.

SHA-1: 7dd5d42d702742809bb11dd7bee22571b17dffef


Detailed log of new commits:

Author: azv
Date: Fri Aug 5 15:21:34 2016 +0300

    0027074: Support of multi-span cache in Geom[2d]Adaptor
    
    The multi-span cache is stored as matrix (for surface) or vector (for curves) of caches. Each cell corresponds to a span. The cache is initialized on first call and destroyed when adaptor is destroyed.
    
    1. Multi-span cache for curve and surfaces.
    2. Revision of BSplSLib_Cache and small improvements.
    3. Renew cache when loading same curve/surface into adaptor.
    4. Optimizations for single-span cache
    5. Remove unused constructors in BSpl*Lib_Cache classes
    6. Allocate cache on first call, not when loading a curve/surface
    7. Note in upgrade.md about multi-span implementation
(0056503)
azv (developer)
2016-08-05 15:21

Dear Mikhail,

Please review branch CR27074_ULC_1, which has same changes as CR27074_ULC, but squashed into single commit and rebased on the latest master.

I have added one more synthetic test case (perf bspline hugenurbs), which evaluates B-spline surface with 1000x1000 spans. The test devoted to comparison of allocated memory. Results are following:

Master:         784148 KB
CR27074_ULC_1: 1838841 KB
(0056535)
msv (developer)
2016-08-08 10:02

Dear azv, no remarks, except defining of cpulimit differently for debug and release.
Dear abv, please give your opinion about which solution (LC or ULC) is more preferable.
(0056536)
git (administrator)
2016-08-08 10:14

Branch CR27074_ULC_1 has been updated forcibly by azv.

SHA-1: 300fd122bf1f6881ce25e720a89bd35899150f7e
(0058040)
git (administrator)
2016-09-23 07:34

Branch CR27074_ULC_2 has been created by abv.

SHA-1: bf6934266402870a854b447cb31bf9389c4762ff


Detailed log of new commits:

Author: azv
Date: Fri Aug 5 15:21:34 2016 +0300

    0027074: Support of multi-span cache in Geom[2d]Adaptor
    
    The multi-span cache is stored as matrix (for surface) or vector (for curves) of caches. Each cell corresponds to a span. The cache is initialized on first call and destroyed when adaptor is destroyed.
    
    1. Multi-span cache for curve and surfaces.
    2. Revision of BSplSLib_Cache and small improvements.
    3. Renew cache when loading same curve/surface into adaptor.
    4. Optimizations for single-span cache
    5. Remove unused constructors in BSpl*Lib_Cache classes
    6. Allocate cache on first call, not when loading a curve/surface
    7. Note in upgrade.md about multi-span implementation
(0058041)
abv (manager)
2016-09-23 07:38

Artem, I have rebased your branch on current master -- see CR27074_ULC_2 -- and observe memory leaks reported by tests bugs caf bug23489 and bugs moddata_3 bug162, please check on your side. Notably, tests bugs caf bug23489 seems to have nothing to do with BSpline calculations at all.
(0058164)
git (administrator)
2016-09-26 15:51

Branch CR27074_ULC_3 has been created by azv.

SHA-1: 65732b21681b94058d4abbeca61af7c97ac42530


Detailed log of new commits:

Author: azv
Date: Fri Aug 5 15:21:34 2016 +0300

    0027074: Support of multi-span cache in Geom[2d]Adaptor
    
    The multi-span cache is stored as matrix (for surface) or vector (for curves) of caches. Each cell corresponds to a span. The cache is initialized on first call and destroyed when adaptor is destroyed.
    
    1. Multi-span cache for curve and surfaces.
    2. Revision of BSplSLib_Cache and small improvements.
    3. Renew cache when loading same curve/surface into adaptor.
    4. Optimizations for single-span cache
    5. Remove unused constructors in BSpl*Lib_Cache classes
    6. Allocate cache on first call, not when loading a curve/surface
    7. Note in upgrade.md about multi-span implementation
(0058165)
azv (developer)
2016-09-26 15:53

Dear Andrey,

Please, review branch CR27074_ULC_3. I suppose, memory leaks are eliminated.
(0058238)
abv (manager)
2016-09-28 11:31

Please implement proper construction and destruction of array items in NCollection_LocalArray, instead of nullifying their items in destructors of cache classes.

I have tested the new branch (with -parallel 0) and confirm that memory leak has gone. Note that due to this memory leak, previously reported results of memory measurements should be considered invalid.
(0058373)
abv (manager)
2016-10-03 19:53

Performance results of my testing are contradictory.

Indeed, there are some cases where considerable improvement is shown, here is top 10:

CPU de step_2 U4: 0.765625 / 38.953125 [-98.03%]
CPU bugs modalg_5 bug23892: 3.21875 / 8.765625 [-63.28%]
CPU bugs modalg_5 bug23884: 2.59375 / 6.578125 [-60.57%]
CPU bugs modalg_3 bug698: 55.1875 / 137.3125 [-59.81%]
CPU bugs modalg_4 bug8842_7: 3.140625 / 6.578125 [-52.26%]
CPU bugs modalg_5 bug25742_1: 3.03125 / 5 [-39.38%]
CPU mesh advanced_incmesh_parallel B8: 1.609375 / 2.546875 [-36.81%]
CPU mesh advanced_mesh B8: 1.625 / 2.546875 [-36.20%]
CPU mesh advanced_incmesh B8: 1.640625 / 2.53125 [-35.19%]
CPU boolean bcut_complex P6: 8.5625 / 12.734375 [-32.76%]

On the other side, there are CPU regressions as well, the worst are:

CPU bugs moddata_1 bug187: 4.796875 / 3.796875 [+26.34%]
CPU mesh advanced_shading B5: 37.40625 / 30.15625 [+24.04%]
(0058638)
abv (manager)
2016-10-13 01:45

Huge acceleration on test de step_2 U4 is due to changes in BSplCLib::BuildCache() (span index passed as argument)
(0062924)
msv (developer)
2017-01-24 10:09

As I understand, the change that caused the main performance improvement was implemented in the separate issue 0028240.
Now we should decide what to do with this issue. Does not this patch give any improvements? If so, we shall close this bug.
(0063005)
abv (manager)
2017-01-25 14:13

I have seen no improvements that would worth the effort. I still have to put here summary of my experiments, then we will decide.
(0063487)
BenjaminBihler (developer)
2017-02-07 13:53

Hi!

Since I am the author of the forum post "Speed Depends on Number of Faces" I would like to share some of my experiences with you. I have created a shell twice, once as one face and once as several faces. Then I have done computations on that shell (solving an ordinary differential equations in stripes along the shell doing mainly D0, D1 and D2 evaluations). The computation times are as follows:

OCE 6.8.0
One Face: 57s
Nine Faces: 16s

Commit cdb82b7490d6a193758b15ebbacb89cfd3c055ba of Branch CR27074
One Face: 7s
Nine Faces: 7s

Commit 4cf17e1c042e8fbcd910c832d1e7d48743422c6d of Current Master
One Face: 10s
Nine Faces: 8s

So my conclusion is that there is a great improvement between 6.8.0 and the current code (you have done a great work!!!). The performance difference between one face and many faces is much reduced. Still I consider the performance benefit from branch CR27074 a significant improvement in this example. If you decide to reject multi-span caches in general, would it be worth it to make them optional (and configurable)?

Benjamin
(0063991)
git (administrator)
2017-02-25 09:40

Branch CR27074_ULC_4 has been created by abv.

SHA-1: 78767df500b11387ab58d2deb50c905aeca46134


Detailed log of new commits:

Author: abv
Date: Fri Feb 24 17:33:11 2017 +0300

    Added tests for performance of bspline curve evaluation

Author: azv
Date: Fri Aug 5 15:21:34 2016 +0300

    0027074: Support of multi-span cache in Geom[2d]Adaptor
    
    The multi-span cache is stored as matrix (for surface) or vector (for curves) of caches. Each cell corresponds to a span. The cache is initialized on first call and destroyed when adaptor is destroyed.
    
    1. Multi-span cache for curve and surfaces.
    2. Revision of BSplSLib_Cache and small improvements.
    3. Renew cache when loading same curve/surface into adaptor.
    4. Optimizations for single-span cache
    5. Remove unused constructors in BSpl*Lib_Cache classes
    6. Allocate cache on first call, not when loading a curve/surface
    7. Note in upgrade.md about multi-span implementation
    
    Conflicts:
        dox/dev_guides/upgrade/upgrade.md
        src/GeomAdaptor/GeomAdaptor_Curve.cxx
        tests/blend/simple/Q6
(0063992)
abv (manager)
2017-02-25 10:03

For the moment the multispan evaluation does not seem to give sufficiently stable improvement to adopt it for OCCT.

Note that one important excpectation was that such improvement would allow making adaptors thread-safe, by eliminating thread-dependent data from the cache. This turned to be not the case: it is still necessary to cache index of the current span, to avoid spending time for searching for the span on each call. If this caching is removed, search for the span (usually performed by BSplCLib::LocateParameter()) takes a lot of time and kills performance.

I have rebased relevant branch on current master, see CR27074_ULC_4.
Here is a list of differences I found in tests (executed with "-parallel 0" to avoid instabilities due to parallel execution).

CPU decreased:

CPU boolean bcut_complex P6: 8.734375 / 12.6875 [-31.16%]
CPU bugs heal bug25712: 104.9375 / 119.359375 [-12.08%]
CPU bugs modalg_2 bug23100: 3.75 / 4.859375 [-22.83%]
CPU bugs modalg_3 bug698: 54.640625 / 136.71875 [-60.03%]
CPU bugs modalg_4 bug8842_7: 3.09375 / 6.640625 [-53.41%]
CPU bugs modalg_5 bug23884: 2.546875 / 6.328125 [-59.75%]
CPU bugs modalg_5 bug23892: 3.109375 / 8.625 [-63.95%]
CPU bugs modalg_6 bug26288: 12.25 / 16.453125 [-25.55%]
CPU bugs modalg_6 bug26717: 11.328125 / 27.578125 [-58.92%]
CPU bugs modalg_6 bug26952_1: 4.828125 / 6.1875 [-21.97%]
CPU bugs modalg_6 bug27033: 112.859375 / 133.8125 [-15.66%]
CPU bugs modalg_6 bug27167: 1.796875 / 2.9375 [-38.83%]
CPU bugs moddata_1 bug22759: 27.1875 / 30.953125 [-12.17%]
CPU de step_3 A6: 6.5 / 8.328125 [-21.95%]
CPU de step_3 A7: 6.453125 / 8.265625 [-21.93%]
CPU mesh advanced_incmesh B8: 1.578125 / 2.375 [-33.55%]
CPU mesh advanced_incmesh_parallel B8: 1.59375 / 2.4375 [-34.62%]
CPU mesh advanced_mesh B8: 1.65625 / 2.484375 [-33.33%]
COUNTER bop: perf modalg bug10160_9: 6.578125 / 7.9375 [-17.13%]
COUNTER BBuild: perf modalg bug25742_1: 2.703125 / 4.59375 [-41.16%]
CPU perf modalg bug25742_1: 3.09375 / 5.015625 [-38.32%]
CPU perf modalg bug5157_1: 32.96875 / 40.78125 [-19.16%]
CPU perf modalg bug5157_2: 33.03125 / 40.625 [-18.69%]

CPU increased:

CPU bugs heal bug210: 7.21875 / 5.765625 [+25.20%]
CPU bugs mesh bug25806: 25.90625 / 22.5625 [+14.82%]
CPU bugs mesh bug27384_1: 25.25 / 21.59375 [+16.93%]
CPU bugs moddata_1 bug187: 4.640625 / 3.546875 [+30.84%]
CPU de step_3 A5: 29.703125 / 24.21875 [+22.65%]
CPU de step_3 A9: 29.625 / 23.640625 [+25.31%]
CPU de step_3 D8: 29.640625 / 24.25 [+22.23%]

In addition, some increase of used memory is reported on multiple cases, but this is expected and does not seem critical.

The totals are:

Total MEMORY difference: 57927868 / 57243401 [+1.20%]
Total CPU difference: 14925.59375 / 14924.609375 [+0.01%]

That is, there is no visible CPU improvement on average.
(0063993)
git (administrator)
2017-02-25 10:05

Branch CR27074_ULC_4 has been updated forcibly by abv.

SHA-1: 41c79a7727afb5238a5f7259d50efe49e74ab9c9

- Issue History
Date Modified Username Field Change
2016-01-13 09:45 Roman Lygin New Issue
2016-01-13 09:45 Roman Lygin Assigned To => msv
2016-05-23 19:26 abv Relationship added related to 0027491
2016-06-01 12:47 msv Assigned To msv => azv
2016-06-01 12:47 msv Status new => assigned
2016-07-01 17:16 git Note Added: 0055644
2016-07-08 14:49 git Note Added: 0055758
2016-07-11 11:15 git Note Added: 0055797
2016-07-11 11:17 azv Note Added: 0055799
2016-07-11 11:17 azv Assigned To azv => msv
2016-07-11 11:17 azv Status assigned => resolved
2016-07-11 11:33 git Note Added: 0055803
2016-07-11 12:12 Roman Lygin Note Added: 0055805
2016-07-11 12:36 msv Note Added: 0055807
2016-07-11 12:49 Roman Lygin Note Added: 0055810
2016-07-11 14:03 Roman Lygin Note Added: 0055815
2016-07-12 12:05 msv Note Added: 0055847
2016-07-12 12:05 msv Assigned To msv => azv
2016-07-12 12:05 msv Status resolved => assigned
2016-07-12 15:38 git Note Added: 0055852
2016-07-12 15:40 azv Note Added: 0055854
2016-07-12 15:40 azv Assigned To azv => msv
2016-07-12 15:40 azv Status assigned => resolved
2016-07-13 07:38 git Note Added: 0055877
2016-07-13 10:12 azv Assigned To msv => azv
2016-07-13 10:12 azv Status resolved => assigned
2016-07-13 10:53 msv Note Added: 0055882
2016-07-13 11:23 msv Note Added: 0055883
2016-07-14 11:40 git Note Added: 0055903
2016-07-15 11:38 git Note Added: 0055934
2016-07-15 15:43 git Note Added: 0055949
2016-07-15 15:43 azv Note Added: 0055950
2016-07-22 13:43 git Note Added: 0056175
2016-07-26 10:02 git Note Added: 0056213
2016-07-26 10:02 azv Note Added: 0056214
2016-07-26 10:12 azv Note Added: 0056215
2016-07-26 10:12 azv Assigned To azv => msv
2016-07-26 10:12 azv Status assigned => feedback
2016-08-03 10:51 msv Note Added: 0056409
2016-08-03 10:51 msv Assigned To msv => azv
2016-08-03 10:51 msv Status feedback => assigned
2016-08-05 15:10 git Note Added: 0056501
2016-08-05 15:20 git Note Added: 0056502
2016-08-05 15:21 azv Note Added: 0056503
2016-08-05 15:21 azv Assigned To azv => msv
2016-08-05 15:21 azv Status assigned => resolved
2016-08-08 10:02 msv Note Added: 0056535
2016-08-08 10:02 msv Assigned To msv => abv
2016-08-08 10:02 msv Status resolved => feedback
2016-08-08 10:14 git Note Added: 0056536
2016-09-23 07:34 git Note Added: 0058040
2016-09-23 07:38 abv Note Added: 0058041
2016-09-23 07:38 abv Assigned To abv => azv
2016-09-26 15:51 git Note Added: 0058164
2016-09-26 15:53 azv Note Added: 0058165
2016-09-26 15:53 azv Assigned To azv => abv
2016-09-26 15:53 azv Status feedback => resolved
2016-09-28 11:31 abv Note Added: 0058238
2016-09-28 11:31 abv Assigned To abv => azv
2016-09-28 11:31 abv Status resolved => assigned
2016-10-03 19:53 abv Note Added: 0058373
2016-10-13 01:45 abv Note Added: 0058638
2016-11-01 06:18 abv Target Version 7.1.0 => 7.2.0
2016-12-18 09:38 abv Relationship added parent of 0028240
2017-01-24 10:09 msv Note Added: 0062924
2017-01-24 10:09 msv Assigned To azv => abv
2017-01-24 10:09 msv Status assigned => feedback
2017-01-25 14:13 abv Note Added: 0063005
2017-02-07 13:53 BenjaminBihler Note Added: 0063487
2017-02-25 09:40 git Note Added: 0063991
2017-02-25 10:03 abv Note Added: 0063992
2017-02-25 10:05 git Note Added: 0063993
2017-08-15 15:43 abv Relationship added related to 0024238
2017-08-29 09:36 abv Target Version 7.2.0 =>


Copyright © 2000 - 2019 MantisBT Team
Powered by Mantis Bugtracker