Nodes edges map graph - Githubissues

BrianHung commented 11 months ago

Context

Uses maps and sets for dependency graph to hold node ids. Faster to query for adjacent nodes, and easier to delete edges and nodes.

How did you test your changes?

Internal refactor. PR should pass graph.spec.ts.

Types of changes

[ ] Breaking change (a fix or a feature because of which an existing functionality doesn't work as expected anymore)
[x] New feature or improvement (a non-breaking change that adds functionality)
[ ] Bug fix (a non-breaking change that fixes an issue)
[ ] Additional language file, or a change to an existing language file (translations)
[ ] Change to the documentation

Related issues:

Checklist:

[x] I have reviewed the guidelines about Contributing to HyperFormula and I confirm that my code follows the code style of this project.
[x] I have signed the Contributor License Agreement.
[x] My change is compliant with the OpenDocument standard.
[x] My change is compatible with Microsoft Excel.
[x] My change is compatible with Google Sheets.
[ ] I described my changes in the CHANGELOG.md file.
[ ] My changes require a documentation update.
[ ] My changes require a migration guide.

codecov[bot] commented 11 months ago

Codecov Report

Merging #1329 (11dd3a0) into master (50731c7) will decrease coverage by 0.06%. The diff coverage is 93.38%.

@@            Coverage Diff             @@
##           master    #1329      +/-   ##
==========================================
- Coverage   97.25%   97.20%   -0.06%     
==========================================
  Files         169      169              
  Lines       14408    14430      +22     
  Branches     3076     3019      -57     
==========================================
+ Hits        14012    14026      +14     
- Misses        391      404      +13     
+ Partials        5        0       -5

Files	Coverage Δ
src/DependencyGraph/DependencyGraph.ts	`97.93% <100.00%> (-0.01%)`	:arrow_down:
src/DependencyGraph/TopSort.ts	`98.90% <98.11%> (-1.10%)`	:arrow_down:
src/DependencyGraph/Graph.ts	`95.18% <89.06%> (-4.14%)`	:arrow_down:

... and 2 files with indirect coverage changes

BrianHung commented 11 months ago

Performance before

``` > hyperformula@2.6.0 test:performance > npm run benchmark:basic && npm run benchmark:cruds > hyperformula@2.6.0 benchmark:basic > npm run tsnode test/performance/run-basic-benchmark.ts > hyperformula@2.6.0 tsnode > ts-node --transpile-only -O {\"module\":\"commonjs\"} "test/performance/run-basic-benchmark.ts" === Benchmark - Sheet A === ________________________________________________ |BUILD_ENGINE_TOTAL: 456.94 | |PREPROCESSING: 424.82 | | |GRAPH_BUILD: 381.79 | | | |INIT_DATASTRUCTURES: 105.14 | | | | |BUILD_COLUMN_INDEX: 0 | | | |PARSER: 276.65 | | |TOP_SORT: 43.03 | |EVALUATION: 19.85 | | |VLOOKUP: 0 ________________________________________________ === Benchmark - Sheet B === ________________________________________________ |BUILD_ENGINE_TOTAL: 165.68 | |PREPROCESSING: 143.57 | | |GRAPH_BUILD: 115.1 | | | |INIT_DATASTRUCTURES: 40.2 | | | | |BUILD_COLUMN_INDEX: 0 | | | |PARSER: 74.9 | | |TOP_SORT: 28.47 | |EVALUATION: 10.49 | | |VLOOKUP: 0 ________________________________________________ === Benchmark - Sheet T === ________________________________________________ |BUILD_ENGINE_TOTAL: 137.44 | |PREPROCESSING: 121.03 | | |GRAPH_BUILD: 99.01 | | | |INIT_DATASTRUCTURES: 39.56 | | | | |BUILD_COLUMN_INDEX: 0 | | | |PARSER: 59.45 | | |TOP_SORT: 22.02 | |EVALUATION: 7.1 | | |VLOOKUP: 0 ________________________________________________ === Benchmark - Column ranges === ________________________________________________ |BUILD_ENGINE_TOTAL: 540.23 | |PREPROCESSING: 424.27 | | |GRAPH_BUILD: 376.01 | | | |INIT_DATASTRUCTURES: 364.4 | | | | |BUILD_COLUMN_INDEX: 0 | | | |PARSER: 11.61 | | |TOP_SORT: 48.26 | |EVALUATION: 94.73 | | |VLOOKUP: 0 ________________________________________________ ┌─────────┬─────────────────┬───────────┐ │ (index) │ name │ totalTime │ ├─────────┼─────────────────┼───────────┤ │ 0 │ 'Sheet A' │ 456.94 │ │ 1 │ 'Sheet B' │ 165.68 │ │ 2 │ 'Sheet T' │ 137.44 │ │ 3 │ 'Column ranges' │ 540.23 │ └─────────┴─────────────────┴───────────┘ > hyperformula@2.6.0 benchmark:cruds > npm run tsnode test/performance/run-cruds-benchmark.ts > hyperformula@2.6.0 tsnode > ts-node --transpile-only -O {\"module\":\"commonjs\"} "test/performance/run-cruds-benchmark.ts" === Benchmark - Sheet A: change value, add/remove row/column === |CRUDS: 38 | |TRANSFORM_ASTS: 18 | |TRANSFORM_ASTS_POSTPONED: 4 | |ADJUSTING_ADDRESS_MAPPING: 5 | |ADJUSTING_MATRIX_MAPPING: 0 | |ADJUSTING_RANGES: 0 | |ADJUSTING_GRAPH: 1 | |EVALUATION: 7 | | |VLOOKUP: 0 ________________________________________________ === Benchmark - Sheet B: change value, add/remove row/column === |CRUDS: 253 | |TRANSFORM_ASTS: 10 | |TRANSFORM_ASTS_POSTPONED: 47 | |ADJUSTING_ADDRESS_MAPPING: 2 | |ADJUSTING_MATRIX_MAPPING: 0 | |ADJUSTING_RANGES: 51 | |ADJUSTING_GRAPH: 2 | |EVALUATION: 164 | | |VLOOKUP: 0 ________________________________________________ === Benchmark - Column ranges - add column === |CRUDS: 196 | |TRANSFORM_ASTS: 0 | |TRANSFORM_ASTS_POSTPONED: 15 | |ADJUSTING_ADDRESS_MAPPING: 0 | |ADJUSTING_MATRIX_MAPPING: 0 | |ADJUSTING_RANGES: 4 | |ADJUSTING_GRAPH: 0 | |EVALUATION: 185 | | |VLOOKUP: 0 ________________________________________________ === Benchmark - Column ranges - without batch === |CRUDS: 529 | |TRANSFORM_ASTS: 0 | |TRANSFORM_ASTS_POSTPONED: 0 | |ADJUSTING_ADDRESS_MAPPING: 0 | |ADJUSTING_MATRIX_MAPPING: 0 | |ADJUSTING_RANGES: 0 | |ADJUSTING_GRAPH: 0 | |EVALUATION: 517 | | |VLOOKUP: 0 ________________________________________________ === Benchmark - Column ranges - batch === |CRUDS: 122 | |TRANSFORM_ASTS: 0 | |TRANSFORM_ASTS_POSTPONED: 0 | |ADJUSTING_ADDRESS_MAPPING: 0 | |ADJUSTING_MATRIX_MAPPING: 0 | |ADJUSTING_RANGES: 0 | |ADJUSTING_GRAPH: 0 | |EVALUATION: 117 | | |VLOOKUP: 0 ________________________________________________ ┌─────────┬─────────────────────────────────────────────────┬───────────┐ │ (index) │ name │ totalTime │ ├─────────┼─────────────────────────────────────────────────┼───────────┤ │ 0 │ 'Sheet A: change value, add/remove row/column' │ 38 │ │ 1 │ 'Sheet B: change value, add/remove row/column' │ 253 │ │ 2 │ 'Column ranges - add column' │ 196 │ │ 3 │ 'Column ranges - without batch' │ 529 │ │ 4 │ 'Column ranges - batch' │ 122 │ └─────────┴─────────────────────────────────────────────────┴───────────┘ ```

Performance after

``` > hyperformula@2.6.0 test:performance > npm run benchmark:basic && npm run benchmark:cruds > hyperformula@2.6.0 benchmark:basic > npm run tsnode test/performance/run-basic-benchmark.ts > hyperformula@2.6.0 tsnode > ts-node --transpile-only -O {\"module\":\"commonjs\"} "test/performance/run-basic-benchmark.ts" === Benchmark - Sheet A === ________________________________________________ |BUILD_ENGINE_TOTAL: 542.53 | |PREPROCESSING: 505.24 | | |GRAPH_BUILD: 439.81 | | | |INIT_DATASTRUCTURES: 131.9 | | | | |BUILD_COLUMN_INDEX: 0 | | | |PARSER: 307.91 | | |TOP_SORT: 65.43 | |EVALUATION: 22.91 | | |VLOOKUP: 0 ________________________________________________ === Benchmark - Sheet B === ________________________________________________ |BUILD_ENGINE_TOTAL: 188.32 | |PREPROCESSING: 167.56 | | |GRAPH_BUILD: 128.62 | | | |INIT_DATASTRUCTURES: 48.3 | | | | |BUILD_COLUMN_INDEX: 0 | | | |PARSER: 80.32 | | |TOP_SORT: 38.94 | |EVALUATION: 10.16 | | |VLOOKUP: 0 ________________________________________________ === Benchmark - Sheet T === ________________________________________________ |BUILD_ENGINE_TOTAL: 159.47 | |PREPROCESSING: 141.36 | | |GRAPH_BUILD: 109.83 | | | |INIT_DATASTRUCTURES: 44.36 | | | | |BUILD_COLUMN_INDEX: 0 | | | |PARSER: 65.47 | | |TOP_SORT: 31.53 | |EVALUATION: 7.64 | | |VLOOKUP: 0 ________________________________________________ === Benchmark - Column ranges === ________________________________________________ |BUILD_ENGINE_TOTAL: 4130.13 | |PREPROCESSING: 4016.46 | | |GRAPH_BUILD: 237.2 | | | |INIT_DATASTRUCTURES: 224.74 | | | | |BUILD_COLUMN_INDEX: 0 | | | |PARSER: 12.46 | | |TOP_SORT: 3779.26 | |EVALUATION: 93.96 | | |VLOOKUP: 0 ________________________________________________ ┌─────────┬─────────────────┬───────────┐ │ (index) │ name │ totalTime │ ├─────────┼─────────────────┼───────────┤ │ 0 │ 'Sheet A' │ 542.53 │ │ 1 │ 'Sheet B' │ 188.32 │ │ 2 │ 'Sheet T' │ 159.47 │ │ 3 │ 'Column ranges' │ 4130.13 │ └─────────┴─────────────────┴───────────┘ > hyperformula@2.6.0 benchmark:cruds > npm run tsnode test/performance/run-cruds-benchmark.ts > hyperformula@2.6.0 tsnode > ts-node --transpile-only -O {\"module\":\"commonjs\"} "test/performance/run-cruds-benchmark.ts" === Benchmark - Sheet A: change value, add/remove row/column === |CRUDS: 35 | |TRANSFORM_ASTS: 13 | |TRANSFORM_ASTS_POSTPONED: 2 | |ADJUSTING_ADDRESS_MAPPING: 4 | |ADJUSTING_MATRIX_MAPPING: 0 | |ADJUSTING_RANGES: 0 | |ADJUSTING_GRAPH: 3 | |EVALUATION: 8 | | |VLOOKUP: 0 ________________________________________________ === Benchmark - Sheet B: change value, add/remove row/column === |CRUDS: 236 | |TRANSFORM_ASTS: 7 | |TRANSFORM_ASTS_POSTPONED: 56 | |ADJUSTING_ADDRESS_MAPPING: 1 | |ADJUSTING_MATRIX_MAPPING: 0 | |ADJUSTING_RANGES: 54 | |ADJUSTING_GRAPH: 2 | |EVALUATION: 148 | | |VLOOKUP: 0 ________________________________________________ === Benchmark - Column ranges - add column === |CRUDS: 448 | |TRANSFORM_ASTS: 0 | |TRANSFORM_ASTS_POSTPONED: 22 | |ADJUSTING_ADDRESS_MAPPING: 0 | |ADJUSTING_MATRIX_MAPPING: 0 | |ADJUSTING_RANGES: 5 | |ADJUSTING_GRAPH: 0 | |EVALUATION: 437 | | |VLOOKUP: 0 ________________________________________________ === Benchmark - Column ranges - without batch === |CRUDS: 900 | |TRANSFORM_ASTS: 0 | |TRANSFORM_ASTS_POSTPONED: 0 | |ADJUSTING_ADDRESS_MAPPING: 0 | |ADJUSTING_MATRIX_MAPPING: 0 | |ADJUSTING_RANGES: 0 | |ADJUSTING_GRAPH: 0 | |EVALUATION: 885 | | |VLOOKUP: 0 ________________________________________________ === Benchmark - Column ranges - batch === |CRUDS: 194 | |TRANSFORM_ASTS: 0 | |TRANSFORM_ASTS_POSTPONED: 0 | |ADJUSTING_ADDRESS_MAPPING: 0 | |ADJUSTING_MATRIX_MAPPING: 0 | |ADJUSTING_RANGES: 0 | |ADJUSTING_GRAPH: 0 | |EVALUATION: 190 | | |VLOOKUP: 0 ________________________________________________ ┌─────────┬─────────────────────────────────────────────────┬───────────┐ │ (index) │ name │ totalTime │ ├─────────┼─────────────────────────────────────────────────┼───────────┤ │ 0 │ 'Sheet A: change value, add/remove row/column' │ 35 │ │ 1 │ 'Sheet B: change value, add/remove row/column' │ 236 │ │ 2 │ 'Column ranges - add column' │ 448 │ │ 3 │ 'Column ranges - without batch' │ 900 │ │ 4 │ 'Column ranges - batch' │ 194 │ └─────────┴─────────────────────────────────────────────────┴───────────┘ ```

sequba commented 11 months ago

I assume you closed this PR because of the results of the performance testing.

For your information: we recently refactored the dependency graph to use simple arrays instead of Maps and Sets in order to improve performance (https://github.com/handsontable/hyperformula/pull/1293). For most real-world use cases simple arrays seem to be faster ;)

handsontable / hyperformula