search

iTwin / presentation

Monorepo for iTwin.js Presentation Library
https://www.itwinjs.org/presentation/
MIT License
4 stars 0 forks source link

Fix slow hierarchy filtering with large number of filtered paths #711

Closed JonasDov closed 2 weeks ago

JonasDov commented 4 weeks ago

Closes #706

changeset-bot[bot] commented 4 weeks ago

🦋 Changeset detected

Latest commit: 37bd81b914d3615d6b7c9548e546d1037a987c87

The changes in this PR will be included in the next version bump.

This PR includes changesets to release 2 packages | Name | Type | | ------------------------------------- | ----- | | @itwin/presentation-hierarchies | Minor | | @itwin/presentation-hierarchies-react | Patch |

Not sure what this means? Click here to learn what changesets are.

Click here if you're a maintainer who wants to add another changeset to this PR

github-actions[bot] commented 4 weeks ago

Hierarchies benchmark

Benchmark suite Current: 37bd81b914d3615d6b7c9548e546d1037a987c87 Previous: ba2ae5ee813ca10ba710ecce4f02ba44f765d597 Deviation Status
flat 50k elements list 4712.3 ms 4741.24 ms -0.6104% ✅
flat 50k elements list (P95 of main thread blocks) 74 ms 73 ms 1.3699% 🚨
filtering filters with 50000 paths 12930.68 ms
filtering filters with 50000 paths (P95 of main thread blocks) 276 ms
grouping by label 10917.23 ms 10942.25 ms -0.2287% ✅
grouping by label (P95 of main thread blocks) 67 ms 69 ms -2.8986% ✅
grouping by class 10949.82 ms 10882.31 ms 0.6204% 🚨
grouping by class (P95 of main thread blocks) 38 ms 33 ms 15.1515% 🚨
grouping by property 11521.93 ms 11374.21 ms 1.2987% 🚨
grouping by property (P95 of main thread blocks) 64 ms 60 ms 6.6667% 🚨
grouping by base class (10 classes) 8321.38 ms 8112.94 ms 2.5692% 🚨
grouping by base class (10 classes) (P95 of main thread blocks) 74 ms 73 ms 1.3699% 🚨
grouping by multiple attributes 28933.68 ms 28504.48 ms 1.5057% 🚨
grouping by multiple attributes (P95 of main thread blocks) 60 ms 42 ms 42.8571% 🚨
hide if no children required to finalize root, w/o children 56772.16 ms 50062.95 ms 13.4015% 🚨
hide if no children required to finalize root, w/o children (P95 of main thread blocks) 40 ms 39 ms 2.5641% 🚨
hide if no children required to finalize root, w/ children 197.64 ms 169.34 ms 16.7119% 🚨
hide if no children required to finalize root, w/ children (P95 of main thread blocks) 0 ms 0 ms NaN% 🚨
models tree initial (Baytown) 42.83 ms 41.76 ms 2.5623% 🚨
models tree initial (Baytown) (P95 of main thread blocks) 0 ms 0 ms NaN% 🚨
models tree full (Baytown) 7943.42 ms 7703.82 ms 3.1101% 🚨
models tree full (Baytown) (P95 of main thread blocks) 90 ms 87 ms 3.4483% 🚨

This comment was automatically generated by workflow using github-action-benchmark.

JonasDov commented 3 weeks ago

These implementations were tested:

  1. Base implementation - stringifying FilteredChildrenPaths and passing it to ecsql query. Then, when parsing the node, the same paths are parsed back from query result.
  2. Positions implementation - creating a dictionary of positions that show which HierarchyNodeIdentifier point to which filter paths and which identifiers positions.
  3. Positions in query implementation - similar implementation to Base implementation however, instead of passing paths to ecsql positions are passed as they contain far less data.
  4. Stateful FilteredChildrenPaths implementation - instead of passing FilteredChildrenPaths to ecsql, saving them in FilteringHierarchyDefinition and retrieving them later, when node is parsed.

Each implementation was tested 3 times running the same test with 20, 500, 1k, 10k, 49k filter paths and the average result time was retrieved:

Filter Path Count Base implementation Positions implementation Positions in query implementation Stateful FilteredChildrenPaths implementation
20 110.76 ms 114.65 ms 102.22 ms 119.76 ms
500 960.18 ms 239.49 ms 500.10 ms 233.65 ms
1k 2.29 s 364.38 ms 912.14 ms 336.81 ms
10k 232.55 s 2.32 s 50.93 s 2.17 s
49k not tested 10.22 s not tested 10.72 s

Positions implementation and Stateful FilteredChildrenPaths implementation had almost the same results, and other implementations were quite significantly slower. Since we prefer to be stateless and not stateful, Positions implementation was chosen.

grigasp commented 2 weeks ago

any idea why "Hierarchies performance benchmark" comment now contains unified selection performance numbers?

JonasDov commented 2 weeks ago

I'd like a few tests to be added to FilteringHierarchyDefinition.test.ts to cover the edge cases we discussed earlier:

  • filtering by multiple paths where ids are the same, but classes are different,
  • filtering by multiple paths where the same identifier is at different positions of the path.

Added 4 unit tests:

JonasDov commented 2 weeks ago

any idea why "Hierarchies performance benchmark" comment now contains unified selection performance numbers?

This was due to adding spec: ["./lib/**/*.test.js"] to .mocharc.json file. I tried a few things to fix this:

  1. Tried specifying --spec option in package.json, but it did not work. It seems from mocha docs, that they merge options that can be merged: https://mochajs.org/#merging
  2. Tried using MOCHA_OPTIONS, but it did not work.
  3. Tried to find a way to split .mocharc.json file into two, but did not find a way to do so.

Decided to revert the change, and add the path to launch.json, by doing it this way the debugger works.