Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Slow UIDL generation when scrolling through large grids #13745

Closed
pepijnve opened this issue May 12, 2022 · 5 comments · Fixed by #13746
Closed

Slow UIDL generation when scrolling through large grids #13745

pepijnve opened this issue May 12, 2022 · 5 comments · Fixed by #13746
Labels
internal improvement prerelease version for Vaadin 23.1.0 Released with Vaadin 14.8.13 Released with Vaadin 22.0.16 Released with Vaadin 23.0.11 Released with Vaadin 23.1.0.rc1

Comments

@pepijnve
Copy link
Contributor

Description of the bug

HierarchicalCommunicationController#passivateInactiveKeys calls removeAll on an AbstractSet implementation passing in a a List. This implementation of removeAll compares the size of the set with the size of the collection parameter. If the set is larger than the collection, it loops over the collection and calls remove in a loop. In the other case, it iterates over the set, calls contains on the collection for each item, and then calls Iterator.remove. This second code path leads to very poor performance when passivateInactiveKeys is called with fairly large collections since List#contains has to do a linear search for ever item in the Set. Worst case scenario this is O(n * m) in time complexity. It's significant enough to show up as a 25% hotspot during profiling.

Expected behavior

O(n * m) code paths are avoided.

Minimal reproducible example

I noticed this while testing our application with a TreeGrid contains about 10k rows and scrolling up and down rapidly.

Versions

  • Vaadin / Flow version: 23.0.7
  • Java version: 11.0.15
  • OS version: macOS
  • Browser version (if applicable): Safari 15.4
  • Application Server (if applicable): Jetty 9.4.36
  • IDE (if applicable): N/A
@pepijnve
Copy link
Contributor Author

Interestingly, as I opened up my IDE to prepare a PR it showed me exactly this 😄
image

pepijnve added a commit to pepijnve/flow that referenced this issue May 12, 2022
@pepijnve
fix: Avoid potential slow Set#removeAll call in HierarchicalCommunica…
5ffb289 
…tionController#passivateInactiveKeys

The performance of calling Set#removeAll(List) is dependent on the relative sizes of the Set and List parameter. Replace Set#removeAll with List#forEach(Set::remove) to avoid this.

Fixes vaadin#13745
@pepijnve pepijnve mentioned this issue May 12, 2022
Merged
9 tasks
pepijnve added a commit to datadobi/flow that referenced this issue May 12, 2022
@pepijnve
fix: Avoid potential slow Set#removeAll call in HierarchicalCommunica…
8cae300 
…tionController#passivateInactiveKeys

The performance of calling Set#removeAll(List) is dependent on the relative sizes of the Set and List parameter. Replace Set#removeAll with List#forEach(Set::remove) to avoid this.

Fixes vaadin#13745
pepijnve added a commit to datadobi/flow that referenced this issue May 12, 2022
@pepijnve
fix: Avoid potential slow Set#removeAll call in HierarchicalCommunica…
5ff430b 
…tionController#passivateInactiveKeys

The performance of calling Set#removeAll(List) is dependent on the relative sizes of the Set and List parameter. Replace Set#removeAll with List#forEach(Set::remove) to avoid this.

