View Issue Details
| ID | Project | Category | View Status | Date Submitted | Last Update |
|---|---|---|---|---|---|
| 0027074 | Community | OCCT:Modeling Data | public | 2016-01-13 09:45 | 2019-10-05 12:55 |
| Reporter | Roman Lygin | Assigned To | |||
| Priority | normal | Severity | feature | ||
| Status | feedback | Resolution | open | ||
| Product Version | 7.0.0 | ||||
| Summary | 0027074: Support of multi-span cache in Geom[2d]Adaptor | ||||
| Description | OCC 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 Reproduce | Refer 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. | ||||
| Tags | No tags attached. | ||||
| Test case number | |||||
|
|
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. |
|
|
Branch CR27074 has been updated forcibly by azv. SHA-1: 99fdd72039bbfc25dffda0fad31387fa86b373e9 |
|
|
Branch CR27074 has been updated forcibly by azv. SHA-1: d1ae6c9e4e4fd987d451569aa766b46d1a49a621 |
|
|
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). |
|
|
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 |
|
|
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. |
|
|
Dear Roman, regression is up to +19.33%, not 44%. |
|
|
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. |
|
|
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. |
|
|
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 |
|
|
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 |
|
|
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. |
|
|
Branch CR27074 has been updated forcibly by azv. SHA-1: 3f4ddcc1f7ce80257b4f5bd2c5887ca878332ffc |
|
|
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. |
|
|
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. |
|
|
Branch CR27074 has been updated forcibly by azv. SHA-1: 368355f10566ba70e1c57832e8d12a6073f244df |
|
|
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) |
|
|
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 |
|
|
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%] |
|
|
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 |
|
|
Branch CR27074_LC has been updated forcibly by azv. SHA-1: f2b4d89d471d7f72ffbd2de31cf67662fac6607f |
|
|
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 |
|
|
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. |
|
|
Let's keep with CR27074_ULC. Please make there corrections as we agreed. |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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. |
|
|
Branch CR27074_ULC_1 has been updated forcibly by azv. SHA-1: 300fd122bf1f6881ce25e720a89bd35899150f7e |
|
|
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 |
|
|
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. |
|
|
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 |
|
|
Dear Andrey, Please, review branch CR27074_ULC_3. I suppose, memory leaks are eliminated. |
|
|
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. |
|
|
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%] |
|
|
Huge acceleration on test de step_2 U4 is due to changes in BSplCLib::BuildCache() (span index passed as argument) |
|
|
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. |
|
|
I have seen no improvements that would worth the effort. I still have to put here summary of my experiments, then we will decide. |
|
|
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 |
|
|
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 |
|
|
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. |
|
|
Branch CR27074_ULC_4 has been updated forcibly by abv. SHA-1: 41c79a7727afb5238a5f7259d50efe49e74ab9c9 |
|
2019-10-05 12:33 manager |
CR27074_LC-0027074-Support-of-multi-span-cache-in-Geom-2d-Adapt.patch (150,763 bytes) |
|
2019-10-05 12:33 manager |
CR27074_ULC-0027074-Support-of-multi-span-cache-in-Geom-2d-Adapt.patch (131,510 bytes) |
|
|
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 |
|
|
Branch CR27074 has been deleted by abv. SHA-1: cdb82b7490d6a193758b15ebbacb89cfd3c055ba |
|
|
Branch CR27074_LC has been deleted by abv. SHA-1: f2b4d89d471d7f72ffbd2de31cf67662fac6607f |
|
|
Branch CR27074_ULC has been deleted by abv. SHA-1: 2151c67443ee202b6fc0a552fd35c4ce9ec82412 |
|
|
Branch CR27074_ULC_1 has been deleted by abv. SHA-1: 300fd122bf1f6881ce25e720a89bd35899150f7e |
|
|
Branch CR27074_ULC_2 has been deleted by abv. SHA-1: bf6934266402870a854b447cb31bf9389c4762ff |
|
|
Branch CR27074_ULC_3 has been deleted by abv. SHA-1: 65732b21681b94058d4abbeca61af7c97ac42530 |
| 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 |
|
Relationship added | related to 0027491 |
| 2016-06-01 12:47 |
|
Assigned To | msv => azv |
| 2016-06-01 12:47 |
|
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 |
|
Note Added: 0055799 | |
| 2016-07-11 11:17 |
|
Assigned To | azv => msv |
| 2016-07-11 11:17 |
|
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 |
|
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 |
|
Note Added: 0055847 | |
| 2016-07-12 12:05 |
|
Assigned To | msv => azv |
| 2016-07-12 12:05 |
|
Status | resolved => assigned |
| 2016-07-12 15:38 | git | Note Added: 0055852 | |
| 2016-07-12 15:40 |
|
Note Added: 0055854 | |
| 2016-07-12 15:40 |
|
Assigned To | azv => msv |
| 2016-07-12 15:40 |
|
Status | assigned => resolved |
| 2016-07-13 07:38 | git | Note Added: 0055877 | |
| 2016-07-13 10:12 |
|
Assigned To | msv => azv |
| 2016-07-13 10:12 |
|
Status | resolved => assigned |
| 2016-07-13 10:53 |
|
Note Added: 0055882 | |
| 2016-07-13 11:23 |
|
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 |
|
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 |
|
Note Added: 0056214 | |
| 2016-07-26 10:12 |
|
Note Added: 0056215 | |
| 2016-07-26 10:12 |
|
Assigned To | azv => msv |
| 2016-07-26 10:12 |
|
Status | assigned => feedback |
| 2016-08-03 10:51 |
|
Note Added: 0056409 | |
| 2016-08-03 10:51 |
|
Assigned To | msv => azv |
| 2016-08-03 10:51 |
|
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 |
|
Note Added: 0056503 | |
| 2016-08-05 15:21 |
|
Assigned To | azv => msv |
| 2016-08-05 15:21 |
|
Status | assigned => resolved |
| 2016-08-08 10:02 |
|
Note Added: 0056535 | |
| 2016-08-08 10:02 |
|
Assigned To | msv => abv |
| 2016-08-08 10:02 |
|
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 |
|
Note Added: 0058041 | |
| 2016-09-23 07:38 |
|
Assigned To | abv => azv |
| 2016-09-26 15:51 | git | Note Added: 0058164 | |
| 2016-09-26 15:53 |
|
Note Added: 0058165 | |
| 2016-09-26 15:53 |
|
Assigned To | azv => abv |
| 2016-09-26 15:53 |
|
Status | feedback => resolved |
| 2016-09-28 11:31 |
|
Note Added: 0058238 | |
| 2016-09-28 11:31 |
|
Assigned To | abv => azv |
| 2016-09-28 11:31 |
|
Status | resolved => assigned |
| 2016-10-03 19:53 |
|
Note Added: 0058373 | |
| 2016-10-13 01:45 |
|
Note Added: 0058638 | |
| 2016-11-01 06:18 |
|
Target Version | 7.1.0 => 7.2.0 |
| 2016-12-18 09:38 |
|
Relationship added | parent of 0028240 |
| 2017-01-24 10:09 |
|
Note Added: 0062924 | |
| 2017-01-24 10:09 |
|
Assigned To | azv => abv |
| 2017-01-24 10:09 |
|
Status | assigned => feedback |
| 2017-01-25 14:13 |
|
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 |
|
Note Added: 0063992 | |
| 2017-02-25 10:05 | git | Note Added: 0063993 | |
| 2017-08-29 09:36 |
|
Target Version | 7.2.0 => |
| 2019-10-05 12:33 |
|
File Added: CR27074_LC-0027074-Support-of-multi-span-cache-in-Geom-2d-Adapt.patch | |
| 2019-10-05 12:33 |
|
File Added: CR27074_ULC-0027074-Support-of-multi-span-cache-in-Geom-2d-Adapt.patch | |
| 2019-10-05 12:37 |
|
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 |
|
Note Edited: 0087856 |
