[PERF] evaluation: (much) faster array formulas #4589
Closed
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
|
|
LucasLefevre
force-pushed
the
17.0-perf-spread-lul
branch
2 times, most recently
from
0ac833a
to
a9cb13c
Compare
LucasLefevre
force-pushed
the
17.0-perf-spread-lul
branch
3 times, most recently
from
aa44902
to
59e4205
Compare
LucasLefevre
changed the title
LucasLefevre
force-pushed
the
17.0-perf-spread-lul
branch
2 times, most recently
from
2477b09
to
5b14256
Compare
`JetSet.deleteMany` only deletes the first element found in the set, instead of deleting all elements. The reason is `wasDeleted ||= super.delete(element);`. It's equivalent to `wasDeleted = wasDeleted || super.delete(element);` and as soon as `wasDeleted` is true (when the first element is deleted) the right-hand part (`|| super.delete(element)`) is no longer executed. I simplified the method by removing the return value. It's never used and this data structure has been removed in future versions anyway. Note that it didn't cause any actual functional bug; only some useless computation in some cases. Task: 4036899
LucasLefevre
force-pushed
the
17.0-perf-spread-lul
branch
from
5b14256
to
df737cd
Compare
|
small question about the third commit message:
Did you mean spread/spreaded zone? |
When spreading the result of an array formula, we invalidate formulas depending on the spread zone. Currently, we look for the dependencies one position in the spread zone at a time. It's much more efficient to group all those individual positions in zones and call `this.getCellsDependingOn(...)` with those zones. This commit reduces the time to evaluate the large array formula dataset from 60+ seconds to ~36 seconds. Task: 4036899
Let's say we have the following array formulas: in B1: =transpose(transpose(A1:A2)) in C1: =transpose(transpose(B1:B2)) in D1: =transpose(transpose(C1:C2)) Each columns depends on the array formula in the previous column. Initially, all cells are evaluated in the order B1,C1,D1 When B1 is evaluated, all cells that depends on its result (B1 and B2) are marked to be re-evaluated in another iteration. => C1 and D1 are added to `this.nextPositionsToUpdate` At the next iteration (which evaluated C1 and D1), when C1 is evaluated it goes again: D1 is added to `this.nextPositionsToUpdate` for a third iteration. Coming back to the initial iteration: even if C1 and D1 are in `this.nextPositionsToUpdate`, they are later computed in the *current* iteration (remember the initial iteration evaluates B1,C1,D1). It's useless to re-compute them since they are already computed (and no other result invalidated their result) The evaluation of the large array formula dataset goes from ~36s to ~750ms Task: 4036899
LucasLefevre
force-pushed
the
17.0-perf-spread-lul
branch
from
df737cd
to
ddd324e
Compare
Yes, my fingers are typing themselves mechanically. I'm writing the word "spreadsheet" too much 😄 |
|
robodoo r+ |
|
@LucasLefevre @VincentSchippefilt because this PR has multiple commits, I need to know how to merge it:
|
|
robodoo rebase-ff |
robodoo
pushed a commit
that referenced
this pull request
Jul 5, 2024
Task: 4036899 Part-of: #4589 Signed-off-by: Vincent Schippefilt (vsc) <vsc@odoo.com>
robodoo
pushed a commit
that referenced
this pull request
Jul 5, 2024
`JetSet.deleteMany` only deletes the first element found in the set, instead of deleting all elements. The reason is `wasDeleted ||= super.delete(element);`. It's equivalent to `wasDeleted = wasDeleted || super.delete(element);` and as soon as `wasDeleted` is true (when the first element is deleted) the right-hand part (`|| super.delete(element)`) is no longer executed. I simplified the method by removing the return value. It's never used and this data structure has been removed in future versions anyway. Note that it didn't cause any actual functional bug; only some useless computation in some cases. Task: 4036899 Part-of: #4589 Signed-off-by: Vincent Schippefilt (vsc) <vsc@odoo.com>
robodoo
pushed a commit
that referenced
this pull request
Jul 5, 2024
When spreading the result of an array formula, we invalidate formulas depending on the spread zone. Currently, we look for the dependencies one position in the spread zone at a time. It's much more efficient to group all those individual positions in zones and call `this.getCellsDependingOn(...)` with those zones. This commit reduces the time to evaluate the large array formula dataset from 60+ seconds to ~36 seconds. Task: 4036899 Part-of: #4589 Signed-off-by: Vincent Schippefilt (vsc) <vsc@odoo.com>
robodoo
pushed a commit
that referenced
this pull request
Jul 5, 2024
Let's say we have the following array formulas: in B1: =transpose(transpose(A1:A2)) in C1: =transpose(transpose(B1:B2)) in D1: =transpose(transpose(C1:C2)) Each columns depends on the array formula in the previous column. Initially, all cells are evaluated in the order B1,C1,D1 When B1 is evaluated, all cells that depends on its result (B1 and B2) are marked to be re-evaluated in another iteration. => C1 and D1 are added to `this.nextPositionsToUpdate` At the next iteration (which evaluated C1 and D1), when C1 is evaluated it goes again: D1 is added to `this.nextPositionsToUpdate` for a third iteration. Coming back to the initial iteration: even if C1 and D1 are in `this.nextPositionsToUpdate`, they are later computed in the *current* iteration (remember the initial iteration evaluates B1,C1,D1). It's useless to re-compute them since they are already computed (and no other result invalidated their result) The evaluation of the large array formula dataset goes from ~36s to ~750ms closes #4589 Task: 4036899 Signed-off-by: Vincent Schippefilt (vsc) <vsc@odoo.com>
|
Merge method set to rebase and fast-forward. |
14 tasks
14 tasks
This was referenced Jul 8, 2024
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Description:
description of this task, what is implemented and why it is implemented that way.
Task: : TASK_ID
review checklist