Fixes vaadin#13745
taefi added a commit that referenced this issue May 19, 2022
@pepijnve @mshabarov @taefi
fix: Avoid potential slow Set#removeAll call in HierarchicalCommunica…
ab2b80d 
…tor (#13746)

* fix: Avoid potential slow Set#removeAll call in HierarchicalCommunicationController#passivateInactiveKeys

The performance of calling Set#removeAll(List) is dependent on the relative sizes of the Set and List parameter. Replace Set#removeAll with List#forEach(Set::remove) to avoid this.

Fixes #13745

Co-authored-by: Mikhail Shabarov <[email protected]>
Co-authored-by: Soroosh Taefi <[email protected]>
vaadin-bot pushed a commit that referenced this issue May 19, 2022
@pepijnve @mshabarov
@taefi @vaadin-bot
fix: Avoid potential slow Set#removeAll call in HierarchicalCommunica…
9ca456d 
…tor (#13746)

* fix: Avoid potential slow Set#removeAll call in HierarchicalCommunicationController#passivateInactiveKeys

The performance of calling Set#removeAll(List) is dependent on the relative sizes of the Set and List parameter. Replace Set#removeAll with List#forEach(Set::remove) to avoid this.

Fixes #13745

Co-authored-by: Mikhail Shabarov <[email protected]>
Co-authored-by: Soroosh Taefi <[email protected]>
vaadin-bot pushed a commit that referenced this issue May 19, 2022
@pepijnve @mshabarov
@taefi @vaadin-bot
fix: Avoid potential slow Set#removeAll call in HierarchicalCommunica…
dc2de17 
…tor (#13746)

* fix: Avoid potential slow Set#removeAll call in HierarchicalCommunicationController#passivateInactiveKeys

The performance of calling Set#removeAll(List) is dependent on the relative sizes of the Set and List parameter. Replace Set#removeAll with List#forEach(Set::remove) to avoid this.

Fixes #13745

Co-authored-by: Mikhail Shabarov <[email protected]>
Co-authored-by: Soroosh Taefi <[email protected]>
vaadin-bot pushed a commit that referenced this issue May 19, 2022
@pepijnve @mshabarov
@taefi @vaadin-bot
fix: Avoid potential slow Set#removeAll call in HierarchicalCommunica…
497d16f 
…tor (#13746)

* fix: Avoid potential slow Set#removeAll call in HierarchicalCommunicationController#passivateInactiveKeys

The performance of calling Set#removeAll(List) is dependent on the relative sizes of the Set and List parameter. Replace Set#removeAll with List#forEach(Set::remove) to avoid this.

Fixes #13745

Co-authored-by: Mikhail Shabarov <[email protected]>
Co-authored-by: Soroosh Taefi <[email protected]>
vaadin-bot pushed a commit that referenced this issue May 19, 2022
@pepijnve @mshabarov
@taefi @vaadin-bot
fix: Avoid potential slow Set#removeAll call in HierarchicalCommunica…
ebeea1b 
…tor (#13746)

* fix: Avoid potential slow Set#removeAll call in HierarchicalCommunicationController#passivateInactiveKeys

The performance of calling Set#removeAll(List) is dependent on the relative sizes of the Set and List parameter. Replace Set#removeAll with List#forEach(Set::remove) to avoid this.

Fixes #13745

Co-authored-by: Mikhail Shabarov <[email protected]>
Co-authored-by: Soroosh Taefi <[email protected]>
vaadin-bot pushed a commit that referenced this issue May 19, 2022
@pepijnve @mshabarov
@taefi @vaadin-bot
fix: Avoid potential slow Set#removeAll call in HierarchicalCommunica…
4863f89 
…tor (#13746)

* fix: Avoid potential slow Set#removeAll call in HierarchicalCommunicationController#passivateInactiveKeys

The performance of calling Set#removeAll(List) is dependent on the relative sizes of the Set and List parameter. Replace Set#removeAll with List#forEach(Set::remove) to avoid this.

Fixes #13745

Co-authored-by: Mikhail Shabarov <[email protected]>
Co-authored-by: Soroosh Taefi <[email protected]>
mshabarov added a commit that referenced this issue May 20, 2022
@vaadin-bot @pepijnve
@mshabarov @taefi
fix: Avoid potential slow Set#removeAll call in HierarchicalCommunica…
1895251 
…tor (#13746) (#13814)

* fix: Avoid potential slow Set#removeAll call in HierarchicalCommunicationController#passivateInactiveKeys

The performance of calling Set#removeAll(List) is dependent on the relative sizes of the Set and List parameter. Replace Set#removeAll with List#forEach(Set::remove) to avoid this.

Fixes #13745

Co-authored-by: Mikhail Shabarov <[email protected]>
Co-authored-by: Soroosh Taefi <[email protected]>

Co-authored-by: Pepijn Van Eeckhoudt <[email protected]>
Co-authored-by: Mikhail Shabarov <[email protected]>
Co-authored-by: Soroosh Taefi <[email protected]>
mshabarov added a commit that referenced this issue May 20, 2022
@vaadin-bot @pepijnve
@mshabarov @taefi
fix: Avoid potential slow Set#removeAll call in HierarchicalCommunica…
40d3b41 
…tor (#13746) (#13818)

* fix: Avoid potential slow Set#removeAll call in HierarchicalCommunicationController#passivateInactiveKeys

The performance of calling Set#removeAll(List) is dependent on the relative sizes of the Set and List parameter. Replace Set#removeAll with List#forEach(Set::remove) to avoid this.

Fixes #13745

Co-authored-by: Mikhail Shabarov <[email protected]>
Co-authored-by: Soroosh Taefi <[email protected]>

Co-authored-by: Pepijn Van Eeckhoudt <[email protected]>
Co-authored-by: Mikhail Shabarov <[email protected]>
Co-authored-by: Soroosh Taefi <[email protected]>
mshabarov added a commit that referenced this issue May 20, 2022
@vaadin-bot @pepijnve
@mshabarov @taefi
fix: Avoid potential slow Set#removeAll call in HierarchicalCommunica…
7bc11b0 
…tor (#13746) (#13815)

* fix: Avoid potential slow Set#removeAll call in HierarchicalCommunicationController#passivateInactiveKeys

The performance of calling Set#removeAll(List) is dependent on the relative sizes of the Set and List parameter. Replace Set#removeAll with List#forEach(Set::remove) to avoid this.

Fixes #13745

Co-authored-by: Mikhail Shabarov <[email protected]>
Co-authored-by: Soroosh Taefi <[email protected]>

Co-authored-by: Pepijn Van Eeckhoudt <[email protected]>
Co-authored-by: Mikhail Shabarov <[email protected]>
Co-authored-by: Soroosh Taefi <[email protected]>
mshabarov added a commit that referenced this issue May 20, 2022
@vaadin-bot @pepijnve
@mshabarov @taefi
fix: Avoid potential slow Set#removeAll call in HierarchicalCommunica…
69ba14d 
…tor (#13746) (#13816)

* fix: Avoid potential slow Set#removeAll call in HierarchicalCommunicationController#passivateInactiveKeys

The performance of calling Set#removeAll(List) is dependent on the relative sizes of the Set and List parameter. Replace Set#removeAll with List#forEach(Set::remove) to avoid this.

Fixes #13745

Co-authored-by: Mikhail Shabarov <[email protected]>
Co-authored-by: Soroosh Taefi <[email protected]>

Co-authored-by: Pepijn Van Eeckhoudt <[email protected]>
Co-authored-by: Mikhail Shabarov <[email protected]>
Co-authored-by: Soroosh Taefi <[email protected]>
mshabarov added a commit that referenced this issue May 20, 2022
@vaadin-bot @pepijnve
@mshabarov @taefi
fix: Avoid potential slow Set#removeAll call in HierarchicalCommunica…
ce63f1f 
…tor (#13746) (#13817)

* fix: Avoid potential slow Set#removeAll call in HierarchicalCommunicationController#passivateInactiveKeys

The performance of calling Set#removeAll(List) is dependent on the relative sizes of the Set and List parameter. Replace Set#removeAll with List#forEach(Set::remove) to avoid this.

Fixes #13745

Co-authored-by: Mikhail Shabarov <[email protected]>
Co-authored-by: Soroosh Taefi <[email protected]>

Co-authored-by: Pepijn Van Eeckhoudt <[email protected]>
Co-authored-by: Mikhail Shabarov <[email protected]>
Co-authored-by: Soroosh Taefi <[email protected]>
@vaadin-bot
Copy link
Collaborator

This ticket/PR has been released with Vaadin 23.1.0.rc1 and is also targeting the upcoming stable 23.1.0 version.

@vaadin-bot
Copy link
Collaborator

This ticket/PR has been released with Vaadin 23.0.11.

@vaadin-bot
Copy link
Collaborator

This ticket/PR has been released with Vaadin 22.0.16.

@vaadin-bot
Copy link
Collaborator

This ticket/PR has been released with Vaadin 14.8.13.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
internal improvement prerelease version for Vaadin 23.1.0 Released with Vaadin 14.8.13 Released with Vaadin 22.0.16 Released with Vaadin 23.0.11 Released with Vaadin 23.1.0.rc1
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

fix: Avoid potential slow Set#removeAll call in HierarchicalCommunicator pepijnve/flow
3 participants
@pepijnve @mcollovati @vaadin-bot