View Issue Details

IDProjectCategoryView StatusLast Update
0027074CommunityOCCT:Modeling Datapublic2019-10-05 12:55
ReporterRoman Lygin Assigned Toabv 
PrioritynormalSeverityfeature 
Status feedbackResolutionopen 
Product Version7.0.0 
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

  • CR27074_LC-0027074-Support-of-multi-span-cache-in-Geom-2d-Adapt.patch (150,763 bytes)
  • CR27074_ULC-0027074-Support-of-multi-span-cache-in-Geom-2d-Adapt.patch (131,510 bytes)

Relationships

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

Activities

git

2016-07-01 17:16

administrator   ~0055644

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.

git

2016-07-08 14:49

administrator   ~0055758

Branch CR27074 has been updated forcibly by azv.

SHA-1: 99fdd72039bbfc25dffda0fad31387fa86b373e9

git

2016-07-11 11:15

administrator   ~0055797

Branch CR27074 has been updated forcibly by azv.

SHA-1: d1ae6c9e4e4fd987d451569aa766b46d1a49a621

azv

2016-07-11 11:17

administrator   ~0055799

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).

git

2016-07-11 11:33

administrator   ~0055803

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

Roman Lygin

2016-07-11 12:12

developer   ~0055805

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.

msv

2016-07-11 12:36

developer   ~0055807

Dear Roman, regression is up to +19.33%, not 44%.

Roman Lygin

2016-07-11 12:49

developer   ~0055810

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.

Roman Lygin

2016-07-11 14:03

developer   ~0055815

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.

msv

2016-07-12 12:05

developer   ~0055847

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

git

2016-07-12 15:38

administrator   ~0055852

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

azv

2016-07-12 15:40

administrator   ~0055854

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.

git

2016-07-13 07:38

administrator   ~0055877

Branch CR27074 has been updated forcibly by azv.

SHA-1: 3f4ddcc1f7ce80257b4f5bd2c5887ca878332ffc

msv

2016-07-13 10:53

developer   ~0055882

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.

msv

2016-07-13 11:23

developer   ~0055883

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.

git

2016-07-14 11:40

administrator   ~0055903

Branch CR27074 has been updated forcibly by azv.

SHA-1: 368355f10566ba70e1c57832e8d12a6073f244df

git

2016-07-15 11:38

administrator   ~0055934

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)

git

2016-07-15 15:43

administrator   ~0055949

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

azv

2016-07-15 15:43

administrator   ~0055950

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%]

git

2016-07-22 13:43

administrator   ~0056175

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

git

2016-07-26 10:02

administrator   ~0056213

Branch CR27074_LC has been updated forcibly by azv.

SHA-1: f2b4d89d471d7f72ffbd2de31cf67662fac6607f

azv

2016-07-26 10:02

administrator   ~0056214

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

azv

2016-07-26 10:12

administrator   ~0056215

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.

msv

2016-08-03 10:51

developer   ~0056409

Let's keep with CR27074_ULC. Please make there corrections as we agreed.

git

2016-08-05 15:10

administrator   ~0056501

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

git

2016-08-05 15:20

administrator   ~0056502

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

azv

2016-08-05 15:21

administrator   ~0056503

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

msv

2016-08-08 10:02

developer   ~0056535

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.

git

2016-08-08 10:14

administrator   ~0056536

Branch CR27074_ULC_1 has been updated forcibly by azv.

SHA-1: 300fd122bf1f6881ce25e720a89bd35899150f7e

git

2016-09-23 07:34

administrator   ~0058040

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

abv

2016-09-23 07:38

manager   ~0058041

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.

git

2016-09-26 15:51

administrator   ~0058164

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

azv

2016-09-26 15:53

administrator   ~0058165

Dear Andrey,

Please, review branch CR27074_ULC_3. I suppose, memory leaks are eliminated.

abv

2016-09-28 11:31

manager   ~0058238

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.

abv

2016-10-03 19:53

manager   ~0058373

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%]

abv

2016-10-13 01:45

manager   ~0058638

Huge acceleration on test de step_2 U4 is due to changes in BSplCLib::BuildCache() (span index passed as argument)

msv

2017-01-24 10:09

developer   ~0062924

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.

abv

2017-01-25 14:13

manager   ~0063005

I have seen no improvements that would worth the effort. I still have to put here summary of my experiments, then we will decide.

BenjaminBihler

2017-02-07 13:53

developer   ~0063487

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

git

2017-02-25 09:40

administrator   ~0063991

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

abv

2017-02-25 10:03

manager   ~0063992

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.

git

2017-02-25 10:05

administrator   ~0063993

Branch CR27074_ULC_4 has been updated forcibly by abv.

SHA-1: 41c79a7727afb5238a5f7259d50efe49e74ab9c9

abv

2019-10-05 12:33

manager  

CR27074_LC-0027074-Support-of-multi-span-cache-in-Geom-2d-Adapt.patch (150,763 bytes)

abv

2019-10-05 12:33

manager  

CR27074_ULC-0027074-Support-of-multi-span-cache-in-Geom-2d-Adapt.patch (131,510 bytes)

abv

2019-10-05 12:37

manager   ~0087856

Last edited: 2019-10-05 12:55

Two branches prepared in the context of this issue are archived as attachments:

CR27074_LC-0027074-Support-of-multi-span-cache-in-Geom-2d-Adapt.patch: branch CR27074_LC, on top of commit b2fbf11a4f7dfcbce20d8dbf3f101a4efe8628b4

CR27074_ULC-0027074-Support-of-multi-span-cache-in-Geom-2d-Adapt.patch: branch CR27074_ULC_4, on top of commit 97f3782bb01c0baab2a6c4fb51e22f6eb6b12c78

git

2019-10-05 12:41

administrator   ~0087857

Branch CR27074 has been deleted by abv.

SHA-1: cdb82b7490d6a193758b15ebbacb89cfd3c055ba

git

2019-10-05 12:41

administrator   ~0087858

Branch CR27074_LC has been deleted by abv.

SHA-1: f2b4d89d471d7f72ffbd2de31cf67662fac6607f

git

2019-10-05 12:41

administrator   ~0087859

Branch CR27074_ULC has been deleted by abv.

SHA-1: 2151c67443ee202b6fc0a552fd35c4ce9ec82412

git

2019-10-05 12:41

administrator   ~0087860

Branch CR27074_ULC_1 has been deleted by abv.

SHA-1: 300fd122bf1f6881ce25e720a89bd35899150f7e

git

2019-10-05 12:41

administrator   ~0087861

Branch CR27074_ULC_2 has been deleted by abv.

SHA-1: bf6934266402870a854b447cb31bf9389c4762ff

git

2019-10-05 12:42

administrator   ~0087862

Branch CR27074_ULC_3 has been deleted by abv.

SHA-1: 65732b21681b94058d4abbeca61af7c97ac42530

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-29 09:36 abv Target Version 7.2.0 =>
2019-10-05 12:33 abv File Added: CR27074_LC-0027074-Support-of-multi-span-cache-in-Geom-2d-Adapt.patch
2019-10-05 12:33 abv File Added: CR27074_ULC-0027074-Support-of-multi-span-cache-in-Geom-2d-Adapt.patch
2019-10-05 12:37 abv Note Added: 0087856
2019-10-05 12:41 git Note Added: 0087857
2019-10-05 12:41 git Note Added: 0087858
2019-10-05 12:41 git Note Added: 0087859
2019-10-05 12:41 git Note Added: 0087860
2019-10-05 12:41 git Note Added: 0087861
2019-10-05 12:42 git Note Added: 0087862
2019-10-05 12:55 abv Note Edited: 0087856