Fix severe performance issue when removing events #9044
Conversation
|
This pull request is automatically built and testable in CodeSandbox. To see build info of the built libraries, click here or the icon next to each commit SHA. Latest deployment of this branch, based on commit fb541b2:
|
|
Clarification question: I'm not entirely sure if you want me to include the generated |
|
Hi @jwueller Thank you for sharing your proposition with all of the details explained in the description. However, the Contributing guidelines are not met. Please check the following list of requirements https://github.com/handsontable/handsontable/blob/master/CONTRIBUTING.md |
|
Hi @AMBudnik, I fixed the target branch, my bad. However, I'm still unclear on some of the other guidelines:
Could you clarify and let me know if there is anything in particular I'm missing? |
|
Thank you for your contribution. I can imagine that you needed to go through a deep investigation to It is correct that you have not committed a full build to Your question about the need for test is valid. The fact that no tests were broken might be adequate. Perhaps, some form of testing that we only do the right thing and don't do the excessive thing would be nice. But let's leave answering that for the reviewer. |
|
Maybe it's worth linking that the |
|
Interesting PR, thanks @jwueller! Before I merge the PR I have two requests. First one, can you generate a changelog file and push it to the branch? Basically, you have to execute the And second thought, It would be great to have a test in a case of regression, accidental code revert or so. I thinking about adding a test that checks if the internal @kirszenbaum In our CONTRIBUTING.md file there is nothing about generating a changelog file. Can we update this document? |
There is a performance bug in EventManager#clearEvents, where every
individual event being removed causes a linear search through all
existing event listeners.
Obviously, this scales really poorly. Example:
A 20x20 table of 400 cells, with up to 4 borders per cell will produce
1600 listeners, not including the myriad of other, unrelated listeners
that are potentially present in a table.
Listener removal iterates over all listeners, but listener removal
itself is also invoked for every single listener. This means that
removing the listener for a single border might result in 2560000 inner
iterations for this example.
It therefore seems that this formula gives a worst-case number of inner
iterations for a certain number `n` of listeners to remove:
f(n) => n*n + f(n-1)
With our example of 1600 this results in roughly 1.4e9 inner iterations,
which takes roughly a minute to execute in my test environment.
This fix only does it once per border instead, which comes out to this
formula:
f(n) => n + f(n-1)
These are just back-of-the-envelope calculations, but they match up with
the measured real-world numbers in my local tests:
Iterations of the event removal loop before the fix:
Setting borders: 7997414 iterations
Removing borders: 4292962614 iterations
Iterations of the event removal loop after the fix:
Setting borders: 2838 iterations
Removing borders: 2279707 iterations
This is still quite a significant number of iterations, but at least it
seems fast enough in practice so that a complete re-engineering of the
whole event architecture isn't strictly required.
The added test verifies that clearing multiple events never delegates to
EventManager#removeEventListener to prevent accidental performance
regressions.
|
@budnix Thanks for your feedback, I made some additions:
|
|
@budnix Shoot, you were too fast for me. I messed up the commit author information with some outdated git configuration. It's fixed in my branch, but it seems you already merged it 😄 I assume it's too late to correct it now, though. |
|
I'm guilty 😄 Do you want me to revert the changes, then you create a new PR? |
|
That's probably not necessary. Unless you do a rewrite/force push, it would still leave the incorrect information on the previous commit anyway. I guess we can just keep it the way it is now. |
|
Just out of curiosity, is there a rough timeline for the next release? It would be great to know when to expect this fix to arrive in production. |
|
As far as I know, the next release is scheduled for mid-January. Your fix will be included in it. |
|
Hi @jwueller I'm happy to notify you that we just released Handsontable v11.1.0 with your fix. Thank you again for your input :) |
Context
There is a performance bug in
EventManager#clearEvents, where every individual event being removed causes a linear search through all existing event listeners.Obviously, this scales really poorly. Example:
A 20x20 table of 400 cells, with up to 4 borders per cell will produce 1600 listeners, not including the myriad of other, unrelated listeners that are potentially present in a table.
Listener removal iterates over all listeners, but listener removal itself is also invoked for every single listener. This means that removing the listener for a single border might result in 2560000 inner iterations for this example.
It therefore seems that this formula gives a worst-case number of inner iterations for a certain number
nof listeners to remove:With our example of 1600 this results in roughly 1.4e9 inner iterations, which takes roughly a minute to execute in my test environment.
This fix only does it once per border instead, which comes out to this formula:
This is still quite a significant number of iterations, but at least it seems fast enough in practice so that a complete re-engineering of the whole event architecture isn't strictly required.
How has this been tested?
This issue and fix were tested by counting the number of iterations of the inner event removal loop of
EventManager#removeEventListenerin a test table with the dimensions from the example above.Before the fix, setting borders took 7997414 iterations of the event removal loop, while removing borders took 4292962614 iterations.
After the fix, setting borders takes 2838 iterations, while removing borders takes 2279707 iterations.
In this use-case, it seems to yield a performance improvement of several orders of magnitude.
Types of changes
Related issue(s):
This bug is directly responsible for #8823, but a lot of other issues might also be affected, due to the fundamental nature of the bug.
Affected project(s):
handsontable@handsontable/angular@handsontable/react@handsontable/vueChecklist: